コラッツ写像

テストケースに不備があることが確認されました。(14:50)

修正いたしました。誠に申し訳ございません。(14:54)

問題文

森久保くんは最初、$1$ 以上の整数 $X_1, X_2$ を持っており、次の操作をちょうど $N$ 回行いました。

1. $i$ を $1$ か $2$ から選ぶ
2. $X_i$ を次の値に置き換える
   • $X_i$ が偶数なら $\dfrac{X_i}{2}$
   • $X_i$ が奇数なら $3X_i + 1$

その結果、森久保くんが持っている値は $Y_1, Y_2$ となりました。森久保くんが最初に持っていた値の合計 $X_1 + X_2$ が $S$ であった可能性はありますか？

ヒント

本問題には $2$ 秒の時間制限があり、それを超えた場合は TLE と表示され、不正解となります。詳しくはこちらをご覧ください。

制約

• $1 \leq N \leq 14$
• $1 \leq S \leq 10^{18}$
• $1 \leq Y_1, Y_2 \leq 10^9$
• $N, S, Y_1, Y_2$ は整数

入力

出力

$Y_1, Y_2$ にできるならば Yes と出力し、そうでなければ No と出力してください。

入力例 $1$

3 8 5 16

出力例 $1$

Yes

$(X_1, X_2) = (3, 5)$ であったとき、次のように操作を行うと $(Y_1, Y_2) = (5, 16)$ になります。

1. $i = 1$ を選ぶ。$X_1$ が奇数なので $X_1$ を $3X_1 + 1 = 10$ で置き換える。$(X_1, X_2) = (10, 5)$ となる。
2. $i = 2$ を選ぶ。$X_2$ が奇数なので $X_2$ を $3X_2 + 1 = 16$ で置き換える。$(X_1, X_2) = (10, 16)$ となる。
3. $i = 1$ を選ぶ。$X_1$ が偶数なので $X_1$ を $\dfrac{X_1}{2} = 5$ で置き換える。$(X_1, X_2) = (5, 16)$ となる。

最初に持っていた値 $(X_1, X_2) = (3, 5)$ の合計は $8$ となり、$S$ に一致します。

入力例 $2$

2 4 1 2

出力例 $2$

No

森久保くんが最初に持っていた値 $(X_1, X_2)$ としてありえるのは $(1, 3), (2, 2), (3, 1)$ です。

どの $(X_1, X_2)$ を選んでどのように操作しても、 ちょうど $2$ 回の操作の後に $(Y_1, Y_2) = (1, 2)$ となることはありません。

入力例 $3$

5 6 4 5

出力例 $3$

No

入力例 $4$

14 76851851850 999999999 1000000000

出力例 $4$

Yes

$S$ の値は $32$bit整数に収まらない可能性があります。