题目描述

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


例如：给定一个10进制数56，将56加56（即把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，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”

输入描述:

两行，分别是N，M。

输出描述:

STEP=ans(ans表示答案)

示例1

输入
9
87

输出

STEP=6

题解

本题在回文串的基础上增加了进制转换，没有什么高深的算法，模拟。
1、    回文判断
        stl里提供的string类容器可以很好的判断两个字符串的大小关系，那么将串A复制到串B，再将串B头尾反转判断两串大小：若相等则为回文串。
2、    进制转换
        周围同学都是严格的使用A~F表示10进制表示不了的数，在此题中也不断进行着进制转换的操作，这样很繁琐，干脆使用数值对应的ASCII码代替A~F，在对应进制上进行操作。 

#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<list>
#include<vector>
#include<queue>
#include<deque>
#include<set>
#include<functional>
#include<time.h>
#include<fstream>
#include<algorithm>
#define pi 3.14159265358979323846264338327950288419716939937510582097494
using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define _for(i, a, b) for(ll i = (a); i < (b); ++i)
#define _rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define _re_for(i, a, b) for(ll i = (a); i > (b); --i)
#define _re_rep(i, a, b) for(ll i = (a); i >= (b); --i)

const int INF1 = 0x3f3f3f3f;
const int INF0 = 0xc0c0c0c0;
const int MAX = 100010;

string ad(string &a, string &b, int n) {
	int r = 0;
	_for(i, 0, a.size()) {
		int sum = a[i] + b[i] - 48 - 48 + r;// 使用ASCII吗计算
		a[i] = sum % n + 48;// n进制下取余
		r = sum / n;
	}
	char c = r + 48;
	if (r + 48 != '0') a += c;// 末尾余位
	return a;
}

string a, b;
char flag[200];

int main() {
	_rep(i, 0, 9) flag['0' + i] = i + 48;
	_rep(i, 'A', 'Z') flag[i] = '9' + (i - 'A' + 1);// 构建码值表
	int n;
	cin >> n >> a;
	_for(i, 0, a.size()) a[i] = flag[a[i]];// 以ASCII码替换原码值
	b = a;
//	while (b.size() && b.back() == '0') b.pop_back();
	reverse(b.begin(), b.end());// 字符串翻转

	int cnt = 0;
	while (cnt <= 30) {
		if (a == b) {
			cout << "STEP="<< cnt;
			return 0; 
		}
		cnt ++;
		a = ad(a, b, n);// 得到两串相加的结果
		b = a;
//		while (b.size() && b.back() == '0') b.pop_back();
		reverse(b.begin(), b.end());
	}
	cout << "Impossible!";
	return 0;
}