若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。 又如：对于10进制数87：
STEP1：$$87+78 = 165$$
STEP2：$$165+561 = 726$$
STEP3：$$726+627 = 1353$$
STEP4：$$1353+3531 = 4884$$
在这里的一步是指进行了一次$N=10$进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个$N(2 \le N \le 16)$进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
输入
共两行
第一行为进制数N,$2 \le N \le 16$
第二行为N进制数M, $0 \le M \le 2^{63}-1$
输出
共一行，为“STEP=经过的步数”或“Impossible!”
样例输入
样例输出
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
int len;
char a[110],b[110];
int n;
int check(){
for(int i=0 ; i<len ; i++) if(a[i] != a[len-i-1]) return 0;
return 1;
}
void add(){
for(int i=0 ; i<len ; i++) b[len-i-1] = a[i];
len += 2;
for(int i=0 ; i<len ; i++){
a[i] += b[i];
if(a[i] >= n){
a[i+1]++;
a[i]-=n;
}
}
while(!a[len-1]) len--;
}
int main(){
scanf("%d",&n);
int step = 0;
cin >> a;
len = strlen(a);
for(int i=0 ; i<len ; i++){
if(a[i] >= '0' && a[i] <= '9') a[i] -= '0';
else a[i] = a[i] - 'A' + 10;
}
while(!check()){
step++;
if(step > 30) break;
add();
}
if(step <= 30) printf("STEP=%d",step);
else printf("Impossible!");
return 0;
}
|
