【Uva 題庫解題】C++ 個人解題筆記（一顆星選集） - part 4

一篇十題讓你看到爽！

CPE 49 道必考題，資料來源：https://cpe.mcu.edu.tw/environment.php

31. All You Need Is Love!

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1134

No Zerojudge :(

題目翻譯（From Lucky貓）：

IBM（International Beautiful Machines）公司發明了一種小玩意兒叫做「愛的算命機」。這台機器會回答你是否非常渴望愛情。這機器運作的情形是：請你輸入一僅含 0 和 1 的字串（稱為 S），機器自己則定義一僅含 0 和 1 的字串（稱為 L，Love 的意思）。然後機器不斷的用 S 去減 L（當然是 2 進位的減法），如果最後可以得到 S = L，代表 S 是用 Love 做成的。如果最後 L > S，代表 S 不是用 Love 做成的。

舉例說明：假設 S = “11011”，L = “11”。如果我們不斷的從 S 減去 L，我們可以得到：11011、11000、10101、10010、1111、1100、1001、110、11。所以我們得到 L 了，也就是 S 是用 Love 做的。由於愛的算命機的某些限制，字串不可以有以 0 為開頭的，也就是說 “0010101”、”01110101”、”011111” 這些字串都是不合法的。另外，只有一個位元的字串也是不合法的。

Input

輸入的第一列有一個整數 N（ N < 10000 ），代表以下有幾組測試資料。每組測試資料 2 列，代表 S1 和 S2 字串，其長度都不會超過 30 個字元。你可以假設所有的字串都是合法的。

Output

對每一組測試資料輸出以下其中之一：

Pair #p: All you need is love!
Pair #p: Love is not all you need!

在這裡 p 代表這是第幾組測試資料。如果 S1 和 S2 至少可以找到一個合法的 L，使得 S1 和 S2 都可以用 Love 做成，則輸出第一種訊息。否則，請輸出第二種訊息。請參考 Sample Output。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5
11011
11000
11011
11001
111111
100
1000000000
110
1010
100

Sample Output

1
2
3
4
5
Pair #1: All you need is love!
Pair #2: Love is not all you need!
Pair #3: Love is not all you need!
Pair #4: All you need is love!
Pair #5: All you need is love!

解題思路：

題目在說要不斷的做 S - L，直到找到一個合法的 L。

所謂合法的 L 就是 S = L。（找 S 是否為 L 的倍數）

若要用一數找出同時對於兩字串都合法的情形，就是用到 GCD。

將二進位字串 S1 S2 轉成十進位 a b（用 stoi(str, nullptr, 2)），判斷 a 與 b 的最大公因數（GCD）是否大於 1。

gcd > 1：有共同的 Love 字串。

else：沒愛。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b){
    while (b != 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N;
    cin >> N;
    string s1, s2;
    
    for (int p = 1; p <= N; ++p){
        cin >> s1 >> s2;
        
        int a = stoi(s1, nullptr, 2);
        int b = stoi(s2, nullptr, 2);
        
        cout << "Pair #" << p << ": ";
        cout << ( gcd(a, b) > 1 ? "All you need is love!" : "Love is not all you need!");
        cout << '\n';
    }
    return 0;
}

32. Divide, But Not Quite Conquer!

PDF Source：https://onlinejudge.org/external/101/10190.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=e566

題目翻譯：

你在這個問題中的目標是，將某個整數 $n$ 重複除以另一個整數 $m$ ，直到 $n = 1$ ，形成一個數列。我們稱這個數列中的每個數為 $a[i]$ ，假設這個數列共有 $k$ 個數（也就是說你需要進行 $k - 1$ 次連續的除法操作才能讓 $n$ 變成 $1$ ）。

你只能在滿足以下限制的情況下擁有這樣的數列：

  • $a[1] = n$ ，且對所有 $1 < i \leq k$ 都有 $a[i] = a[i - 1] \div m$
  • $a[i]$ 可以被 $m$ 整除（也就是 $a[i] \quad mod \quad m = 0$ ，對所有 $1 \leq i < k$ 皆成立
  • $a[1] > a[2] > a[3] > \cdots > a[k]$

例如，若 $n = 125$ 且 $m = 5$ ，你會得到：125、25、5 和 1（你做了三次除法：125 ÷ 5、25 ÷ 5 和 5 ÷ 5）。

因此 $k = 4$ ， $a[1] = 125$ 、 $a[2] = 25$ 、 $a[3] = 5$ 、 $a[4] = 1$ 。

若 $n = 30$ 且 $m = 3$ ，你會得到 30、10、3 和 1。但 $a[2] = 10$ ，而 $10 \quad mod \quad 3 = 1$ ，因此此數列不成立，因為它違反了限制 2。當這樣的數列不存在時，我們覺得它既不好玩又很無聊！

注意點：

m 可能為 0 或 1，這兩個情況可在開頭就先排除掉。

範例程式碼：

2025/09/28 修改：部分錯誤，資料型態改成 long long，然後確認一下 m n 條件就可在 Uva Online Judge 上 AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

int main(){
    long long n, m;
    while (cin >> n >> m){
        if (m <= 1 || n < m) {
            cout << "Boring!\n";
            continue;
        }
        
        if (n == 1) {
            cout << "Boring!\n";
            continue;
        }

        vector<long long> nums;
        bool isBoring = false;

        while (true) {
            nums.emplace_back(n);
            if (n == 1) break;
            if (n % m != 0) {
                isBoring = true;
                break;
            }
            n /= m;
        }

        if (isBoring) {
            cout << "Boring!\n";
        } else {
            for (size_t i = 0; i < nums.size(); ++i) {
                if (i > 0) cout << " ";
                cout << nums[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

33. Simply Emirp

PDF Source：https://onlinejudge.org/external/102/10235.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=d387

題目翻譯：

一個大於 1 的整數，若其唯一的正整數因數為 1 和它本身，則稱為質數（Prime Number）。
質數多年來一直是許多數學家研究的對象。質數在密碼學與編碼理論中也有應用。

你曾試過把一個質數反轉嗎？對於大多數質數來說，反轉後會變成一個合數（例如 43 變成 34）。
Emirp（Prime 的反拼法）是一種質數，其數字反轉後仍為不同的質數。
例如，17 是 Emirp，因為 17 與其反轉後的 71 都是質數。

在本題中，你必須判斷一個數字 $N$ 是「非質數（Non-prime）」、「質數（Prime）」還是「Emirp」。假設 $1 < N < 1000000$ 。

有趣的是，Emirp 對於 NTU 的學生並不陌生。我們已經搭了 199 號與 179 號公車很長一段時間了！

精選單字：

  • prime number 質數
  • cryptography 密碼學
  • composite (n.) （由不同部分組成的）混合物，合成物，綜合體；複合材料，混合材料
  • emirp 反質數

解題思路：

用字串輸入 N，設兩變數 int a, b，a 是原本的數字 N，b 為反轉後的數字 N。

可用 <algorithm> 內建方法 reverse(N.begin(), N.end()) 反轉字串。

比較簡單且時間複雜度低的質數篩法可見範例程式碼。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

bool is_prime(int x){
    for (int y = 2; y * y <= x; ++y){
        if (x % y == 0){
            return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string N;
    
    while (cin >> N){
        
        int a = stoi(N);
        reverse(N.begin(), N.end());
        int b = stoi(N);
        
        if (is_prime(a)){
            if (a != b && is_prime(b)){
                cout << a << " is emirp.";
            }
            else{
                cout << a << " is prime.";
            }
        }
        else{
            cout << a << " is not prime.";
        }
        
        cout << "\n";
    }
    return 0;
}

34. 2 the 9s

PDF Source：https://onlinejudge.org/external/109/10922.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=d672

題目翻譯：

一個眾所皆知的技巧是：若要判斷一個整數 $N$ 是否為 $9$ 的倍數，可以計算其所有位數的總和 $S$ 。如果 $S$ 是 $9$ 的倍數，那 $N$ 也是。這是一種遞迴式的檢查方式，而要得到 $N$ 是否為 $9$ 的倍數所需遞迴的層數，就稱為 $N$ 的 $9$ 度數（9-degree）。

你的任務是：給定一個正整數 $N$ ，判斷它是否為 $9$ 的倍數；若是，則求出它的 $9$ 度數。

解題思路：

用迴圈替代遞迴，可避免 stack overflow（疑？好像有雙關…。

因為 N 可能有 1000 位，所以用 string 存。

再來題目要求計算 S，S 是所有「位」數字的和，如 9999：

$S = 9 + 9 + 9 + 9 = 36$

若 $S \quad mod \quad 9 \neq 0$ ，表 S 非 9 的倍數，則直接輸出即可。

那 S 做到 36 還不夠，要繼續做下去，下一個 S = 3 + 6 = 9，做到剩一個 9 就結束。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

int digitSum(const string& N){
    int sum = 0;
    for (char c : N){
        sum += c - '0';
    }
    return sum;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    string N;
    while (cin >> N && N != "0"){
        int degree = 0;
        
        int sum = digitSum(N);
        degree++;
        
        while (sum >= 10){
            sum = digitSum(to_string(sum));
            degree++;
        }
        
        if (sum == 9) {
            cout << N << " is a multiple of 9 and has 9-degree " << degree << "." << '\n';
        } else {
            cout << N << " is not a multiple of 9." << '\n';
        }
    }
    return 0;
}

35. GCD

PDF Source：https://onlinejudge.org/external/114/11417.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=d255

題目翻譯：

給定 N 的值，你必須找到一個值 G。G 的定義如下所示：

image

這裡的 $GCD(i, j)$ 表示整數 i, j 的最大公因數。

對於那些難以理解求和符號（Sigma）的人來說，G 的意義可從以下程式碼看出：

1
2
3
4
5
6
7
8
9
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=GCD(i,j);
}
/*Here GCD() is a function that finds
the greatest common divisor of the two
input numbers*/

範例程式碼：

實測 Uva Online Judge 跟 Zerojudge 都過得了，主打一個能過就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N;
    while (cin >> N && N != 0){
        int G = 0;
        for (int i = 1; i < N; ++i){
            for (int j = i + 1; j <= N; ++j){
                G += __gcd(i, j); // C++ 14
            }
        }
        cout << G << '\n';
    }
    return 0;
}

36. Largest Squares

PDF Source：https://onlinejudge.org/external/109/10908.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=e575

題目翻譯：

給定一個由字元組成的矩形網格，你需要找出最大的正方形邊長，使得該正方形內所有字元相同，且該正方形的中心點（兩條對角線的交點）位於位置 $(r, c)$ 。網格的高度和寬度分別為 $M$ 和 $N$ 。網格的左上角和右下角分別用 $(0, 0)$ 和 $(M-1, N-1)$ 來表示。以下是給定的字元網格。已知位置 $(1, 2)$ 之處，最大正方形的邊長為 $3$ 。

abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa

解題思路：

首先要釐清一件事情，就是有中心的正方形的邊長必為奇數。

在這邊初始化 maxLen 最大邊長可預設為 1，表示只有他自己而已。

之後跑個 for loop，for (int len = 3; ; len += 2)，從 3 開始去跑，每次 + 2 確保是奇數的。

內部邏輯就是自訂函數 is_valid() 去判斷擴張後是否能成為一個正方形，這部分根據題目條件去對 is_valid() 內部做設計。

如果 is_valid() true 的時候就更新最大長度，否則直接 break。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

// 檢查中心 (r, c) 為中心、邊長為 len 的正方形是否合法
bool is_valid(const vector<string>& grid, int r, int c, int len, int M, int N) {
    char ch = grid[r][c];           // 中心點的字元
    int half = len / 2;             // 擴張範圍的一半（如邊長 3，擴張距離是 1）
    // half 有點像半徑的概念

    // 邊界檢查
    if (r - half < 0 || r + half >= M || c - half < 0 || c + half >= N)
        return false;

    // 檢查範圍內所有字元是否與中心相同
    for (int i = r - half; i <= r + half; ++i) {
        for (int j = c - half; j <= c + half; ++j) {
            if (grid[i][j] != ch)
                return false;
        }
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int M, N, Q;
        cin >> M >> N >> Q;
        cout << M << " " << N << " " << Q << "\n";

        vector<string> grid(M);
        for (int i = 0; i < M; ++i) {
            cin >> grid[i];
        }

        while (Q--) {
            int r, c;
            cin >> r >> c;
            int maxLen = 1;        // 初始化最大正方形邊長為 1（最小可能）

            // 擴張正方形邊長：從 3 開始每次加 2（保持為奇數）
            for (int len = 3;; len += 2) {
                if (is_valid(grid, r, c, len, M, N)) {
                    maxLen = len;  // 若合法就更新最大長度
                } else {
                    break;         // 否則跳出迴圈，因為不能再擴張了
                }
            }

            cout << maxLen << "\n";
        }
    }

    return 0;
}

37. Satellites

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1162

No Zerojudge :(

題目翻譯：

地球的半徑為 6440 公里。有許多的衛星和小行星圍繞著地球移動。如果兩個衛星與地心形成一個角度，你能求出它們之間的距離嗎？

在此，我們所說的距離是指「弧」長和「弦」長。兩者的衛星皆位於相同的軌道上。（然而，請考慮它們是在圓形軌道上旋轉，而非橢圓形軌道。）

image

Input

輸入檔將包含一個或多個測資。

每組測資含一行，由兩個整數 s、a 所組成，及一個字串 “min” or “deg”。

其中 s 表示衛星與與地球表面的距離，a 表示衛星與地心間的夾角，單位可能是 min 分（’）或 deg 度（◦）。

請記得同一行永遠不會同時有分和度。

Output

對於每組測資，輸出一行，其中包含所需的距離，即兩顆衛星之間的弧長和弦長，以公里為單位。此距離應為浮點數值，顯示到小數點後六位數。

Sample Input

1
2
3
500 30 deg
700 60 min
200 45 deg

Sample Output

1
2
3
3633.775503 3592.408346
124.616509 124.614927
5215.043805 5082.035982

解題思路：

  1. 計算半徑

s 為衛星到地球表面的距離，而題目有給地球半徑 = 6440 km，因此可算由衛星到地心的總半徑：

r = R + s，設地球半徑為 R = 6440 km。

  1. 地心角單位換算

遇到 min 分的話，就除以 60 換算成 deg 度。

之後把度數轉成弧度，方便後續公式的計算：

1
double rad = angle * π / 180;
  1. 計算弧長

以下 θ 皆為弧度。

$arc = r × θ$

  1. 計算弦長

$chord = 2 × r × sin(\frac{θ}{2})$

最後要說一下這題有陷阱阿，試了好幾次都 WA，才知道問題出在 a 大於 180 度的情形。

因為題目要求最短距離，所以超過 180 度的都要寫 360 - a。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

const double R = 6440.0;
const double PI = acos(-1.0);

int main() {
    double s, a;
    string unit;

    while (cin >> s >> a >> unit) {
        double r = R + s;

        if (unit == "min") {
            a = a / 60.0;
        }

        if (a > 180.0) {
            a = 360.0 - a;
        }

        double rad = a * PI / 180.0;

        double arc = r * rad;
        double chord = 2.0 * r * sin(rad / 2.0);

        printf("%.6f %.6f\n", arc, chord);
    }

    return 0;
}

38. Can You Solve It?

PDF Source：https://onlinejudge.org/external/106/10642.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=i859

題目翻譯：

首先請看看下圖。在這張圖中，每個圓圈在笛卡兒座標系（就是直角坐標系）中都有一個座標。你可以沿著圖中標示的箭頭方向，從一個圓圈移動到另一個圓圈。若要從起始圓圈走到目標圓圈，

total_number_of_step(s)_needed = number_of_intermediate_circles_you_pass + 1

舉個例子，若要從 (0, 3) 走到 (3, 0)，你必須經過兩個中間圓圈 (1, 2) 和 (2, 1)。因此，在這個例子中，總步數為 2 + 1 = 3。

於本題中，你的任務是計算從一個起始圓圈到一個目標圓圈所需的步數。你可以假設無法逆著箭頭方向返回。

精選單字：

  • coordinate (n.) 座標
    • (v.) 協調；使相配合

解題思路：

這題我想了很久，最後沒辦法只能上網找解題思路，沒想到居然是用公式解出來的！？

解題思路主要就是把所有座標依照 x + y 去做分層，每層由左下到右上（假設平面座標不是題目畫的那樣奇奇怪怪的，而是 x 軸為橫軸、y 軸為縱軸）去做一個編號：

座標 (x, y)序號 idx
(0,0)0
(0,1)1
(1,0)2
(0,2)3
(1,1)4
(2,0)5
……

而分層的意思是依照平面上所有座標的 x + y 值去做分類，如果 x + y 值相同就會被分到同一層。

也可以想成是題目給的圖中，往左上的斜線經過的點都是同一層（原點 (0, 0) 也被視為一層）。

座標圖

那可以從表中觀察到幾個規律：

  • 每層的每點皆滿足 x + y = n 的條件。（n 為每層中的一個定值，如第一層 0 + 0 = 0、第二層 1 + 0 = 1、0 + 1 = 1）
  • 每層會有 n + 1 個點。
  • 每層的初始編號為 $S = \frac{n(n+1)}{2}$ 。

另外 S 也表示在進入該層（即 $x + y$ 層）之前，共有這麼多個點。（如 n = 2，進入點 (0, 2) 之前有三個點 (0, 1), (1, 0), (0, 0)）

經過多次驗證跟思考，如果在 S 後面加上一個 x，就可以推算出座標點的編號了。

舉個栗子：

$(1, 1)$ 的 n = 2，S = 3，編號 = 3 + 1 = 4。

$(1, 2)$ 的 n = 3，S = 6，編號 = 6 + 1 = 7。

看圖的話，編號上就結果而言是正確的，如果是 y 的話就變成：

  • 3 + 1 = 4
  • 6 + 2 = 8

雖然第一個是對的，但第二個編號錯了，因此不能 + y。

最後可得公式 $loc(x, y) = \frac{n(n+1)}{2} + x$ 。

由於只能向前，而不能向後移動，所以假設兩點 $(x1, y1), (x2, y2)$ ，則：

$step = loc(x2, y2) - loc(x1, y1)$

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll loc(ll x, ll y) {
    ll n = x + y;
    return n * (n + 1) / 2 + x;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int T;
    cin >> T;
    for(int i = 1; i <= T; ++i) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ll ans = loc(x2, y2) - loc(x1, y1);
        cout << "Case " << i << ": " << ans << '\n';
    }
    return 0;
}

39. Fourth Point!!

PDF Source：https://onlinejudge.org/external/102/10242.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=e512

題目翻譯：

已知平行四邊形兩條相鄰邊端點的 $(x, y)$ 座標。求第四個點的 $(x, y)$ 座標。

精選單字：

  • adjacent (adj.) 鄰近的
  • parallelogram (n.) 平行四邊形

解題思路：

利用向量及平行四邊形的性質去求第四個點。

平行四邊形的特性為對邊平行且長度相等。

image

用平行四邊形性質，可得到表示式： $\overrightarrow{AB} = \overrightarrow{CD}$ 。

假設 $A(0, 1), B(1, 1), C(0, 0), D(x, y)$ ，

$\overrightarrow{AB} = (1 - 0, 1 - 1) = B - A$

$\overrightarrow{CD} = (x - 0, y - 0) = D - C$

最後可得： $D - C = B - A$ → $D = C + (B - A)$ → $D = (1, 0)$ 。

記得題目的範例輸入不一定都是第二個、第三個點相同，所以這部分要一個一個找。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
    bool operator==(const Point& other) const { // overloading operator
        return abs(x - other.x) < 1e-8 && abs(y - other.y) < 1e-8;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    Point p[4];

    while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y >> p[3].x >> p[3].y) {
        Point A, B, C;
        
        if (p[0] == p[2]) {
            A = p[0]; 
            B = p[1]; 
            C = p[3];
            
        } else if (p[0] == p[3]) {
            A = p[0]; 
            B = p[1]; 
            C = p[2];
            
        } else if (p[1] == p[2]) {
            A = p[1]; 
            B = p[0]; 
            C = p[3];
            
        } else {
            A = p[1]; 
            B = p[0]; 
            C = p[2];
        }

        double Dx = B.x + C.x - A.x;
        double Dy = B.y + C.y - A.y;

        // or printf("%.3f %.3f", Dx, Dy);
        cout << fixed << setprecision(3) << Dx << " " << Dy << "\n";
    }

    return 0;
}

40. A mid-summer night’s dream

PDF Source：https://onlinejudge.org/external/100/10057.pdf

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=e606

題目翻譯：

今為公元 2200 年。科學在兩百年間進步了許多。提到兩百年是因為這個問題是利用時間機器送回到公元 2000 年。現在可以建立人與電腦 CPU 之間的直接連結。人們可以透過 3D 顯示器（也就是今天的螢幕）來觀看他人的夢境，就像看電影一樣。本世紀的一個問題是人們對電腦變得過度依賴，以致於他們的分析能力幾乎接近於零。電腦現在可以閱讀問題並自動解決它們，但只能解決困難的問題。現在沒有簡單的問題了。我們的首席科學家遇到了大麻煩，因為他忘記了組合鎖的密碼。出於安全考量，現今的電腦無法解決和組合鎖相關的問題。在一個仲夏夜，科學家做了一個夢，夢見許多無號整數四處飛舞。他利用他的電腦記錄下這些數字，然後他得到線索，如果這些數字是（ $X₁, X₂, …, Xₙ$ ），他必須找到一個整數 $A$ （ $A$ 是組合鎖密碼），使得

$(|X₁ - A| + |X₂ - A| + … + |Xₙ - A|)$

的值最小。

精選單字：

  • as if 好像、彷彿
  • chief (adj.) 首席的、首要的

解題思路：

這題的重點就是要找到一個 A 使 S 最小：

$S = \sum^n_{i = 1} |X_i - A|$

其實這題跟 Vito’s family 蠻像的，A 是要取中位數，才可以讓 S 變最小。

為了方便求中位數，所以要先將資料排序。

若資料總量 n 是奇數，表示中位數只有一個，否則為兩個。

遇到兩個中位數可這樣求：

1
2
int low = v[n / 2 - 1];
int high = v[n / 2];

若要計算輸出的第二個數字（|Xi − A| 為最小值的數量，其實就是找兩個中位數間的區間長），則用：

1
int count = upper_bound(v.begin(), v.end(), high) - lower_bound(v.begin(), v.end(), low);

用線性搜尋找也不是不行，但既然都資料排序了，那用二分搜豈不是更快？

第三個數字則是算區間長度：

1
int range_count = high - low + 1;

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n;
    while (cin >> n && n > 0) {
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        
        sort(v.begin(), v.end());

        if (n % 2 == 1) {
            int median = v[n / 2];
            int count = upper_bound(v.begin(), v.end(), median) - lower_bound(v.begin(), v.end(), median);
            cout << median << " " << count << " 1\n";
        } else {
            int low = v[n / 2 - 1];
            int high = v[n / 2];
            int count = upper_bound(v.begin(), v.end(), high) - lower_bound(v.begin(), v.end(), low);
            int range_count = high - low + 1;
            cout << low << " " << count << " " << range_count << "\n";
        }
    }
    return 0;
}