ZeroJudge C015: Reverse and Add

UVa 10018 – Reverse and Add

The method of reversing a number and adding it is simple: just reverse the number and add it to the original number. If the sum is not a palindrome (meaning the number is the same when read from left to right and right to left), repeat this process. Here's an example:

Starts with 195
591
—–
786
687
—–
1473
3741
—–
5214
4125
—–
Palindrome 9339 appears!

In this example, after 4 iterations of addition, we obtain the palindrome 9339. Almost all integers yield palindromes using this method, but there are interesting exceptions. 196 is the first number for which a palindrome cannot be found using this method, although it hasn't been proven that such a palindrome doesn't exist.

Now, give me a starting number, and your task is to find out after how many iterations of addition a palindrome will be produced. For all test data, you can assume:

  1. There will always be exactly one answer.
  2. The answer will be found within 1000 iterations of addition.
  3. The produced palindrome will not be greater than 4294967295.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains an integer N (0 < N <= 100), representing how many sets of test data follow. Each set of test data consists of one line containing an integer P, which is the starting number.For each set of test data, please output 2 numbers: the minimum number of additions required to obtain the palindrome and the palindrome itself.
5
195
265
750
2
99		4 9339
5 45254
3 6666
1 4
6 79497

Thought Process

Each number needs to be calculated at least once, so even if it's already a palindrome at the beginning, you need to calculate when the next palindrome will appear. You can convert the received data into strings or receive it as strings from the beginning. Use a while loop to continuously calculate if the current number is not a palindrome, and increment the count each time inside the while loop.

Sample Code－ZeroJudge C015: Reverse and Add

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

int toint (string str)
{
    if (str.length() == 1) return int(str[0] - '0');
    return stoi(str);
}

int calc (int N)
{
    int a = N;
    string str = to_string(N);
    reverse(str.begin(), str.end());
    int b = toint(str);
    return a + b;
}

bool OK (int N)
{
    string str = to_string(N);
    string str1 = str;
    reverse(str1.begin(), str1.end());
    if (str == str1) return true;
    return false;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        int count = 1;
        tmp = calc(tmp);
        while (!OK(tmp))
        {
            count++;
            tmp = calc(tmp);
        }
        cout << count << " " << tmp << "\n";
    }
}

//ZeroJudge C015
//Dr. SeanXD
Tags

Related Posts

Comments