信息学奥赛问题：回文数的问题

Question

回文数
时间限制：1秒 内存限制：128M
题目描述
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个 10进制数 56，将 56加 65（即把56从右向左读），得到 121是一个回文数。 写一个程序，给定一个N（2＜N＜＝10或N=16）进制数 M．求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!” 。

输入描述
给定一个N（2＜N＜＝10或N=16）进制数M。

输出描述
最少几步。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”。

样例
输入
9 87
输出
6
用c++，python解出。

Answer 1

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool isPalindrome(string num) {
    int n = num.size();
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        if (num[i] != num[j]) {
            return false;
        }
    }
    return true;
}

string convertToBase(int num, int base) {
    string result;
    while (num > 0) {
        int digit = num % base;
        result += to_string(digit);
        num /= base;
    }
    reverse(result.begin(), result.end());
    return result;
}

int stepsToPalindrome(int base, string num) {
    int steps = 0;
    while (!isPalindrome(num)) {
        int n = stoi(num, nullptr, base);
        reverse(num.begin(), num.end());
        int reverse_n = stoi(num, nullptr, base);
        int sum = n + reverse_n;
        num = convertToBase(sum, base);
        steps++;
        if (steps > 30) {
            return -1;  // 超过30步不可能得到回文数
        }
    }
    return steps;
}

int main() {
    int base;
    string num;
    cin >> base >> num;

    int result = stepsToPalindrome(base, num);

    if (result == -1) {
        cout << "Impossible!" << endl;
    } else {
        cout << result << endl;
    }

    return 0;
}

def is_palindrome(num):
    return str(num) == str(num)[::-1]

def convert_to_base(num, base):
    result = ""
    while num > 0:
        digit = num % base
        result = str(digit) + result
        num //= base
    return result

def steps_to_palindrome(base, num):
    steps = 0
    while not is_palindrome(num):
        n = int(num, base)
        reverse_n = int(num[::-1], base)
        num = convert_to_base(n + reverse_n, base)
        steps += 1
        if steps > 30:
            return -1  # 超过30步不可能得到回文数
    return steps

base, num = map(int, input().split())
result = steps_to_palindrome(base, num)

if result == -1:
    print("Impossible!")
else:
    print(result)