NOIP1999回文数
题目描述
若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。
例如:给定一个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进制的加法,上例最少用了4步得到回文数4884。
写一个程序,给定一个N(2<=N<=16)进制数M,求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible!”
输入
仅有两行,包含两个整数N和M。
输出
得到回文的最少经过步数为K,则输出“STEP=K”,而30步以内(包含30步)不可能得到回文,输出“Impossible!”。
样例输入
1 2 |
10 87 |
样例输出
1 |
STEP=4 |
代码
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstring> #include<string> #include<algorithm> using namespace std; struct bign { int len,num[1001]; bign() { len=0; memset(num,0,sizeof(num)); } }; int getnum(char ch) { if(ch>='0'&&ch<='9')return (int)ch-'0'; if(ch>='A'&&ch<='Z')return (int)ch-'A'+10; } bign pplus(bign a,bign b,int k) { int j=0;bign c; for(int i=0;j||i<max(a.len,b.len);i++) { if(i<a.len)j+=a.num[i]; if(i<b.len)j+=b.num[i]; c.num[c.len++]=j%k; j/=k; } return c; } bign reverse(bign a) { int i=a.len-1,j; bign b; for(j=0;j<=a.len-1;j++) if(a.num[j]!=0)break; for(i;i>=j;i--) b.num[b.len++]=a.num[i]; return b; } bool dengyu(bign a,bign b) { if(a.len!=b.len)return false; for(int i=0;i<=a.len-1;i++) if(a.num[i]!=b.num[i])return false; return true; } string m; int n,step=0; bign sum; int main() { cin>>n>>m; for(int i=m.length()-1;i>=0;i--) sum.num[sum.len++]=getnum(m[i]); while(!dengyu(sum,reverse(sum))) { sum=pplus(sum,reverse(sum),n); if(++step>=30) { cout<<"Impossible!"<<endl; return 0; } } cout<<"STEP="<<step<<endl; return 0; } |
Subscribe