No.2063 ±2^k operations (easy)
タグ : / 解いたユーザー数 168
作問者 : とりゐ / テスター : 遭難者 ygussany karinohito
問題文
$n$ を正整数とします.$X=n$ から始めて,以下の操作を繰り返すことによって $X=0$ にするために必要な最小の操作回数を $f(n)$ とします.
- 非負整数 $k$ および演算子 $+,-$ のいずれかを選ぶ.
- 演算子が $+$ のとき,$X$ を $X+2^k$ で置き換える.
- 演算子が $-$ のとき,$X$ を $X-2^k$ で置き換える.
入力
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。