題目描述
若一個數（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數，
例如：給定一個十進制數 5656，將 5656 加 6565（即把 5656 從右向左讀），得到 121121 是一個回文數，
又如：對于十進制數 8787：
STEP1：87+78=16587+78=165
STEP2：165+561=726165+561=726
STEP3：726+627=1353726+627=1353
STEP4：1353+3531=48841353+3531=4884
在這里的一步是指進行了一次 NN 進制的加法，上例最少用了 44 步得到回文數 48844884，
寫一個程式，給定一個 NN（2 \le N \le 102≤N≤10 或 N=16N=16）進制數 MM（100100 位之內），求最少經過幾步可以得到回文數，如果在 3030 步以內（包含 3030 步）不可能得到回文數，則輸出 Impossible!，
輸入格式
兩行，分別是 NN，MM，
輸出格式
如果能在 3030 步以內得到回文數，輸出格式形如 STEP=ans，其中 ansans 為最少得到回文數的步數，
否則輸出 Impossible!，
輸入輸出樣例
輸入 #1復制
10
87
輸出 #1復制
STEP=4
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char c[100001];
int t,k,lena,leng=1,a[100001],b[100001],g[100001],n;
void pd();
void jf()
{
int x=0;leng=1;g[1]=0;
while(leng<=lena+1)
{g[leng]=a[leng]+a[lena+1-leng]+x;
x=g[leng]/n;
g[leng]%=n;
leng++;
}g[leng+1]=x;t++;//cout<<t;
while(g[leng]==0&&leng>1)
{leng--;
}
pd();
}
void pd()
{
int o=0;
for(int i=1;i<=leng/2;i++)
{if(g[i]==g[leng+1-i])
{o++;if(o==leng/2)
{cout<<"STEP="<<t;k++;}
}
else
{for(int i=1;i<=leng;i++)
a[i]=g[i];
lena=leng;
}
}
}
int main()
{scanf("%d",&n);
scanf("%s",c);
lena=strlen(c);
for(int i=0;i<=lena-1;i++)
{if(c[i]>57)a[lena-i]=10+c[i]-17-48;
else a[lena-i]=c[i]-48;
}
while(t<=30&&k==0)
{jf();
}
if(k==0)cout<<"Impossible!";
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/155879.html
標籤：其他
上一篇：P1014 Cantor表
下一篇：P1016 旅行家的預算