17年秋季第一题 PAT甲级 1136 A Delayed Palindrome (20分)

港控/mmm° 2023-07-04 04:42 9阅读 0赞

1136 A Delayed Palindrome (20分)

Consider a positive integer N written in standard notation with k+1 digits ai as ak⋯a1a0 with 0≤ai<10 for all i and ak>0. Then N is **palindromic** if and only if ai=ak−i for all i. Zero is written 0 and is also palindromic by definition.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. Such number is called **a delayed palindrome**. (Quoted from [https://en.wikipedia.org/wiki/Palindromic\_number][https_en.wikipedia.org_wiki_Palindromic_number] )

Given any positive integer, you are supposed to find its paired palindromic number.

### Input Specification: ###

Each input file contains one test case which gives a positive integer no more than 1000 digits.

### Output Specification: ###

For each test case, print line by line the process of finding the palindromic number. The format of each line is the following:

A + B = C

where `A` is the original number, `B` is the reversed `A`, and `C` is their sum. `A` starts being the input number, and this process ends until `C` becomes a palindromic number -- in this case we print in the last line `C is a palindromic number.`; or if a palindromic number cannot be found in 10 iterations, print `Not found in 10 iterations.` instead.

### Sample Input 1: ###

97152

### Sample Output 1: ###

97152 + 25179 = 122331
    122331 + 133221 = 255552
    255552 is a palindromic number.

### Sample Input 2: ###

196

### Sample Output 2: ###

196 + 691 = 887
    887 + 788 = 1675
    1675 + 5761 = 7436
    7436 + 6347 = 13783
    13783 + 38731 = 52514
    52514 + 41525 = 94039
    94039 + 93049 = 187088
    187088 + 880781 = 1067869
    1067869 + 9687601 = 10755470
    10755470 + 07455701 = 18211171
    Not found in 10 iterations.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70][]

#include<iostream>
    #include<vector>
    #include<set>
    #include<map>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int main(){
        string s,r,k,t;
        long long p;
        cin>>s;
        r=s;
        reverse(r.begin(), r.end());
        if(r==s){
            cout<<s<<" is a palindromic number.";
            return 0;
        }
        bool f=false;
        for(int i=0;i<10;i++){
            k="";
            int carry=0,x;
            for(int i=0;i<s.size();i++){
                x=(s[i]-'0')+(r[i]-'0');
                k+=to_string((x%10+carry)%10);
                carry=x/10+(x%10+carry)/10;
            }
            if(carry!=0)k+=to_string(carry);
            cout<<s<<" + "<<r<<" = ";
            r=k;
            s=r;
            reverse(s.begin(), s.end());
            cout<<s<<endl;
            if(s==r){
                cout<<k<<" is a palindromic number.";
                f=true;
                break;
            }
        }
        if(!f){
            cout<<"Not found in 10 iterations.";
        }
        return 0;
    }

[https_en.wikipedia.org_wiki_Palindromic_number]: https://en.wikipedia.org/wiki/Palindromic_number
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207230719350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw==,size_16,color_FFFFFF,t_70