302038: CF387C. George and Number

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

George and Number

题意翻译

乔治喜欢对他的数列 b 进行操作。 我们将乔治的数列表示成 b1, b2, ..., b|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 加到数列的末尾。数列长度增加1。 将数列中第 i 项和第 j 项删除。数列长度缩短 2 ,并且数列会被重新编号为 1 到当前数列长度。 乔治进行了太多的操作使得数列 b 使得数列最终只存在一个数 p。现在乔治想知道,数列 b 最初最多能有几个数?帮他求出答案。注意数列最初只能包含正整数。 Input 第一行包含一个整数 p (1 ≤ p < 10100000)。 保证数字 p 最高位不为0。 Output 输出一个整数 — 数列 b 最初的最长长度。 Example Input 9555 Output 4 Input 10000000005 Output 2 Input 800101 Output 3 Input 45 Output 1 Input 1000000000000001223300003342220044555 Output 17 Input 19992000 Output 1 Input 310200 Output 2 Note 我们来看样例: 数列 b 最初可以是 {5, 9, 5, 5}。这个数列的变化可以是:{5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}. 数列 b 最初可以是 {1000000000, 5}。注意数列 b 不能包含0。 数列 b 最初可以是 {800, 10, 1}. 数列 b 最初可以是 {45}。这个数列最初不能是 {4, 5},因为乔治只能将他变成 {54}。 注意这些数可能会很大。

题目描述

George is a cat, so he really likes to play. Most of all he likes to play with his array of positive integers $ b $ . During the game, George modifies the array by using special changes. Let's mark George's current array as $ b_{1},b_{2},...,b_{|b|} $ (record $ |b| $ denotes the current length of the array). Then one change is a sequence of actions: - Choose two distinct indexes $ i $ and $ j $ $ (1<=i,j<=|b|; i≠j) $ , such that $ b_{i}>=b_{j} $ . - Get number $ v=concat(b_{i},b_{j}) $ , where $ concat(x,y) $ is a number obtained by adding number $ y $ to the end of the decimal record of number $ x $ . For example, $ concat(500,10)=50010 $ , $ concat(2,2)=22 $ . - Add number $ v $ to the end of the array. The length of the array will increase by one. - Remove from the array numbers with indexes $ i $ and $ j $ . The length of the array will decrease by two, and elements of the array will become re-numbered from $ 1 $ to current length of the array. George played for a long time with his array $ b $ and received from array $ b $ an array consisting of exactly one number $ p $ . Now George wants to know: what is the maximum number of elements array $ b $ could contain originally? Help him find this number. Note that originally the array could contain only positive integers.

输入输出格式

输入格式


The first line of the input contains a single integer $ p $ ( $ 1<=p&lt;10^{100000} $ ). It is guaranteed that number $ p $ doesn't contain any leading zeroes.

输出格式


Print an integer — the maximum number of elements array $ b $ could contain originally.

输入输出样例

输入样例 #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

说明

Let's consider the test examples: - Originally array $ b $ can be equal to $ {5,9,5,5} $ . The sequence of George's changes could have been: $ {5,9,5,5}→{5,5,95}→{95,55}→{9555} $ . - Originally array $ b $ could be equal to $ {1000000000,5} $ . Please note that the array $ b $ cannot contain zeros. - Originally array $ b $ could be equal to $ {800,10,1} $ . - Originally array $ b $ could be equal to $ {45} $ . It cannot be equal to $ {4,5} $ , because George can get only array $ {54} $ from this array in one operation. Note that the numbers can be very large.

Input

题意翻译

乔治喜欢对他的数列 b 进行操作。 我们将乔治的数列表示成 b1, b2, ..., b|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 加到数列的末尾。数列长度增加1。 将数列中第 i 项和第 j 项删除。数列长度缩短 2 ,并且数列会被重新编号为 1 到当前数列长度。 乔治进行了太多的操作使得数列 b 使得数列最终只存在一个数 p。现在乔治想知道,数列 b 最初最多能有几个数?帮他求出答案。注意数列最初只能包含正整数。 Input 第一行包含一个整数 p (1 ≤ p < 10100000)。 保证数字 p 最高位不为0。 Output 输出一个整数 — 数列 b 最初的最长长度。 Example Input 9555 Output 4 Input 10000000005 Output 2 Input 800101 Output 3 Input 45 Output 1 Input 1000000000000001223300003342220044555 Output 17 Input 19992000 Output 1 Input 310200 Output 2 Note 我们来看样例: 数列 b 最初可以是 {5, 9, 5, 5}。这个数列的变化可以是:{5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}. 数列 b 最初可以是 {1000000000, 5}。注意数列 b 不能包含0。 数列 b 最初可以是 {800, 10, 1}. 数列 b 最初可以是 {45}。这个数列最初不能是 {4, 5},因为乔治只能将他变成 {54}。 注意这些数可能会很大。

加入题单

算法标签: