Skip to content

14269: 【原4269】助教的寻宝之旅

题目

题目描述

author: Lei Zheng 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4269

Description

助教来到了一个群岛,其中一个岛上藏有从前大海盗离开时候没有来得及带走的宝藏。助教非常想要得到这个大宝藏。为了得到这个宝藏,助教需要得到一个走向真正宝藏所在岛屿的路线。守卫老人给了助教一个数字,这个数字中包含了这个秘密。如果这个数字从前面看和从后面看都是相同的(回文数),数字代表的岛屿编号就是宝藏的藏身地点。如果不是的话,就要把数字与这个数字的逆序数字相加,直到得到这样一个奇特的数字(比如 12 -> (12 + 21) 33 bingo!)。由此形成的路线就是安全的前进路线。聪明的你,快来帮助教找到安全的寻宝路线吧。

Input Format

一个正整数 特别说明:计算过程中的数字不会超过 2^31,并且程序一定会终止。

Output Format

第一行输出助教需要几步才能走到宝藏。 第二行输出助教的前进路线。

Sample Input

12345
57392

Sample Output

1
12345--->66666
3
57392--->86767--->163535--->698896

ligongzzz's solution

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

bool is_ans(int input) {
    string a = to_string(input);
    int length = a.length();
    for (int i = 0; i < length; ++i) {
        if (a[i] != a[length - i - 1])
            return false;
    }
    return true;
}

int next_n(int input) {
    string a = to_string(input);
    reverse(a.begin(), a.end());
    return stoi(a) + input;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;

    while (cin >> n) {
        int o_n = n;
        vector<int> nxt_ans;
        while (!is_ans(n)) {
            n = next_n(n);
            nxt_ans.emplace_back(n);
        }

        cout << nxt_ans.size() << endl << o_n;
        for (auto p : nxt_ans)
            cout << "--->" << p;
        cout << endl;
    }

    return 0;
}

victrid's solution

#include <iostream>
#include <cmath>
using namespace std;
int Invert(int);
int main(){
    int n;
    cin>>n;
    //get step.
    int step = 0;
    int n_op=n;
    while(n_op!=Invert(n_op)){
        n_op+=Invert(n_op);
        step++;
    }
    //print step.
    bool INI_FLAG=false;
    cout<<step<<endl;
    cout << n;
    while(n!=Invert(n)){
        cout << "--->";
        n+=Invert(n);
        cout << n;
    }
    return 0;
}
int Invert(int n){
    int a=0;
    while(n>0){
        a=a*10+n%10;
        n/=10;
    }
    return a;
}

Zsi-r's solution

#include <iostream>
#include <cstring>

using namespace std;


class seqStack
{
private:
    char *elem;
    int top_p;
    int maxSize;
    void doubleSpace();
public:
    seqStack(int initSize = 10);
    seqStack(const seqStack &s1);
    ~seqStack();
    bool isEmpty() const;
    void push(const char &x);
    char pop();
    char top() const;
    int rout(int count,char *s[]);
    void print() const;
};

seqStack::seqStack(int initSize)
{
    elem = new char[initSize];
    maxSize = initSize;
    top_p = -1;
}

seqStack::seqStack(const seqStack &s1)
{
    elem = new char[10];
    maxSize = s1.maxSize;
    top_p = s1.top_p;
    for (int i = 0; i < s1.top_p;i++)
    {
        elem[i]=s1.elem[i];
    }
}

seqStack::~seqStack()
{
    delete []elem;
}

bool seqStack::isEmpty() const
{
    return top_p==-1;
}

void seqStack::push(const char &x)
{
    if (top_p==maxSize-1) doubleSpace();
    elem[++top_p] = x;
}

char seqStack::pop()
{
    return elem[top_p--];
}

char seqStack::top() const
{
    return elem[top_p];
}

void seqStack::doubleSpace()
{
    char *tmp = elem;

    elem  = new char[2*maxSize];

    for (int i =0;i<maxSize ; i++)
    {
        elem[i]= tmp[i];
    }
    maxSize *=2;
    delete []tmp;
}

int seqStack::rout(int count,char *s[])
{
    seqStack s2,tmp;
    s[count-1] = new char[(this->top_p)+2];
    for (int i = 0; i <= top_p;i++)
    {
        s[count - 1][i] = elem[i];
    }

    bool flag = true;
    for (int i = 0; i <= top_p;i++)
    {
        tmp.push(this->elem[i]);
    }
    while (!tmp.isEmpty())
    {
        s2.push(tmp.pop());
    }
    for (int i = 0; i <= this->top_p;i++)
    {
        if (this->elem[i]!=s2.elem[i])
        {
            flag = false;
            break;
        }
    }

    if (flag)
    {
        return count;
    }
    else
    {
        seqStack s3,s4;
        int carry = 0;
        int sum;
        int x1 = top_p + 1;
        for (int i = 0; i < x1;i++)
        {
            sum = (pop()) + (s2.pop()) - '0' - '0'+carry;
            carry = sum / 10;
            s3.push(sum % 10 + '0');
        }
        if (carry !=0)
            s3.push('1');
        int x2 = s3.top_p + 1;
        for (int i = 0; i < x2;i++)
        {
            s4.push(s3.pop());
        }
        return s4.rout(count + 1, s);
    }
}

void seqStack::print()const
{
    for (int i = 0; i <= this->top_p;i++)
    {
        cout << elem[i];
    }
}

int main()
{
    char num[100];
    cin >> num;
    int count = 1;

    seqStack s1;
    char *s[20];

    for (int i = 0; i < strlen(num);i++)
    {
        s1.push(num[i]);
    }

    count = s1.rout(count,s);

    cout << count-1 << endl;

    cout << s[0];

    if (count>1){
        for (int i = 1; i < count;i++)
        {
            cout << "--->"<< s[i];
        }
    }

}