No.884 Eat and Add

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 86
作問者 : QCFiumQCFium / テスター : e869120e869120
2 ProblemId : 3334 / 出題時の順位表

問題文

あなたの前に1つの皿があり、りんごが$N$個あります。
以下のどちらかの操作を繰り返して皿を空にするとき、操作回数の最小値を求めてください。2つの操作はどのような順番で行っても構いません。

  • 非負整数$k$を選び、皿から$2^k$個のりんごを食べる。皿に$2^k$個以上のりんごがない場合この操作はできない。
  • 非負整数$k$を選び、皿に$2^k$個のりんごを追加する。

入力

$N$

$1 \le N \lt 2^{200000}$
$N$は整数で、先頭に余計な0を含まない2進数で与えられる。

出力

操作回数の最小値を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
101
出力
2

5個のりんごがあり、例えば次のように操作すれば良いです。

  • $2^2=4$個のりんごを食べる
  • $2^0=1$個のりんごを食べる

サンプル2
入力
111
出力
2

7個のりんごに1個追加してから8個食べれば良いです。

サンプル3
入力
11110101101110110001100
出力
8

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。