← 返回题目列表

Codeforces · 387/C

C. 乔治和数字

中文机器翻译题面 查看原题

乔治是一只猫,所以他很喜欢玩。最重要的是,他喜欢摆弄他的正整数数组 b。在比赛过程中,乔治通过特殊的改变来修改阵列。让我们将 George 的当前数组标记为 b1, b2, ..., b|b| (记录|b|表示数组的当前长度)。然后一个更改是一系列操作:

- 选择两个不同的索引 i 和 j (1 ≤ i, j ≤ |b|; i ≠ j),使得 bi ≥ bj。
- 获取数字 v = concat(bi, bj),其中 concat(x, y) 是通过将数字 y 添加到数字 x 的小数记录末尾而获得的数字。例如,concat(500, 10) = 50010,concat(2, 2) = 22。
- 将数字 v 添加到数组末尾。数组的长度将增加一。
- 从数组中删除索引 i 和 j 的数字。数组的长度将减少 2,并且数组的元素将从 1 重新编号为数组的当前长度。

George 用他的数组 b 玩了很长时间,从数组 b 中收到了一个恰好包含一个数字 p 的数组。现在乔治想知道:数组 b 最初最多可以包含多少个元素?帮他找到这个号码。请注意,最初该数组只能包含正整数。

输入

输入的第一行包含单个整数 p (1 ≤ p < 10100000)。确保数字 p 不包含任何前导零。

输出

打印一个整数 — 数组 b 最初可以包含的最大元素数。

示例

输入 #1

9555

输出 #1

4

输入 #2

10000000005

输出 #2

2

输入 #3

800101

输出 #3

3

输入#4

45

输出#4

1

输入 #5

1000000000000001223300003342220044555

输出 #5

17

输入 #6

19992000

输出 #6

1

输入#7

310200

输出 #7

2

注意

让我们考虑一下测试示例:

- 最初数组 b 可以等于 {5, 9, 5, 5}。乔治的变化顺序可能是:{5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}。
- 最初数组 b 可能等于 {1000000000, 5}。请注意,数组 b 不能包含零。
- 最初数组 b 可能等于 {800, 10, 1}。
- 最初数组 b 可能等于 {45}。它不能等于{4, 5},因为George一次操作只能从这个数组中得到数组{54}。

请注意,数字可能非常大。