14034: 【原4034】NaivePalindrome

题目

题目描述

author: Vegw 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4034

Description

​ 云学长性格严谨，因此对于一切具有对称美的事物有着天然的喜好。

若一个合法（首位不为零）的数字从左向右读与从右向左读都一样，就将其称之为回文数。显然回文数符合云学长的审美，他因而决定对一切数字进行回文化改造。

改造的具体实现如下，将一个N进制下的数字与它的逆反相加，得到一个新数字，被称为一步操作。对得到的新数字重复上述操作直至得到一个回文数，现在云学长希望知道最少几步可以成功回文化一个给定数字。

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

​

又如：对于10进制数87：

​ STEP1：87+78 = 165 STEP2：165+561 = 726

​ STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

上例最少用了4步得到回文数4884，因此输出“STEP=4”(答案输出不包含引号)。

​ 但人生苦短，如果在30步以内（包含30步）不可能得到回文数，云学长就不希望继续对该数字进行回文化改造，输出“Impossible!”

Input Format

输入数据为两行,

第一行为一个正整数N(2 <= N <= 20)，代表给出数字为N进制

注：N > 10时，会使用从A开始的一系列大写字母顺序代替大于10的数字

例如：(12进制) A = 10 (10进制)

​ (16进制) C = 12 (10进制)

第二行是给出的一个长度为 L (0 < L <= 100 )的数字串

对于70%的数据 N = 10；

Output Format

对于能在30步（包含30步）之内得到回文数的数字串，输出“STEP=步数”

否则输出“Impossible!”

Sample Input

10
56

Sample Output

STEP=1

FineArtz's solution

/* NaivePalindrome */
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int MAXS = 105;
int n = 10;
inline int change(const char &ch){
    if (isalpha(ch)) return (ch - 'A' + 10);
    else return (ch - '0');
}
class BigInt{
    //friend
    friend void add(BigInt&);
public:
    //constructor
    BigInt();
    BigInt(const string&);
    BigInt(const BigInt&);
    int len;
    int data[MAXS];
};
BigInt::BigInt() : len(0){
    memset(data, 0, sizeof(data));
}
BigInt::BigInt(const string &s){
    memset(data, 0, sizeof(data));
    len = s.size();
    for (int i = 1; i <= len; ++i)
        data[i] = change(s[len - i]);
}
BigInt::BigInt(const BigInt &rhs) : len(rhs.len) {
    memset(data, 0, sizeof(data));
    for (int i = 1; i <= len; ++i) data[i] = rhs.data[i];
}
void add(BigInt &x){
    BigInt ret;
    ret.len = x.len;
    for (int i = 1; i <= x.len; ++i)
        ret.data[i] = x.data[i] + x.data[x.len - i + 1];
    for (int i = 1; i <= x.len; ++i){
        if (ret.data[i] >= n){
            ret.data[i] -= n;
            ++ret.data[i + 1];
        }
    }
    if (ret.data[ret.len + 1] != 0)
        ++ret.len;
    x.len = ret.len;
    for (int i = 1; i <= ret.len; ++i)
        x.data[i] = ret.data[i];
}
bool check(const BigInt &x){
    for (int i = 1; i <= x.len / 2; ++i)
        if (x.data[i] != x.data[x.len - i + 1]) return false;
    return true;
}
int main(){
    cin >> n;
    string num;
    cin >> num;
    BigInt x(num);
    int step = 0;
    while (!check(x)){
        add(x);
        ++step;
        if (step >= 30){
            cout << "Impossible!" << endl;
            return 0;
        }
    }
    cout << "STEP=" << step << endl;
    return 0;
}