Reverse and Add

Problem

反轉相加的操作是拿一個數，把它的數字順序反過來，再與原本的數相加。如果加出來的和不是迴文（從左讀和從右讀順序一樣），就對這個和重複同樣的操作。

以 $195$ 為例：

加了 $4$ 次得到回文 $9339$，所以輸出 $4$ $9339$。

題目有提到大部分的數都會在幾步之內變成迴文，但也有例外：196 （剛好就是範例測資的下一個數） 是第一個到現在都沒有人找到迴文的數（但也還沒有人證明它永遠不會變成回文）。不過這題有保證所有測資：

• 一定會得到迴文；
• 少於 1000 次加法；
• 最後的迴文不超過 $4,294,967,295$（也就是 $2^{32} - 1$，咦？ unsigned int 範圍？）。

輸入第一行是測資數 $N$（$0 < N \le 100$），接著 $N$ 行各一個數 $P$。每筆輸出「加法次數」和「最終得到的迴文」，中間一個空白。

Approach

沒有任何捷徑可走，直接模擬：

1. 反轉 $p$，得到 $\text{rev}(p)$。
2. $p \leftarrow p + \text{rev}(p)$，次數 $+1$。
3. 如果 $p = \text{rev}(p)$，結束；否則回到 $1$。

而「是不是迴文」其實就是「反轉後是否跟自己一樣」，所以步驟 $1$ 的反轉函式可以重複用來判斷。

會不會溢位呢？

題目保證最後的迴文 $\le 2^{32} - 1$。過程中的每個數都比最後的結果小（每一步都是加上一個正數），而 $\text{rev}(p)$ 又小於 $p + \text{rev}(p)$，所以整個過程中出現的所有數都不超過 $2^{32} - 1$。

本來想用 unsigned int，結果沒有現在才發現居然沒有 stoui？

unsigned int 的上限剛好就是 $2^{32} - 1$，看起來完美貼合題目限制，所以我原本想用它。寫到一半才發現，標準庫的字串轉整數只有這幾個：

好吧，沒有 stoui。上網查了一下，這些函式都是包裝 C 的 strtol 系列，而 C 本來就只有 strtoul（unsigned long）和 strtoull，沒有回傳 unsigned int 的版本。

真的要用 unsigned int 的話，有兩條路：

1
unsigned x = stoul(p) + stoul(p_rev);

1
unsigned p;
2
cin >> p;          // cin 可以直接讀進 unsigned

用方法 1 時要注意，stoul 回傳的 unsigned long 大小會隨平台改變：

這題的數都不超過 $2^{32} - 1$，所以兩種平台都還行，但寫 Cross-platform 程式時不能假設 long 一定是 64 位元。

所以結論是：在 online judge 上用 long long 或 unsigned long long 比較保險，多出來的 4 bytes 對這題完全沒有影響。

至於反轉時的前導零要怎麼處理？

反轉 750 會得到 057，也就是 57。不過以下提供的兩種寫法都處理掉了：

• 字串版經過 stoll(“057”) 後會得到 57。
• 數字版的話則是 r = r * 10 + x % 10 反轉後，開頭的 $0$ 本就不會留下來。

判斷迴文時也不會誤判：“750” 和 “057” 不相等，750 和 57 也不相等，因為位數上就有差異。

我在寫的時候其實有在想要用 while 還是 do-while？

題目的描述其實是「先反轉相加，如果和不是回文再重複」，也就是至少會做一次加法，然後才檢查。我一開始寫的 AC 版用的是 while，會先檢查再加：

1
while (p != rev(p)) {     // 先檢查
2
    p += rev(p);
3
    ++it;
4
}
5

6
do {                      // 先加，再檢查
7
    p += rev(p);
8
    ++it;
9
} while (p != rev(p));

兩張圖唯一的差別是菱形的位置：while 把檢查放在加法前面，do-while 放在後面。

這兩種寫法只有在輸入本身就是迴文時會不一樣。以輸入 $1$ 為例：

若按照題目的字面定義，要用 do-while 才對。不過我的 while 版一次 AC，代表 online judge 的測資裡應該沒有本身就是迴文的輸入，所以這個差別沒有被測到。

Solution

5 collapsed lines
1
#include <iostream>
2
#include <string>
3

4
using namespace std;
5

6
void solve() {
7
    int n;
8
    string p;
9
    string p_rev;
10
    long long x;
11

12
    while (cin >> n) {
13
        for (int i = 1; i <= n; i++) {
14
            int iteration = 0;
15

16
            cin >> p;
17

18
            p_rev = string(p.rbegin(), p.rend());
19

20
            while (p != p_rev) {
21
                x = stoll(p) + stoll(p_rev);
22
                p = to_string(x);
23
                p_rev = string(p.rbegin(), p.rend());
24
                iteration++;
25
            }
26

27
            cout << iteration << ' ' << p << '\n';
28
        }
29
    }
30
}
9 collapsed lines
31

32
int main() {
33
    ios::sync_with_stdio(false);
34
    cin.tie(nullptr);
35

36
    solve();
37

38
    return 0;
39
}

第 18 行我用反向迭代器 rbegin()、rend() 直接建出反轉後的字串。第 20～25 行是主迴圈：兩個字串轉成 long long 之後相加，再轉回字串、重新反轉，直到兩者相等。

Sample Input

1
3
2
195
3
265
4
750

Sample Output

1
4 9339
2
5 45254
3
3 6666

Refinement

AC 之後回來看，有幾個地方可以更精簡。

其實不用字串，直接用數字反轉？

既然整個過程都在 64 位元整數的範圍內，就不需要在字串和數字之間來回轉換。原本每一輪要做兩次 stoll、一次 to_string，再建一次反轉字串，其實不必，改成純數字運算後只會剩下除法和取餘數的運算。

1
unsigned long long rev(unsigned long long x) {
2
    unsigned long long r = 0;
3
    while (x != 0) {
4
        r = r * 10 + x % 10;
5
        x /= 10;
6
    }
7
    return r;
8
}

每輪把 x 的個位數接到 r 後面，再把 x 的個位數去掉。以 1234 為例：

Alternatives

然而，字串版還是有它的用處。數字版的前提是「結果放得進 64 位元」。但如果題目拿掉 $\le 2^{32} - 1$ 的保證，比如要你算到幾百位數，數字版就完全不能用了。

這時候字串版只要把 stoll + to_string 換成逐位的大數加法，就能處理任意長度。

雖然這題用不到，但題目提及的 $196$ 這種算了幾百萬步還沒變迴文的研究，用的就是這類大數運算寫法。

See also

• Lychrel number（Wikipedia）：196 這類數的名稱