Zapping

Problem

題目的主角很喜歡看電視，不過他從來不會乖乖停在同一台，會一直切到其他台。偏偏他家的狗把遙控器啃了，數字鍵全滅，只剩下「下一台」（△）和「上一台」（▽）兩顆按鈕還能用。想從第 3 台轉到第 9 台嗎？乖乖按 △ 六次吧。🐶🥵

而電視總共有 100 個頻道，編號 0 到 99，而且是循環的：

• 在 99 台按 △ 會回到 0 台。

• 在 0 台按 ▽ 會跳到 99 台。

給定現在的頻道 $a$ 和想去的頻道 $b$，求最少要按幾下。

輸入有多組測資（最多 200 組），每行兩個整數 $a$、$b$，$0 \le a, b \le 99$，以一行 $-1 -1$ 作為結束字元。

Approach

我一看到就把它畫成數線：$a$、$b$ 是 0–99 上的兩個點，想從 $a$ 走到 $b$ 只有兩條路：

1. 直接走：從 $a$ 走到 $b$，距離 $|a - b|$。

2. 繞過去：往反方向走到盡頭，從 99 跳回 0（或反過來），再走到 $b$。

關鍵在於第二條路那個「跳回去」的動作也要按一下。把數線頭尾接起來看就很清楚：

四段加起來是 $a + (b - a) + (99 - b) + 1 = 100$，正好是 100 個頻道。數線上 0 到 99 只有 99 個間隔，第 100 個間隔就是那條虛線，也就是環的接縫。

所以令 $d = |a - b|$，兩個方向的按鍵數分別是 $d$ 和 $100 - d$，答案就是

因為取了絕對值，$a > b$ 還是 $a < b$ 都一樣，完全不用像我一開始那樣 swap。

什麼時候該繞路？

兩條路一條走 $d$ 格、一條走 $100 - d$ 格，加起來永遠是 100，也就是剛好一整圈。所以兩條路不可能同時都很長，一邊變長，另一邊就等量變短。（呈線性負相關）

要判斷繞路是否比較近，只要解這個不等式：

換成白話：

所以 50 就是分界點，也就是一圈 100 的一半。這個分界也直接解釋了我第一版為什麼只有 $d \ge 50$ 會錯：舊公式用的是 $99 - d$，等於把一圈當成 99，分界點被偷偷挪到 $49.5$。

• $d \le 49$ 時兩個版本都選「直接走」，答案都是 $d$，錯誤完全被藏住。
• $d \ge 50$ 時舊版改選「繞過去」，而繞過去那條剛好少算了一格，錯誤才浮上來。

另一種寫法

如果想直接模擬「往上按幾下」和「往下按幾下」，可以用取模。往上是從 $a$ 走到 $b$，往下是從 $b$ 走回 $a$：

1
int up   = (b - a + 100) % 100;  // 一直按 △
2
int down = (a - b + 100) % 100;  // 一直按 ▽
3
cout << min(up, down) << '\n';

先加 100 是因為 C++ 對負數取模會得到負數（例如 $-6$），加完再取模就能保證落在 $0$ 到 $99$。而 up + down 在 $a \ne b$ 時一定等於 100，跟上面的 $d$ 和 $100 - d$ 是同一件事。

Wrong attempts

第一版我先 swap 讓 $a \le b$，然後另一條路寫成 $99 - b + a$：

1
while (cin >> a >> b) {
2
    if (a == -1 && b == -1) {
3
        break;
4
    }
5
    if (a > b) {
6
        swap(a, b);
7
    }
8

9
    if (a == 0 && b == 99) {
10
        cout << "1\n";
11
    } else {
12
        cout << min(b - a, 99 - b + a) << '\n';
13
    }
14
}

我少算了 99 → 0 那一格。題目寫的是 0 到 99，我腦中就直接拿 99 當一圈的長度，忘了它其實有 100 個頻道，太粗心了。😂

更好笑的是第 9–10 行那個特判。範例的 $0$ $99$ 用我的公式算出來是 $\min(99,\ 99 - 99 + 0) = 0$，明顯不對，我就直接寫死輸出 1。其實那是公式在報錯，我卻直接忽略了。它剛好是 $b - a = 99$ 的情況，少算一格的錯誤在這裡非常明顯，真的是事出必有因。

實際上只要間距 $d = b - a \ge 50$，繞過去那條就會變成比較短的一邊，少的那一格就會直接反映在答案上：

三筆範例全過，其中一筆還是靠特判撐住的，難怪自己測不出來。WA 之後我想到 $0$ $50$ 這組，果然跑出 49，才發現是 99 和 100 的差別。

改完的差異只有這幾行：

1
if (a > b) {
2
    swap(a, b);
3
}
4
d = abs(a - b);
5
if (a == 0 && b == 99) {
6
    cout << "1\n";
7
} else {
8
    cout << min(b - a, 99 - b + a) << '\n';
9
cout << min(d, 100 - d) << '\n';

swap 和特判都不見了，特判能被刪掉，本身就是公式終於對了的證據，程式碼本身也優雅簡潔了許多（可讀性也更高）！

Solution

6 collapsed lines
1
#include <iostream>
2
#include <algorithm>   // min
3
#include <cstdlib>     // abs
4

5
using namespace std;
6

7
void solve() {
8
    int a, b;
9
    int d;
10

11
    while (cin >> a >> b) {
12
        if (a == -1 && b == -1) {
13
            break;
14
        }
15

16
        d = abs(a - b);
17

18
        cout << min(d, 100 - d) << '\n';
19
    }
20
}
21

8 collapsed lines
22
int main() {
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25

26
    solve();
27

28
    return 0;
29
}

被標起來的兩行就是全部：算出兩點距離，再跟繞一圈的另一邊比大小。

Sample Input

1
3 9
2
0 99
3
12 27
4
-1 -1

Sample Output

1
6
2
1
3
15

驗算：$0$ $99$ 的 $d = 99$，另一邊是 $100 - 99 = 1$，答案 1，不需要任何特判。

自己加的測資

1
0 50
2
50 0
3
7 7
4
99 0
5
80 10
6
-1 -1

1
50
2
50
3
0
4
1
5
30

分別測了剛好一半、$a > b$、原地不動、繞一圈、以及 $a > b$ 又要繞路的情況。

See also

• Cycle graph（Wikipedia）：環圖 $C_n$ 的定義與性質

• Lee distance（Wikipedia）：同一個距離公式在 Coding theory 裡的版本