OJ 1020 minimum palindromes

describe

Palindrome number is the same number from front to back and from back to front .
Here is a positive integer N, Please find Bi N The largest and smallest palindrome number P.

Input

Input contains multiple sets of test data .
Enter a positive integer for each group N,N No more than 10000 position , also N No leading 0.

Output

For each group of input , Output ratio N The largest and smallest palindrome number P.

sample input 1

44
3
175

sample output 1

55
4
181

Answer key

First , Title and statement N No more than 1000 Bitwise is N<=10^1000, This normal number must not be stored , Even if it's long long It is impossible to save such a large number , At the same time, since the number is so large, it is unrealistic to find the first palindrome number that is larger than him if it is convenient , After all, this number is too large, and the time complexity of loop traversal is too high , So what data structure can store such a huge astronomical number without exceeding the time limit ？ It must be string For strings 1000 The length of is not long , At the same time, the string can directly modify the data of each bit . This means that the calculation can be completed without traversal .

Now let's look at the rules ：

Palindrome , As the name suggests, it's the same from front to back and from back to front . Then the law of palindromes comes out, since they are all the same , We only need to maintain half section , The other half is reversed, so , We just need to take out the first half , For palindromes with even digits, the first half of the palindrome is taken directly , Odd palindromes take the first half plus the middle , Then directly perform palindrome operation to combine the first half and the second half into palindromes , Then compare it with the previous number. If it is greater than it , There is no doubt that he is the smallest ratio N Large palindromes , Otherwise, take out the first half +1 Then retrieve the palindrome , This number must be the smallest ratio N Large palindromes

Code ：

#include <bits/stdc++.h>

using namespace std;
string a;

string mult(string x)
{

    x[x.length()-1]++;
    for(int i=x.length()-1; i>=0; i--)
    {
        if(x[i]>'9')
        {
            if(i==0)
            {
                x[i]-=10;
                x.insert(0,1,'1');
            }

            else
            {
                x[i]-=10;
                x[i-1]++;
            }
        }
    }
    return x;
}

int main()
{
    while(cin>>a)
    {
        if(a.size()==1)
        {
            if(a[a.length()-1]<'9')
            {
                a[a.length()-1]++;
                cout<<a<<endl;
            }
            else
            {
                cout<<"11"<<endl;
            }
        }
        else
        {
            string b;
            int len;
            if(a.length()%2==0)
                len=a.length()/2;
            else
                len=a.length()/2+1;
            for(int i=0; i<len; i++)
            {
                b+=a[i];
            }
            //cout<<b<<endl;
            string c=b;


            if(a.length()%2==0)
            {
                for(int i=b.length()-1; i>=0; i--)
                    c+=c[i];
            }
            else
            {
                for(int i=b.length()-2; i>=0; i--)
                    c+=c[i];
            }
            if(c>a)
                cout<<c<<endl;
            else
            {
                c=mult(b);
                if(c.length()==b.length())
                {
                    if(a.length()%2==0)
                    {
                        for(int i=b.length()-1; i>=0; i--)
                            c+=c[i];
                    }
                    else
                    {
                        for(int i=b.length()-2; i>=0; i--)
                            c+=c[i];
                    }
                    cout<<c<<endl;
                }
                else{
                    int lenc=c.length();
                   // cout<<c<<endl;
                    if(a.length()%2!=0)
                    {
                        for(int i=lenc-3; i>=0; i--)
                            c+=c[i];
                    }
                    else
                    {
                        for(int i=lenc-2; i>=0; i--)
                            c+=c[i];
                    }
                    cout<<c<<endl;
                }

            }
        }
    }
    return 0;
}