526互联

回文数

发布时间 2023-09-19 14:37:26作者: freedragon

 

 

 

回文数
 

描述

 

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：对整数56，将56加65（即把56从右向左读），得到121是一个回文数。

又如：对于整数87：

STEP1：87+78= 165

STEP2：165+561= 726

STEP3：726+627= 1353

STEP4：1353+3531= 4884

在这里的一步是指进行了一次加法，上例中最少用了4步得到回文数4884。

写一个程序，给定一个数N，求最少经过几步可以得到回文数。如果在30步以内（包含30步）没有得到回文数，则输出“Impossible”

 

输入

 

一行。输入一个整数N，位数少于50位，用于进行加法求回文数。

 

输出

 

一行。如果能得到回文数，输出最少的步数M，如果30步以内不可能得到，则输出“Impossible”

 

输入样例 1 

87

输出样例 1

4

输入样例 2 

23445456443988173748455

输出样例 2

Impossible

 

 



 

#include<iostream>
#include<cstring>
using namespace std;
char a1[100000];    
int a[100000], b[100000];
bool huiwen (int a[], int len) {
    for (int i = 0;i <= len/2;i ++) {        
        if (a[i] != a[len - i -1]) {    
            return 0;
        }
    }
    return 1;
}
int main() {
    cin >> a1;
    int len = strlen(a1);
    for(int i = 0; i < len; i++) {
        a[i] = a1[i] - 48;
    }
    int count = 0;
    while (huiwen(a,len)==0 && count <= 30) {
        count ++;                                
        int x = 0;                            
        for (int i = 0;i < len;i ++) {
            b[i] = a[i] + a[len-1-i] + x;    
            x = b[i] / 10;
            b[i] = b[i] % 10;    
        }
        if (x != 0) {
            b[len] = x;
            len ++;
        }
        for (int i = len-1;i >= 0;i --) {
            a[len-i-1] = b[i];
        }
    }
    if (count <= 30) {
        cout << count << endl;
    } else {
        cout << "Impossible" << endl;
    }
    return 0;
}