描述
若一个数 (首位不为零) 从左向右读与从右向左读都一样, 我们就将其称之为回文数
例如: 给定一个 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<=10 或 N=16)进制数 M, 其中 16 进制数字为 0-9 与 A-F, 求最少经过几步可以得到回文数如果在 30 步以内 (包含 30 步) 不可能得到回文数, 则输出 Impossible!
格式
输入格式
共两行
第一行为进制数 N(2<=N<=10 或 N=16)
第二行为 N 进制数 M(0<=M<=maxlongint)
输出格式
共一行
第一行为 STEP = 加上经过的步数或 Impossible!
样例 1
样例输入 1
9
87
Copy
样例输出 1
STEP=6
Copy
限制
各个测试点 1s
来源
NOIP1999 提高组第 2 题
- #include <iostream>
- #include <string.h>
- #include <math.h>
- #include <cstdio>
- #include <stdlib.h>
- using namespace std;
- int main()
- {
- int n;//n 进制数
- char m[40];
- int m_n[40]={0},m_rev[40]={0};
- cin>>n>>m;
- int l=strlen(m);
- for(int i=l-1;i>=0;i--)
- {
- if(m[i]<=9&&m[i]>=0)
- m_n[i]=m[i]-0;
- else
- m_n[i]=m[i]-A+10;
- }
- int flag=1;
- for(int i=0;i<=l/2;i++)
- if(m_n[i]!=m_n[l-i-1])
- {
- flag=0;
- break;
- }
- if(flag==1)
- {
- cout<<"STEP=0"<<endl;
- return 0;
- }
- int step=0;
- while(1)
- {
- for(int i=l-1;i>=0;i--)
- m_rev[i]=m_n[l-i-1];
- int l0=l;
- for(int i=0;i<=l0-1;i++)
- {
- m_n[i]+=m_rev[i];
- while(m_n[i]>=n)
- {
- m_n[i]-=n;
- m_n[i+1]++;
- if(i==l-1)
- l++;
- }
- }
- step++;
- int flag=1;
- for(int i=0;i<=l/2;i++)
- if(m_n[i]!=m_n[l-i-1])
- {
- flag=0;
- break;
- }
- if(flag==0&&step>30)
- {
- cout<<"Impossible!"<<endl;
- break;
- }
- else if(flag==1)
- {
- printf("STEP=%d\n",step);
- break;
- }
- }
- return 0;
- }
- View Code
因为没加 = 而 wa 巨多次
因为 impossible 的 I 没有大写而 wa
题是水题 但细心才能对啊...
来源: http://www.bubuko.com/infodetail-2515844.html