問題一覧 > 通常問題

No.2063 ±2^k operations (easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 171
作問者 : とりゐ / テスター : 遭難者 👑 ygussany karinohito
0 ProblemId : 8446 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-01 01:31:53

問題文

nn を正整数とします.X=nX=n から始めて,以下の操作を繰り返すことによって X=0X=0 にするために必要な最小の操作回数を f(n)f(n) とします.

  • 非負整数 kk および演算子 +,+,- のいずれかを選ぶ.
    • 演算子が ++ のとき,XXX+2kX+2^k で置き換える.
    • 演算子が - のとき,XXX2kX-2^k で置き換える.
正整数 NN22 進法で与えられるので,f(N)=2f(N)=2 かどうか判定してください.

入力

NN

  • 1N<21000001\leq N\lt 2^{100000}
  • NN22 進法で与えられる.

出力

f(N)=2f(N)=2 なら Yes を,そうでないなら No を出力してください.

サンプル

サンプル1
入力
10100
出力
Yes

NN22 進法で与えられるため,1010 進法に直すと N=20N=20 です.

n=20n=20 のとき,11 回目の操作で (2,)(2,-) を選ぶことで X=16X=16 とすることができ,22 回目の操作で (4,)(4,-) を選ぶことで X=0X=0 とすることができます.11 回の操作で 00 にすることは不可能なため f(20)=2f(20)=2 です.

サンプル2
入力
11100
出力
Yes

NN22 進法で与えられるため,1010 進法に直すと N=28N=28 です.

n=28n=28 のとき,11 回目の操作で (5,)(5,-) を選ぶことで X=4X=-4 とすることができ,22 回目の操作で (2,+)(2,+) を選ぶことで X=0X=0 とすることができます.11 回の操作で 00 にすることは不可能なため f(28)=2f(28)=2 です.

サンプル3
入力
10000
出力
No

NN22 進法で与えられるため,1010 進法に直すと N=16N=16 です.

n=16n=16 のとき,11 回目の操作で (4,)(4,-) を選ぶことで X=0X=0 とすることができます.よって f(16)=1f(16)=1 です.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。