P1015 [NOIP1999 普及组] 回文数

题目描述

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

例如：给定一个十进制数 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!。

输入样例

10 87

输出样例

STEP=4

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<string.h>

using namespace std;

int n,a[10010],b[10010],ans,l;

void zhuanhuan()//输入加转换

{

	string s;

	cin>>n>>s;

	memset(a,0,sizeof(a));

	l=s.length();

	for(int i=1;i<=l;i++)

	{

		if(s[l-i]>='0'&&s[l-i]<='9')a[i]=s[l-i]-'0';

		else a[i]=s[l-i]-'A'+10;

	}

}

bool check()//判断回文

{

	for(int i=1;i<=l;i++)

	{

		if(a[i]!=a[l-i+1])return false;

	}

	return true;

}

void gaojing()//进位比较特殊

{

	for(int i=1;i<=l;i++)b[i]=a[l-i+1];

	for(int i=1;i<=l;i++)a[i]+=b[i];

	for(int i=1;i<=l;i++)

	{

		a[i+1]+=a[i]/n;

		a[i]%=n;

	}

	if(a[l+1]>0)l++;

}

int main()

{

	zhuanhuan();

	if(check())

	{

		printf("STEP=0\n");

		return 0;

	}

	for(int ans=1;ans<=30;++ans)

	{

		gaojing();

		if(check())

		{

			printf("STEP=%d\n",ans);

			return 0;

		}

	}

	printf("Impossible");

	return 0;

}