題目描述

若一個數（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數。

例如：給定一個十進制數?5656，將?5656?加?6565（即把?5656?從右向左讀），得到?121121?是一個回文數。

又如：對于十進制數?8787：

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（100?位之內），求最少經過幾步可以得到回文數。如果在?30?步以內（包含?30?步）不可能得到回文數，則輸出?Impossible!。

輸入格式

兩行，分別是?N，M。

輸出格式

如果能在?30?步以內得到回文數，輸出格式形如?STEP=ans，其中?ans為最少得到回文數的步數。

否則輸出?Impossible!。

輸入輸出樣例

輸入 #1

10
87

輸出 #1

STEP=4

這題用add函數負責將當前數與它的反向讀取數相加，并更新到 c[] 數組中，同時處理進位情況和去除高位前導零。用pd函數判斷當前數是否為回文數。用main

將字符轉換為對應的數值存入 c [ ]?

#include <bits/stdc++.h>
using namespace std;
int n, a[305], len;
char c[305], d[305];void add() {for (int i = 0; i < len; i++)d[len - i - 1] = c[i];len+=2;for (int i = 0; i < len; i++) {c[i] += d[i];if (c[i] >= n) {c[i + 1]++;c[i] -= n;}}while (!c[len - 1])len--;
}
bool pd() {for (int i = 0; i < len; i++) {if (c[i] != c[len - 1 - i]) {return false;}}return true;
}int main() {cin >> n >> c;len= strlen(c);for (int i = 0; i < len; i++) {if (c[i] >= '0' && c[i] <= '9')c[i] -= '0';elsec[i] = c[i] - 'A' + 10;}int step = 0;while (!pd()) {step++;if (step > 30)break;add();}if (step <= 30)cout << "STEP=" << step;elsecout << "Impossible!";return 0;
}