問題一覧 > 通常問題

No.884 Eat and Add

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : QCFiumQCFium / テスター : e869120e869120
7 ProblemId : 3334 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-09-02 13:42:11

問題文

あなたの前に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

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