[NOIP1999 普及组] 回文数

题目描述

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

例如：给定一个十进制数 \(56\)，将 \(56\) 加 \(65\)（即把 \(56\) 从右向左读），得到 \(121\) 是一个回文数。

又如：对于十进制数 \(87\)：

STEP1：\(87+78=165\)
STEP2：\(165+561=726\)
STEP3：\(726+627=1353\)
STEP4：\(1353+3531=4884\)

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

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

输入格式

两行，分别是 \(N\)，\(M\)。

输出格式

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

否则输出 Impossible!。

样例 #1

样例输入 #1

10
87

样例输出 #1

STEP=4

思路

首先要考虑是否为回文数，所谓回文数就是将自己倒转和原来的相同。那么有一个函数reverse()完美符合我们的需求，它的作用就是将一个字符串倒转过来。那么我们可以写判断是否为回文数的func：

bool isdrome(string a){
    string b=a;
    reverse(b.begin(),b.end());
    return a==b;
}

再回看题目，它需要将自己与自己的回文数加起来，由于我们处理的是字符串，因此我们需要把它转换成整型再进行相加，同时我们也要考虑相加后的进位问题：

string add(string a){
    string b=a;
    reverse(b.begin(),b.end());
    int x,y,t=0,len=a.size();
    for(int i=len-1;i>=0;i--){
        x=(a[i]>='A')?(a[i]-'A'+10):(a[i]-'0');
        y=(b[i]>='A')?(b[i]-'A'+10):(b[i]-'0');
        x+=y+t;//此时是将x+y然后处理进位
        t=(x>=n)?1:0;//进位判断
        if(t==1){
            x-=n;
        }
        a[i]=(x>9)?(x+'A'-10):(x+'0');//复原
    }
    if(t==1){
        a="1"+a;
    }
    return a;
}

完整程序

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;
int n;

string add(string a){
	string b=a;
	reverse(b.begin(),b.end());
	int x,y,t=0,len=a.size();
	for(int i=len-1;i>=0;i--){
		x=(a[i]>='A')?(a[i]-'A'+10):(a[i]-'0');
		y=(b[i]>='A')?(b[i]-'A'+10):(b[i]-'0');
		x+=y+t;
		t=(x>=n)?1:0;
		if(t==1)
			x-=n;
		a[i]=(x>9)?(x+'A'-10):(x+'0');//复原 
	}
	if(t==1)
		a="1"+a;
	return a;
}

bool isdrome(string a){
	string b=a;
	reverse(b.begin(),b.end());
	return a==b;
}

int main(){
	int i;
	string m;
	cin>>n>>m;
	for(i=0;i<=30&&!isdrome(m);i++)
		m=add(m);
	if(i>30)
		cout<<"Impossible!"<<endl; 
	else
		cout<<"STEP="<<i<<endl;
	return 0;
}