A11943. Polycarp and Div 3
编程题
普及/提高-
知识点
题目描述
Polycarp likes numbers that are divisible by 3.
He has a huge number $s$ . Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$ . To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$ .
For example, if the original number is $s=3121$ , then Polycarp can cut it into three parts with two cuts: $3|1|21$ . As a result, he will get two numbers that are divisible by $3$ .
Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.
What is the maximum number of numbers divisible by $3$ that Polycarp can obtain?
He has a huge number $s$ . Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$ . To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$ .
For example, if the original number is $s=3121$ , then Polycarp can cut it into three parts with two cuts: $3|1|21$ . As a result, he will get two numbers that are divisible by $3$ .
Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.
What is the maximum number of numbers divisible by $3$ that Polycarp can obtain?
输入格式
The first line of the input contains a positive integer $s$ . The number of digits of the number $s$ is between $1$ and $2\cdot10^5$ , inclusive. The first (leftmost) digit is not equal to 0.
输出格式
Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$ .
输入输出样例
输入 #1
3121
输出 #1
2
输入 #2
6
输出 #2
1
输入 #3
1000000000000000000000000000000000
输出 #3
33
输入 #4
201920181
输出 #4
4
说明/提示
In the first example, an example set of optimal cuts on the number is 3|1|21.
In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $3$ .
In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $33$ digits 0. Each of the $33$ digits 0 forms a number that is divisible by $3$ .
In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$ , $9$ , $201$ and $81$ are divisible by $3$ .
In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $3$ .
In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $33$ digits 0. Each of the $33$ digits 0 forms a number that is divisible by $3$ .
In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$ , $9$ , $201$ and $81$ are divisible by $3$ .