C - Cash Register Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋君は、レジ打ちの仕事をしています。

レジの機械には 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の 11 個のボタンがあります。 レジの機械には、はじめ 0 が表示されています。 ボタン 00 を押すと、表示されている数が 100 倍されます。 それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。

高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。

制約

  • 1\leq S\leq 10^{100000}
  • S は整数

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを 1 行で出力せよ。

入力例 1

40004

出力例 1

4

例えば、次のように操作することでボタンを 4 回押して 40004 を表示させることができます。 はじめ、レジには 0 が表示されています。

  • ボタン 4 を押す。レジに表示されている数は 4 となる。
  • ボタン 00 を押す。レジに表示されている数は 400 となる。
  • ボタン 0 を押す。レジに表示されている数は 4000 となる。
  • ボタン 4 を押す。レジに表示されている数は 40004 となる。

3 回までボタンを押すことでレジに 40004 を表示させることはできないので、出力すべき値は 4 です。

入力例 2

1355506027

出力例 2

10

入力例 3

10888869450418352160768000001

出力例 3

27

S は 64\operatorname{bit} 整数に収まらない場合があることに注意してください。

Score : 300 points

Problem Statement

Takahashi is a cashier.

There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The cash register initially displays 0. Whenever he types the key 00, the displayed number is multiplied by 100; whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.

Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?

Constraints

  • 1\leq S\leq 10^{100000}
  • S is an integer.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer in a line.

Sample Input 1

40004

Sample Output 1

4

For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.

  • Type the key 4. It now displays 4.
  • Type the key 00. It now displays 400.
  • Type the key 0. It now displays 4000.
  • Type the key 4. It now displays 40004.

He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.

Sample Input 2

1355506027

Sample Output 2

10

Sample Input 3

10888869450418352160768000001

Sample Output 3

27

Note that S may not fit into a 64-\operatorname{bit} integer type.