『ACM C++』 Codeforces | 1005D - Polycarp and Div 3

------------------------------------------------题目----------------------------------------------------------

Polycarp and Div 3

Polycarp likes numbers that are divisible by 3.

He has a huge number ss. Polycarp wants to cut from it the maximum number of numbers that are divisible by 33. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after mm such cuts, there will be m+1m+1 parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by 33.

For example, if the original number is s=3121s=3121, then Polycarp can cut it into three parts with two cuts: 3|1|213|1|21. As a result, he will get two numbers that are divisible by 33.

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 33 that Polycarp can obtain?

Input

The first line of the input contains a positive integer ss. The number of digits of the number ss is between 11 and 2⋅1052⋅105, inclusive. The first (leftmost) digit is not equal to 0.

Output

Print the maximum number of numbers divisible by 33 that Polycarp can get by making vertical cuts in the given number ss.

Examples

input

3121

output

 2

input

 6

output

 1

input

1000000000000000000000000000000000

output

33

input

201920181

output

 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 33.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and 3333 digits 0. Each of the 3333digits 0 forms a number that is divisible by 33.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers 00, 99, 201201 and 8181 are divisible by 33.

------------------------------------------------题目----------------------------------------------------------

（一） 原题大意：

　　输入一个数，某人可以进行以下的操作：　　

　　某人可以进行任意数量的垂直切割，其中每个切割在一对相邻的数字之间进行。结果数字不能包含额外的前导零（也就是说，当且仅当此数字恰好是一个字符' 0 '时，数字才能以0开头）。例如，007，01和00099不是有效的数字，但90，0和10001是有效的。

　　分割出来的每一部分的数，都能被3整除，则说明可以得到一个整除3的数，其中0也能被3整除，请算一算能为该同学获得最多几个整除3的数呢？

（二） 题目分析：

　　首先，肯定是需要得到每一个数字，如果这个数字是0，那么答案比较简单，如果当前数字能够直接被3整除（0， 3， 6， 9）的话，那就直接结果加一就好了。 

　　然后如果这两种情况都不成立，那么就是两位数以上的组合了，在这里我出了点弯路子，刚开始用求和法，然后却疯狂到test11就WA了，检查了很久也没有找到解决办法，后来心理课结束后和大佬们交谈才发现一些新想法奥秘，那就是符合3整除的数，求余之后有特殊关系，待会列一下我的弯路给自己提个醒。

　　然后我换了一种方法，那就是用加和，利用整除3的特性，下面也列出来了，但还是WA了。

　　最后我翻看一些博客，发现在我原来写得基础上，只要改变if条件的位置就能AC了，总结来说有三种情况：当前数字模3为0、现有的数字之和模3为0（当前正在处理的）、隔了三个数字了一定可以做到模3为0

（三） 错误弯路：

　　第一次直接用long long int 去扔输入，然后丢OJ结果发现第一次就WA了

#include<stdio.h>
#include<math.h>
long long int temp,num;
int temp_num,counter,ans,k;
int main()
{
    ans = 0;
    scanf("%d",&temp);
    num = temp;
    while(num>0)
    {
        k = num % 10;
        if(k == 0)
        {
            ans++;
            counter = temp_num = 0;
            num = num / 10;
            continue;
        }
        if(k % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
        }
        else
        {
            temp_num += k * pow(10,counter);
            if(temp_num % 3 == 0)
            {
                ans++;
                counter = temp_num = 0;
            }
        }
        num = num / 10;
    }
    printf("%d\n",ans);
    return 0;
 } 

　　结果是因为scanf这里用了%d，结果才发现过样例1000000000000000000000000000的时候错了，然后就换了一种方法，像这样大数都只能用char来处理了：

　　第二步弯路，然后就改了改，扔进去：

