問題一覧 > 通常問題

No.884 Eat and Add

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 154
作問者 : QCFium / テスター : e869120
お気に入りにしたユーザー ProblemId : 3334 / 自分の提出
問題文最終更新日: 2019-09-02 13:42:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 223 (順位表) の他の問題:

Problem Statement

There is one plate in front of you, with $N$ apples on it.
Find the minimum number of operations needed to empty the plate by repeatedly performing either of the following operations. The two operations may be performed in any order.

  • Choose a non-negative integer $k$ and eat $2^k$ apples from the plate. This operation cannot be performed if the plate does not have at least $2^k$ apples.
  • Choose a non-negative integer $k$ and add $2^k$ apples to the plate.

Input

$N$

$1 \le N \lt 2^{200000}$
$N$ is an integer, given in binary without extra leading zeros.

Output

Output the minimum number of operations. Print a newline at the end.

Sample

Sample 1
Input
101
Output
2

There are 5 apples, and you can, for example, operate as follows.

  • Eat $2^2=4$ apples
  • Eat $2^0=1$ apple

Sample 2
Input
111
Output
2

You can add 1 apple to the 7 apples and then eat 8 apples.

Sample 3
Input
11110101101110110001100
Output
8

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