問題一覧 > 通常問題

No.2063 ±2^k operations (easy)

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

問題文

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

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

入力

$N$

  • $1\leq N\lt 2^{100000}$
  • $N$ は $2$ 進法で与えられる．

出力

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

サンプル

サンプル1
入力
10100
出力
Yes

$N$ は $2$ 進法で与えられるため，$10$ 進法に直すと $N=20$ です．

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

サンプル2
入力
11100
出力
Yes

$N$ は $2$ 進法で与えられるため，$10$ 進法に直すと $N=28$ です．

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

サンプル3
入力
10000
出力
No

$N$ は $2$ 進法で与えられるため，$10$ 進法に直すと $N=16$ です．

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

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