問題一覧 > 通常問題

No.2063 ±2^k operations (easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 163
作問者 : とりゐとりゐ / テスター : karinohitokarinohito 遭難者遭難者 👑 ygussanyygussany
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もしくは右上の雲マークをクリックしてアカウントを作成してください。