Skip to content

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;
}