#include<stdio.h>
#include<math.h>
#include<string.h>
char input[2000005];
int num;
int temp_num,counter,ans,k;
int main()
{
    ans = 0;
    scanf("%s",&input);
    for(int i = strlen(input) - 1;i>=0;i--)
    {
        k = input[i];
        if(k == 0)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
        if(k % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
        }
        else
        {
            temp_num += k * pow(10,counter);
            if(temp_num % 3 == 0)
            {
                ans++;
                counter = temp_num = 0;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
 } 

　　到这里样例就都全过了，代码思路是：将输入的值扔进char数组里，然后获取到他的长度，从后往前来处理，从判断当前数是否为0，如果是的话就直接加一，然后判断当前数能否被3整除，如果可以就也直接加一。都没有的话，就存到一个temp变量里，然后与后面处理的数求和，然后判断该求和temp是否能被3整除。结果这里到test11就WA了，半天没搞懂，后来和同学讨论了半天，结果发现对于122 221这样的数判断就出现了问题，后来实在解不了，嫌判断太乱，都单独列了出来，结果居然AC了：

#include<stdio.h>
#include<math.h>
#include<string.h>
char input[200005];
long long int temp_num,counter,ans,k;
int main()
{
    ans = counter = 0;
    scanf("%s",&input);
    for(int i = strlen(input) - 1;i>=0;i--)
    {
        k = input[i] - '0';
        temp_num += k;
        counter++;
        if(counter == 3)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
        else if(k % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
        else if(temp_num % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
    }
    printf("%d\n",ans);
    return 0;
 } 

　　结果误打误撞发现了一些牛皮的数学思维~ 待会献上：

（四）AC代码：

　　　　因为代码比较简单，依旧不分块了~

#include<stdio.h>
#include<math.h>
#include<string.h>
char input[200005];
long long int temp_num,counter,ans,k;
int main()
{
    ans = counter = 0;
    scanf("%s",&input);
    for(int i = strlen(input) - 1;i>=0;i--)
    {
        k = input[i] - '0';
        temp_num += k;
        counter++;
        if(counter == 3 || k % 3 == 0 || temp_num % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
        }
    }
    printf("%d\n",ans);
    return 0;
 } 

（五）AC截图：

（六）解后分析：

　　　　分析1 - 能被特殊数整除的特征：

1、能被2整除的数的特征。

   如果一个数能被2整除，那么这个数末尾上的数为偶数，“0”、“2”、“4”、“6”、“8”。

2、能被3整除的数的特征。

   如果一个数能被3整除，那么这个数所有数位上数字的和是3的倍数。例如：225能被3整除，因为2+2+5=9,9是3的倍数，所以225能被3整除。

3、能被4整除的数的特征。

   如果一个数的末尾两位能被4整除，这个数就能被4整除。例如：15692512能不能被4整除呢？因为15692512的末尾两位12，能被4整除，所以15692512能被4整除。

4、能被5整除的数的特征。

   若一个数的末尾是0或5，则这个数能被5整除。

5、能被7整除的数的特征。

方法一：若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否是7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否是7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，以此类推。

方法二：如果一个多位数的末三位数与末三位以前的数字所组成的数的差，是7的倍数，那么这个数就能被7整除。例如：280678末三位数是678，末三位以前数字所组成的数是280,679-280=399,399能被7整除，因此280679也能被7整除。

方法三：首位缩小法，减少7的倍数。

例如，判断452669能不能被7整除，452669-420000=32669，只要32669能被7整除即可。可对32669继续，32669-28000=4669,4669-4200=469,469-420=49,49当然被7整除所以452669能被7整除。
6、能被8整除的数的特征。
   若一个整数的未尾三位数能被8整除，则这个数能被8整除。
7、能被9整除的数的特征。
   若一个数的数位上的数字的和能被9整除，则这个整数能被9整除。例如：111111111能不能被9整除呢？因为1+1+1+1+1+1+1+1+1=9,9是9的倍数，所以111111111能被9整除。
8、能被11整除的数的特征。
   方法一：若一个整数的奇位数字之和与偶位数字之和（从右往左数）的差能被11整除，则这个数能被11整除。例如，判断491678能不能被11整除。奇位数字之和8+6+9=23；偶位数字之和7+1+4=12；23-12=11,11能被11整除，所以491678能被11整除。这种方法叫作“奇偶位差法”。  

方法二：11的倍数检验法也可用上述检查7的「割尾法」处理！过程唯一不同的是：倍数不是2而是1！例如：判断491678能不能被11整除，49167-8=49159,4915-9=4906，

490-6=484,48-4=44。44能被11整除，所以得491678能被11整除。

方法三：还可以根据7的方法二判断。例如：283679的末三位数是679，末三位以前数所组成的数是283,679-283=396,396能被11整除，因此283679就一定能被11整除。
9、能被13整除的数的特征。
   方法一：若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，如果和是13的倍数，则原数能被13整除。如果和太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验和」的过程，直到能清楚判断为止。

例如，判断1284322能不能被13整除。128432+2×4=128440,12844+0×4=12844，

1284+4×4=1300,1300÷13=100。所以1284322能被13整除。

方法二：前面7的方法二，也适用判定13。例如：判定1284322能不能被13整除，128432的末尾三位数是322，末尾以前的数字所组成的数是1284,322-1284=-962。962÷13=74。所以1284322能被13整除。
10、能被17整除的数的特征。
    方法一：若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，如果差是17的倍数，则原数能被17整除。如果差太大或心算不易看出是否17的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断1675282能不能被17整除，167528-2×5=167518,16751-8×5=16711,1671-1×5=1666,166-6×5=136,

136÷17=8，所以1675282能被17整除。

方法二：若一个整数的末三位与3倍的前面的隔出数的差能被17整除，则这个数能被17整除。例如，判断1675282能不能被17整除，1675282的末三位是282，前面的数是1675，

282-1675×3=-4743,4743÷17=279，所以1675282能被17整除。

11、能被19整除的数的特征。  

方法一：若一个整数的末三位与7倍的前面的隔出数的差能被19整除，则这个数能被19整除。例如，判断234555能不能被19整除，234555末尾三位数是555，前面三位是234，

555-234×7=-1083,1083÷19=57，所以234555能被19整除。

方法二：若一个整数的个位数字截去，再从余下的数中，加上个位数的2倍，如果和是19的倍数，则原数能被19整除。如果和太大或心算不易看出是否19的倍数，就需要继续上述「截尾、倍大、相加、验和」的过程，直到能清楚判断为止。
12、能被23整除的数的特征。
    若一个整数的末四位与前面5倍的隔出数的差能被23(或29)整除，则这个数能被23整除。

13、能被25整除的数的特征。

如果一个数的末尾两位能被25整除，则这个数能被25整除。

14、能被125整除的数的特征。

    如果一个数的末尾三位能被125整除，则这个数能被125整除。

 

 

分析2-为什么将counter == 3判断单独拿出来就能求解了？

　　考虑将每个数字模3以后的结果。

　　如果对于当前数字能被3整除（0、3、6、9）模3结果为0的数，则直接个数加1

　　如果是两个数字那就有四种可能(1,1) (2, 2) (1, 2) (2, 1)其中后两个组合之和为3能被3整除

　　如果是三个数字对于之前两个数字的组合只剩下(1, 1)和(2, 2) 那么下个数不管是1还是2都可以组成一个3的整数倍

分析3-其他优质解法搜集：

　　解法一：

　　  贪心思路：
　　对每位数字对3求余,则结果只能是0、1、2.如果当前位是0，则对结果贡献为1，如果不为0，则判断连续出现2或者1的数目num，如果num%3为0，则对结果的贡献为num/3，否则可以找到一个与当前数字不相等的数字(前面连续出现的是2，当前为1。或者前面连续出现的是1，当前为2)，则对结果贡献是num/3+1.

#include<bits/stdc++.h>

using namespace std;
string s;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        s[i] = (s[i] - '0') % 3 + '0';
    }
    int num = 1;
    int ans = 0;
    for(int i = 1; i < s.length(); i++) {
        if(s[i] == s[i-1]) num++;
        else {
            if(s[i] == '0') {
                ans += num / 3;
                num = 1;
            }
            else if(s[i-1] == '0') {
                ans += num;
                num = 1;
            }
            else {
                ans += num / 3;
                if(num % 3) {
                    ans++;
                    num = 0;
                }
                else num = 1;
            }
        }
    }
    if(s[s.length()-1] == '0') ans += num;
    else ans += num / 3;
    cout << ans << endl;
    return 0;
}

　　解法二：

　　dp思路：
　　dp[i]表示截止到下标为i的元素之前最多有多少个片段%3=0。很容易想到当(sum[i]-sum[j]) % 3 == 0时，dp[i] = max{dp[j]} + 1;所以用一个pre[]数组表示和当前sum值相等的上一个sum值，中间肯定经历了一个(+3)%3的过程。所以最终的状态方程是dp[i] = max(dp[pre[sum]]+1, dp[i]);

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e7;
string s;
int dp[maxn], pre[maxn];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    memset(pre, -1, sizeof(pre));
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        s[i] = (s[i] - '0') % 3 + '0';
    }
    dp[0] = (s[0] == '0');
    int sum = s[0] - '0';
    pre[sum] = 0;
    for(int i = 1; i < s.length(); i++) {
        int t = s[i] - '0';
        sum = (sum + t) % 3;
        dp[i] = dp[i-1];
        if(sum == 0) dp[i] = max(dp[i], 1);
        if(pre[sum] != -1) dp[i] = max(dp[pre[sum]] + 1, dp[i]);
        pre[sum] = i;
    }
    cout << dp[s.length()-1] << endl;
    return 0;
}

　　解法三：大师兄的神奇循环解法：

注：如果有更好的解法，真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~