P1015 回文数

admin

https://www.luogu.org/problemnew/show/P1015

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

例如：给定一个十进制数 5656 ，将 5656 加 6565 （即把 5656 从右向左读），得到 121121 是一个回文数。

又如：对于十进制数 8787 ：

STEP1： 8787 + 7878 = 165165
STEP2： 165165 + 561561 = 726726
STEP3： 726726 + 627627 = 13531353
STEP4： 13531353 + 35313531 = 48844884

在这里的一步是指进行了一次 NN 进制的加法，上例最少用了 44 步得到回文数 48844884 。

写一个程序，给定一个 NN ( 2 \le N \le 10,N=162≤N≤10,N=16 )进制数 MM ( 100100 位之内)，求最少经过几步可以得到回文数。如果在 3030 步以内（包含 3030 步）不可能得到回文数，则输出Impossible!

输入输出格式
输入格式：
两行，分别是 NN ， MM 。

输出格式：
STEP=ans

输入输出样例
输入样例#1：
10
87
输出样例#1：
STEP=4

admin

1. #include<iostream>
   
2. using namespace std;
   
3. int N;
   
4. string M;
   
5. string  rever(string s)
   
6. {
   
7.     int i,l=s.size();
   
8.     string t="";
   
9.     for (i=0; i<=l-1; i++) t=s[i]+t;
   
10.     return t;
    
11. }
    
12. string add(string s,string t)
    
13. {
    
14.     int x,j,i,l1=s.size(),l2=t.size();
    
15.     int x1,x2;
    
16.     if (l1<l2)
    
17.     {
    
18.         swap(s,t);
    
19.         swap(l1,l2);
    
20.     }
    
21.     for (i=1; i<=l1-l2; i++) t='0'+t;
    
22.     string ss="";j=0;
    
23.     for (i=l1-1; i>=0; i--)
    
24.     {
    
25. 
    
26.         if (s[i]<='9')x1=s[i]-'0';else x1=s[i]-'A'+10;
    
27.         if (t[i]<='9')x2=t[i]-'0';else x2=t[i]-'A'+10;
    
28.         x=x1+x2+j;
    
29.         if (x>=N)
    
30.         {
    
31.             x=x-N;
    
32.             j=1;
    
33.         }
    
34.         else j=0;
    
35.         if (x<=9)ss=char(x+'0')+ss;
    
36.         else ss=char(x-10+'A')+ss;
    
37.     }
    
38.     if (j==1) ss='1'+ss;
    
39.     return ss;
    
40. }
    
41. string trim(string s)
    
42. {
    
43.     string t=s;
    
44.     while (t[0]=='0' && t.size()>1) t.erase(0,1);
    
45.     return t;
    
46. }
    
47. int main()
    
48. {
    
49.     int i;
    
50.     cin>>N;
    
51.     cin>>M;
    
52.     for(i=0; i<=30; i++)
    
53.     {
    
54.     ///cout<<M<<endl;
    
55.         string sm=rever(M);
    
56.     /// cout<<sm<<endl;
    
57.         if (M==sm) break;
    
58.         else
    
59.         {
    
60.             M=add(M,sm);
    
61.             M=trim(M);
    
62.         }
    
63.     }
    
64.     if (i<=30) cout<<"STEP="<<i;
    
65.     else cout<<"Impossible!";
    
66.     return 0;
    
67. 
    
68. }

复制代码