1309:【例1.6】回文数(Noip1999)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 24068 通过数: 10153
【题目描述】
若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其称之为回文数。例如:给定一个 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.求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible” 。
【输入】
第1行,给定一个N(2<N≤10或N=16)表示进制;
第2行,一个N进制数M。
【输出】
最少几步。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible”。
【输入样例】
9 87
【输出样例】
6
#include<bits/stdc++.h> using namespace std; int n,w,a[101]={},b[101]={};//初始化数组 bool panduan(int a[]){//判断一个数是不是回文数 for(int i=1;i<=w;i++){ if(a[i]!=a[w-i+1]){//循环判断有一个不一样就不是回文数 return false; } } return true; } int main(){ string s; cin>>n>>s; w=s.length();//存入位数 for(int i=1;i<=w;i++){ if(s[w-i]>='0'&&s[w-i]<='9'){ a[i]=s[w-i]-'0'; }else{ a[i]=s[w-i]-'A'+10;//表示10进制以上的数(如16进制) 存入 //return 0; } } int i=0; while(i<=30){ if(panduan(a)){ cout<<i;//输出步数 return 0; } for(int j=1;j<=w;j++){ b[j]=a[w-j+1];//反序存入另一个数组 } for(int j=1;j<=w;j++){ a[j]+=b[j];//相加 } for(int j=1;j<=w;j++){//根据进制进一 a[j+1]+=a[j]/n; a[j]%=n; } if(a[w+1]>0){//改为其他进制后 位数有所变化 w++; } i++; } cout<<"Impossible"; return 0; }