P1015 [NOIP1999 普及组] 回文数

发布时间:2023年12月23日

[NOIP1999 普及组] 回文数

题目描述

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

例如:给定一个十进制数 56 56 56,将 56 56 56 65 65 65(即把 56 56 56 从右向左读),得到 121 121 121 是一个回文数。

又如:对于十进制数 87 87 87

STEP1: 87 + 78 = 165 87+78=165 87+78=165
STEP2: 165 + 561 = 726 165+561=726 165+561=726
STEP3: 726 + 627 = 1353 726+627=1353 726+627=1353
STEP4: 1353 + 3531 = 4884 1353+3531=4884 1353+3531=4884

在这里的一步是指进行了一次 N N N 进制的加法,上例最少用了 4 4 4 步得到回文数 4884 4884 4884

写一个程序,给定一个 N N N 2 ≤ N ≤ 10 2 \le N \le 10 2N10 N = 16 N=16 N=16)进制数 M M M 100 100 100 位之内),求最少经过几步可以得到回文数。如果在 30 30 30 步以内(包含 30 30 30 步)不可能得到回文数,则输出 Impossible!

输入格式

两行,分别是 N N N M M M

输出格式

如果能在 30 30 30 步以内得到回文数,输出格式形如 STEP=ans,其中 ans \text{ans} ans 为最少得到回文数的步数。

否则输出 Impossible!

样例 #1

样例输入 #1

10
87

样例输出 #1

STEP=4

解法

#include <bits/stdc++.h>
using namespace std;
int a[50000],b[50000];
int l,n,s;
string m;
bool huiwen ()
{
	for (int i=0;i<l/2;i++)
		if (a[i]!=a[l-i-1])
			return 0;
	return 1;
}
void caozuo()
{
	if (huiwen()) return;
	if (s==30)
	{
		cout <<"Impossible!";
		exit (0);
	}
	s++;
	for (int i=0;i<l;i++)
	{
		b[i]+=a[i]+a[l-i-1];
		b[i+1]=b[i]/n;
		b[i]%=n;
	}
	if (b[l])
		l++;
	for (int i=0;i<l;i++)
		a[i]=b[i];
	memset (b,0,sizeof(b));
	caozuo();
}
int main()
{
	cin >>n >>m; l=m.size();
	for (int i=0;i<l;i++)
		if (m[l-i-1]>47 && m[l-i-1]<58)
			a[i]=m[l-i-1]-48;
		else
			a[i]=m[l-i-1]-55;
	caozuo();
	cout <<"STEP=" <<s;
	return 0;
}
文章来源:https://blog.csdn.net/DUXS11/article/details/135164948
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。