回文数
链接:https://ac.nowcoder.com/acm/contest/59758/I?&headNav=acm
来源:牛客网
若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。
例如:给定一个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(100位之内),求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible!”
进制N>10时,使用大写’A’字母表示10,’B’表示11,…,’E’表示15
输入描述:
两行,分别为N,M
输出描述:
STEP=ans
示例1
输入
复制
9
87
输出
复制
STEP=6
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[1100],b[1100];
int n;
void init(int a[])
{
string s;
cin>>s;
a[0]=s.size();
for(int i=1;i<=a[0];i++)//注意进制还有10以上的
{
if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')
a[i]=s[a[0]-i]-'0';
else
a[i]=s[a[0]-i]-'A'+10;
}
}
void print(int a[])
{
for(int i=a[0];i>=1;i--)
{
cout<<a[i];
}
}
void hw(int a[],int b[])
{
for(int i=1;i<=a[0];i++)
{
b[i]=a[a[0]-i+1];
}
}
void jia(int a[],int b[])
{
int x=0;
for(int i=1;i<=a[0];i++)
{
a[i]+=b[i]+x;
if(a[i]>=n)
{
x=a[i]/n;
a[i]=a[i]%n;
if(i==a[0])
a[0]++;
}
else
x=0;
}
}
bool pd(int a[])
{
for(int i=1;i<=a[0]/2;i++)
{
if(a[i]!=a[a[0]-i+1])
return false;
}
return true;
}
int main()
{
cin>>n;
init(a);
for(int k=1;k<=30;k++)
{
hw(a,b);
jia(a,b);
bool ok;
ok=pd(a);
if(ok==true)
{
cout<<"STEP="<<k;
return 0;
}
}
cout<<"Impossible!";
return 0;
}
版权声明:本文为weixin_74827496原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。