preface

Blue Bridge Cup 2020 provincial competition, programming problem (C + +)

1, Title Description

During the Spring Festival in 2020, a special date has attracted everyone's attention: February 2, 2020. Because if this date is written in the format of "yyyymmdd", it is 20200202, which is exactly a palindrome number. We call this date palindrome date.

Some people said that 20200202 is a special day of "once in a thousand years". Xiao Ming disagrees with this, because the next palindrome date is less than two years later: 20211202, that is, December 2, 2021.

Others said that 20200202 is not only a palindrome date, but also an abbaba palindrome date. Xiao Ming also disagrees with this, because about 100 years later, he will encounter the next Ababa palindrome date: 21211212, that is, December 12, 2121. It is not "once in a thousand years", but "twice in a thousand years" at most.

Given an 8-digit date, please calculate the next palindrome date and the next Ababa palindrome date after the date.

Enter description

The input contains an eight digit integer N representing the date.

For all evaluation cases, 10000101 ≤ N ≤ 89991231, ensure that N is an 8-digit representation of a legal date.

Output description

Output two lines with one eight digit in each line. The first line represents the next palindrome date, and the second line represents the next Ababa palindrome date.

Sample input and output

Examples

input

20200202

output

20211202
21211212

Operational limits

• Maximum running time: 1s
• Maximum operating memory: 256M

2, Train of thought

For the 8-digit processing of this problem, I use the way of string instead of becoming an integer variable. I feel that if integer variables are used to accumulate, it will cause timeout.

For 8 digits, it can be divided into the first four years and the last four dates. Accumulate from the year, and then judge whether the month and date are in line with the situation. In this way, the time complexity of the cycle is absolutely within the allowable range of the maximum running time, which shall not exceed 10000 times at most. For each accumulated year, construct the palindrome string in reverse, and then judge whether the month and date are legal, so as to find the next palindrome date and abbaba type.

The general idea is basically like this. In addition, there are several points to pay attention to:

• For the input year, judge it first and then add it up. For example, if you enter 10100000, the next palindrome string is 10100101, which happens to be abbaba type. Be careful not to skip the input year
• In the correspondence between month and date, the number of days in February corresponds to leap year (29 days), non leap year (28 days), 30 day month and 31 day month

Pay attention to the above two points, and basically there will be no problem!

3, Specific code

#include<bits/stdc++.h>
using namespace std;
bool check(string s) //Check whether the month and date are legal
{
    int yue=0;
    int ri=0;
    yue=(s[4]-'0')*10;
    yue+=(s[5]-'0');
    ri=(s[6]-'0')*10;
    ri+=(s[7]-'0');
    if(yue<=0||yue>12)  
    {
        return false;
    }
    //Legal month, inspection date
    if(ri<=0||ri>31)
    {
        return false;
    }
    if(yue==4||yue==6||yue==9||yue==11)  //31 day month
    {
        if(ri>=31)
        {
            return false;
        }
    }
    else if(yue==2)  //Special in February
    {
        int year=0;
        year+=(s[0]-'0')*1000;
        year+=(s[1]-'0')*100;
        year+=(s[2]-'0')*10;
        year+=(s[3]-'0');
        if((year%4==0&&year%100!=0)||year%400==0)  //leap year
        {
            if(ri>29)
            {
                return false;
            }
        }
        else  //Non leap year
        {
            if(ri>28)
            {
                return false;
            }
        }
    }
    return true;
}

bool check_AB(string s)
{
    for(int i=0;i<8;i++)
    {
        if(s[i]!=s[7-i])
        {
            return false;
        }
    }
    if(s[0]==s[2]&&s[1]==s[3]&&s[0]!=s[1])  //Check ABAB type
    {
        return true;
    }
    return false;
}
string add(string s) //Search down
{
    int num=0;
    num+=(s[0]-'0')*1000;
    num+=(s[1]-'0')*100;
    num+=(s[2]-'0')*10;
    num+=(s[3]-'0');
    num++;
    string temp2=to_string(num);
    temp2+=temp2[3];
    temp2+=temp2[2];
    temp2+=temp2[1];
    temp2+=temp2[0];
    return temp2;
}
int main()
{
    string s;
    cin>>s;
    string temp=s;
    int flag=0;
    string ans1;
    string ans2;
    int poi=0; //Check whether the next reply date has been found
    int flag2=0;
    temp[4]=temp[3];
    temp[5]=temp[2];
    temp[6]=temp[1];
    temp[7]=temp[0];
    if(temp>s&&check(temp))  //First check whether there is a palindrome string in the entered year
    {
        ans1=temp;
        poi=1;
        if(temp[0]==temp[2]&&temp[1]==temp[3]&&temp[0]!=temp[1]) //Check ABAB type
        {
            ans2=temp;
            cout<<ans1<<endl;
            cout<<ans2<<endl;
            return 0;
        }
    }
    else
    {
        temp=s;
    }
    while(1) //Find the next palindrome date and abbaba date. The addition rule is to add according to the year
    {
        temp=add(temp);  //Realize temp self increment
        if(check(temp))
        {
            if(poi==0)
            {
                ans1=temp;  //The date is legal. It is the date of the next reply
                poi=1;
            }
            if(check_AB(temp)) //Check whether it is abbaba type date
            {
                ans2=temp;
                break;
            }
        }
    }
    cout<<ans1<<endl;
    cout<<ans2<<endl;
    return 0;
}