Codeforces Round #496 (Div. 3)--D. Polycarp and Div 3（emm.... 难受~~，数学题）

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?

Input

The first line of the input contains a positive integer $s$ . The number of digits of the number $s$ is between $1$ and $2 \cdot 10^{5}$ , inclusive. The first (leftmost) digit is not equal to 0.

Output

Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$ .

   Examples  
     input           Copy     
3121
     output           Copy     
2
     input           Copy     
6
     output           Copy     
1
     input           Copy     
1000000000000000000000000000000000
     output           Copy     
33
     input           Copy     
201920181
     output           Copy     
4

Note

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$

题意：把一组数据分啊分，分成任意组，找到可以整除3的个数。

思路：1.这个数取余 3 之后的性质不变，划分的每部分数都不超过三个。

2.循环一遍，单个数，或部分连续和可以整除3 或被3整除。

emmm.......不会第三种。人家写的好象是dp。

就。。。。。。俩个代码

#include <stdio.h>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s1;
	while(cin >> s1)
	{
		int ans = 0;
		for(int i = 0 ; i < s1.length() ; i++)
		{
			int t = (s1[i]-'0') % 3;
		
		 	s1[i] = t + '0';
		 	if(s1[i] == '0')
		 	{
		 		s1[i] = '#';
		 		ans++;
			 }
				if(i >= 2 && s1[i] == '1' && s1[i-1] == '1' && s1[i-2] == '1') ans++ , s1[i] = s1[i-1] = s1[i-2] = '#'; 
				if(i >= 2 && s1[i] == '2' && s1[i-1] == '2' && s1[i-2] == '2') ans++ , s1[i] = s1[i-1] = s1[i-2] = '#'; 
				if(i >= 1 && s1[i] == '2' && s1[i-1] == '1')ans++ , s1[i] = s1[i-1] = '#';
				if(i >= 1 && s1[i] == '1' && s1[i-1] == '2')ans++ , s1[i] = s1[i-1] = '#';
		 }
		 printf("%d\n" , ans);
	}
	return 0;
 }

这里还有一个小知识点，hia hia hia~~

逗号是下面这个操作

而分号是这个：

2.第二个代码

#include <stdio.h>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main()
{
	string s1;
	while(cin >> s1)
	{
		long long int sum = 0 , ret = 0 ,ans = 0;
		for(int i = 0 ; i < s1.length() ; i++)
		{
			if((s1[i]-'0') % 3 == 0)
			{
				ans++;
				sum = ret = 0;
			}
			else
			{
				sum = sum + (s1[i]-'0');
				ret++;
				if(sum % 3 == 0 || ret == 3)
				{
					ans++;sum = ret = 0;
				}
				
			}
		 } 
		 cout << ans << endl;
	}
	return 0;
 }

评论加载中...