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

一篇十題讓你看到爽！

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

1. Vito’sfamily

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

zerojudge：https://zerojudge.tw/ShowProblem?problemid=a737

題目翻譯：

世界知名的黑幫 Vito Deadstone 要搬到紐約了。他在那邊有個大家族，他們全部都住在 Lamafia 大街上。因為他時常要拜訪他所有的親戚，所以他想要找一間離他們很近的房子。

Vito 想最小化與他們的距離和，然後還威脅你要寫個程式幫他解決這個問題。

精選單字：

  • avenue (n.) 大街、大道；方法、途徑、管道
  • relative (n.) 親戚、親屬
    • (adj.) 比較的；相對的

解題思路：

首先要搞懂這個距離的定義。題目給定多個門牌號碼 $s_1, s_2, …, s_r$，選定一個數 $x$ 作為 Vito 的家，因此總距離為：

這題的重點是 $x$ 要取什麼，直接說結論好了，就是取中位數。

為什麼是中位數？這就需要會一點微分的概念去做數學證明了。

但是本系列僅止於解題，這部分不多贅述，反倒是有個方法能夠直覺地看出為什麼是中位數：

假設其中一個輸入測資是 [1, 2, 4, 8, 10]，此時我們將這些數字一個個代入上面那個公式，即可列表：

x 值總距離
10+1+3+7+9 = 20
21+0+2+6+8 = 17
43+2+0+4+6 = 15
87+6+4+0+2 = 19
109+8+6+2+0 = 25

唉呦，可以發現在中位數的地方就是最小值 15。

如果你不信的話，可以拿範例測資來試試看：

2 4

x 值總距離
20 + 2 = 2
42 + 0 = 2

2 4 6

x 值總距離
20 + 2 + 4 = 6
42 + 0 + 2 = 4
64 + 2 + 0 = 6

1 2 5 9999

x 值總距離
10 + 1 + 4 + 9998 = 10003
21 + 0 + 3 + 9997 = 10001
54 + 3 + 0 + 9994 = 10001
99999998 + 9997 + 9994 = 29989

範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    
    while (T--){
        int r;
        cin >> r;
        
        vector <int> s(r);
        for (int i = 0; i < r; ++i){
            cin >> s[i];
        }
        
        sort(s.begin(), s.end());
        
        int median = s[r/2];
        int result = 0;
        
        for (int i = 0; i < r; ++i){
            result += abs(median - s[i]);
        }
        
        cout << result << '\n';
    }
    return 0;
}

2. Hashmat the Brave Warrior

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

zeroJudge：https://zerojudge.tw/ShowProblem?problemid=a012

題目翻譯：

Hashmat 是個勇敢的戰士，帶領著他的一群年輕士兵，從某地移動到另一個地方與敵人對抗。打仗之前他會計算一件事，就是他的士兵數量與敵對士兵數量的差距。這個差距會讓他決定要不要打。Hashmat 的士兵數量都不會大於敵對士兵。

沒有解題思路，so ez。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>

using namespace std;

int main(){
    long long h, o;
    while (cin >> h >> o){
        cout << abs(h - o) << '\n';
    }
    return 0;
}

3. Primary Arithmetic

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

ZeroJudge：https://zerojudge.tw/ShowProblem?problemid=c014

題目翻譯：

孩子們被教導從右到左逐位相加多位數。許多人發現「進位」操作——即從一位數位置進位 1 到下一位數位置相加——是一項顯著的挑戰。你的任務是計算每組加法問題中的進位操作次數，以便教育工作者能夠評估其難度。

精選單字：

  • assess (v.) 評價；對…估價

解題思路：

唯一要注意的就是記得設 carry 變數表示進位（1 或 0），在每次的 sum 中都要加上 carry，不然的話就會判斷錯誤，然後 WA。

範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

int main(){
    
    long long n1, n2;
    
    while (cin >> n1 >> n2 && (n1 || n2)){
        int carry = 0, operation = 0;
        
        while (n1 > 0 || n2 > 0){
            int digit_1 = n1 % 10, digit_2 = n2 % 10;
            
            int sum = digit_1 + digit_2 + carry;
            
            sum >= 10 ? carry = 1, operation++ : carry = 0;
            
            n1 /= 10, n2 /= 10;
        }
        
        if (operation){
            cout << operation << (operation > 1 ? " carry operations." : " carry operation.");
        }
        else{
            cout << "No carry operation.";
        }
        
        cout << '\n';
        
    }
    return 0;
}

4. The 3n + 1 problem

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

zerojudge：https://zerojudge.tw/ShowProblem?problemid=c039

題目翻譯：

電腦科學中的問題通常被分類為某類問題（如 NP、不可解、遞迴）。在本題中，你將分析一個演算法的性質，其分類對於所有可能的輸入尚不清楚。

考慮以下演算法：

  1. 輸入 $n$
  2. 輸出 $n$
  3. 如果 $n = 1$ 則停止
  4. 如果 $n$ 是奇數則 $n$ ← $3n+1$
  5. 否則 $n$ ← $n/2$
  6. 轉到步驟 2

給定輸入 22，會列印出以下數列：

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

據推測，上述演算法對於任何整數輸入值，均會終止（當列印出 1 時）。儘管該演算法簡單，但是否屬實尚不清楚。已驗證，對於所有整數 $n$ 滿足 $0 < n < 1,000,000$ （實際上遠超此範圍的更多數值），該推測成立。

給定一個輸入 $n$ ，可以確定在列印出 1 前後（包括 1）的列印數量。對於給定的 $n$ ，這被稱為 $n$ 的循環長度。在上述範例中，22 的循環長度為 16。

對於任意兩個數值 $i$ 和 $j$ ，您需要確定所有數值（包括 $i$ 和 $j$ ）之間的最大循環長度。

精選單字：

  • conjecture (n.)(v.) 推測、猜測。

範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

int getCycleLength(int n){
    int count = 1;
    while (n != 1){
        if (n % 2 == 1) n = 3 * n + 1;
        else n /= 2;
        count++;
    }
    return count;
}

int main(){
    int i, j;
    while (cin >> i >> j){
        int from = min(i, j);
        int to = max(i, j);
        int max_cycle = 0;
        for (int i = from; i <= to; ++i){
            int cycle_length = getCycleLength(i);
            if (cycle_length > max_cycle) max_cycle = cycle_length;
        }
        cout << i << " " << j << " " << max_cycle << '\n';
    }
    return 0;
}

唯一要注意的就是 for 迴圈的條件，寫成 <= 而非 <，因為題目說包含 i, j，所以是閉區間 [i, j]。

其他就是按照題目演算法流程去走，不要看題目寫一大堆廢話。

5. You can say 11

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

zerojudge：https://zerojudge.tw/ShowProblem?problemid=d235

沒啥好翻譯的，就是給你一個數字，這數字有可能到 1000 位數，然後求數字 % 11 是否等於 0。

解題思路：

先說這是 Python 天堂，我也很想用 Python… QQ，但為了磨練 CPP 實力只好動腦一下惹～

在 C++ 中要處理這種位數大的數字，就是用字串去存他。

然後 11 倍數判別法相信各位都還知道，就是奇數位相加 - 偶數位相加 = 0 的時候就是 11 的倍數。

如 121 是 11 的平方，1 + 1 - 2 = 0，因此這是 11 的倍數。

所以在 C++ 程式碼中要做的就是取出偶數位跟奇數位、分別求他們的和然後相減，看是不是 0。

這樣寫好像比較麻煩，所以可以換個思路，每個偶數位跟奇數位一加一減也可以做到判斷 11 倍數的事情。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>

using namespace std;

bool isMultipleOf11(const string& num){
    int sum = 0;
    for (size_t i = 0; i < num.size(); ++i){
        int digit = num[i] - '0'; // 把字串轉整數，用 stoi() 也可以
        if (i % 2 == 0) sum += digit;
        else sum -= digit;
    }
    return sum % 11 == 0;
}

int main(){
    string num;
    while (cin >> num && num != "0"){
        cout << num << ( isMultipleOf11(num) ? " is a multiple of 11." : " is not a multiple of 11.");
        cout << '\n';
    }
    return 0;
}

6. Bangla Numbers

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

zerojudge：https://zerojudge.tw/ShowProblem?problemid=a741

題目翻譯：

孟加拉數字一般都用 ‘kuti’ (10000000), ‘lakh’ (100000), ‘hajar’ (1000), ‘shata’ (100) 來展開並轉換為文字。你要撰寫一個程式，將給定的數字轉換為包含這些單位的文字。

輸入說明：

輸入檔案可能包含多個測試案例。每個案例將包含一個非負數，且不大於 999999999999999。

輸出說明：

對於每個輸入案例，你必須輸出一行，以四位數調整的案例編號開始，後接轉換後的文字。

解題思路：

可以發現題目的 9 有 15 位數，而 long long 可以處理到 19 位數，所以可以直接用 long long 做。

另外可以從輸入測資 2 45897458973958 發現，輸出結果是 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58。

這個有點像程式溢位（overflow）的概念，但他是單位用完後，回到最小單位，繼續往上表示有多少個 45 kuti 89 lakh 73 hajar 9 shata 58，如上範例測資就是 45 lakh 89 hajar 7 shata 個的 45 kuti 89 lakh 73 hajar 9 shata 58。

那這部份我們可以拆解成兩個部份來做，分別是「高位數的 kuti 部分」跟「低位數的剩餘部分」。

高位數的 kuti 部分就是 45897458973958 / 10000000 後的結果，也就是 45 kuti 89 lakh 73 hajar 9 shata 58 。

低位數就是 45897458973958 % 10000000 後的結果，表示 kuti 前面需要用較小的單位去表示。

高位數就用遞迴優先處理，低位數的最後再處理，於是請看範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

void printBangla(long long n) {
    if (n >= 10000000) {
        printBangla(n / 10000000);
        cout << " kuti";
        n %= 10000000;
    }
    if (n >= 100000) {
        printBangla(n / 100000);
        cout << " lakh";
        n %= 100000;
    }
    if (n >= 1000) {
        printBangla(n / 1000);
        cout << " hajar";
        n %= 1000;
    }
    if (n >= 100) {
        printBangla(n / 100);
        cout << " shata";
        n %= 100;
    }
    if (n > 0) {
        cout << " " << n;
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    long long num;
    int caseNum = 1;
    
    while (cin >> num) {
        cout << setw(4) << caseNum++ << ".";
        if (num == 0) {
            cout << " 0";
        } else {
            printBangla(num);
        }
        cout << '\n';
    }
    return 0;
}

7. List of Conquests

PDF Source：https://onlinejudge.org/external/104/10420.pdf

zerojudge：https://zerojudge.tw/ShowProblem?problemid=a743

題目翻譯：

在第一幕中，Leporello 向 Donna Elvira 述說著有關他主人長長的征服名單：

「這是我主人所愛的美女名單，是我親自整理的：來看吧，跟我一起讀。在義大利（Italy）有 640 位，在德國（Germany）有 231 位，100 位在法國（France），91 位在土耳其（Turkey）；但在西班牙（Spain）已有 1003 位！其中有鄉村女孩、女僕、城市美人；還有伯爵夫人、男爵夫人、侯爵夫人、公主：各個階層、各個身材、各個年齡的女性。」

（Madamina, il catalogo è questo）

由於 Leporello 按時間順序紀錄了 Don Giovanni 「愛過」的「美女」，他每次向他人展示主人的征服成果時都感到非常麻煩，因為他需要按國籍逐一計算「美女」的數量。你需要幫助 Leporello 進行計數。

輸入說明：

輸入最多包含 2000 行，但首行除外。首行包含一個數字 n，表示接下來還有 n 行。每行最多 75 個字元，包含一個國家名稱（首個單詞）和 Giovanni 所愛的女性的名字（該行其餘單詞）。你可以假設所有國家名稱僅由一個單字組成。

輸出說明：

輸出包含按字母順序排列的行。每行以國家名稱開頭，後跟 Giovanni 在該國愛過的女性總數，兩者之間以空格分隔。

精選單字：

  • conquest (n.) 征服；性玩物
  • maid (n.) （飯店的）女服務員；（家中的）女傭，女僕，侍女
    • 女孩，少女，（未婚的）年輕女子
  • countess (n.) 女伯爵；伯爵夫人
  • baroness (n.) 女男爵；男爵夫人
  • marchioness (n.) （英國）侯爵夫人；女侯爵
  • chronological (adj.) 按事件發生的年代順序排列的
  • troublesome (adj.) 令人煩惱的；討厭的；麻煩的
  • nationality (n.) 國籍；民族

解題思路：

首先看到國家映射數字，就知道要用 map 或 unordered_map，因為題目要求輸出用字母順序，所以用 map 會比較方便。

有個蠻取巧的方法，就是可以透過 cin 只讀前面的字元，然後到空格就不讀了嘛對不對，之後再用 getline() 把後面的都吃掉就好。

範例程式碼：

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
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    map<string, int> countries;

    for (int i = 0; i < n; ++i) {
        string country;
        cin >> country;
        
        string line;
        getline(cin, line);
        
        countries[country]++;
    }

    for (const auto& [x, y] : countries){
        cout << x << " " << y << '\n';
    }

    return 0;
}

8. What’s Cryptanalysis?

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

zerojudge：https://zerojudge.tw/ShowProblem?problemid=c044

密碼分析（Cryptanalysis）是破解他人密文的過程。這有時涉及對一段（加密）文字進行某種統計分析。你的任務是撰寫一個程式，對給定的文字進行簡單的分析。

精選單字：

  • cryptanalysis (n.) 密碼分析、密碼破譯
  • else’s 別人的、他人的
  • encrypt (v.) 將…譯成密碼；把…編碼；把…加密

解題思路：

建 counts 整數陣列，表示字母出現的次數。

題目範例測資有非字母字元，所以要判斷是不是字母 isalpha(ch)。

後續處理字母時，先將所有字母轉成大寫或小寫（tolower() or toupper()）用 ASCII 碼特性去求出 A-Z 的位置（數字）：counts[ch - 'A']++;。 ‘A’ 根據你填了什麼函數去做調整。

之後建一個 vector<pair<char, int>> freq 用來存字母與出現頻率的映射表。

為什麼不用 map？因為題目要求出現頻率由大到小的排序，而 map 只能對 key 做排序，身為 value 的 int 就不行。

範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    cin.ignore();
    int counts[26] = {0};
    for (int i = 0; i < n; ++i){
        string line;
        getline(cin, line);
        
        for (char& ch : line){
            if (isalpha(ch)){
                ch = toupper(ch);
                counts[ch - 'A']++;
            }
        }
        
    }
    
    vector <pair<char, int>> freq;
    for (int i = 0; i < 26; ++i){
        if (counts[i] > 0){
            freq.push_back({char('A' + i), counts[i]});
        }
    }
    
    sort(freq.begin(), freq.end(), [](const pair<char, int>& a, const pair<char, int>& b){
        if (a.second != b.second)
            return a.second > b.second;
        else
            return a.first < b.first;
    });
    
    for (auto [x, y] : freq){
        cout << x << " " << y << '\n';
    }
    
    return 0;
}

9. Decode the Mad man

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

zerojudge：https://zerojudge.tw/ShowProblem?problemid=e578

題目翻譯：

曾經在BUET，有一位老教授完全瘋了。他開始用一些奇怪的詞語說話。沒有人能聽懂他的演講跟課堂內容。最後，BUET 當局陷入了極大的困境。已經沒有辦法讓那個人繼續留在在大學裡了。突然有一位學生（他肯定是 UVA ACM 章節的註冊作者，並且在 24-hours Online Judge 中有很好的排名）建立了一個能夠解碼那位教授說的話的程式。他的發明出現之後，大家再次感到安心，那位老教授也恢復了日常的教學工作。

所以，如果你有一天參觀 BUET，看到一位老師對著麥克風講話，而麥克風連接著一台配有語音識別軟體的IBM 電腦，學生們正從電腦螢幕上聽課，請不要驚訝！因為現在你的任務就是寫出同樣能解碼那位瘋狂老師語音的程式！

精選單字：

  • peculiar (adj.) 奇怪的；古怪的；獨特的
  • thunder (n.) 雷（聲）
    • (v.) 打雷、怒吼
    • 在此作為「驚嚇、嚇到」，我想應該是比喻打雷的那種聲響會讓人嚇到那樣。

解題思路：

我們正常用的鍵盤佈局如下：

1
2
3
4
` 1 2 3 4 5 6 7 8 9 0 - =
q w e r t y u i o p [ ] \
a s d f g h j k l ; '
z x c v b n m , . /

如果是 k，則往左移兩位得到 h，剩下以此類推。

  1. 建立一個 keyboard 字串，就是鍵盤上所有字元，依序排列（空格跟換行不在裡面）。
  2. 輸入的每個字元，根據在這個字串裡面往左移兩位，取出來。
  3. 空白和換行直接輸出。

字元處理部分，可用 string.find() 去找這個字元在 keyboard 字串的位置，然後位置 - 2 輸出。

2025/09/23 勘誤：未判斷書入測資可能有大寫字元，因此加上 isalpha() 判斷。

範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

int main(){
    string key = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
    string line;
    while (getline(cin, line)){
        for (char& ch : line){
            if (isalpha(ch)){
                ch = tolower(ch);
            }
            if (ch == ' ' || ch == '\n'){
                cout << ch;
            }
            else{
                size_t pos = key.find(ch);
                if (pos >= 2){
                    cout << key[pos - 2];
                }
            }
        }
        cout << '\n';
    }
    return 0;
}

10. Summing Digits

PDF Source：https://onlinejudge.org/external/113/11332.pdf

zerojudge：https://zerojudge.tw/ShowProblem?problemid=c813

題目翻譯：

對於所有正整數 n，令 $f(n)$ 表示 n 在十進位表示時各位十進位數字的總和。可以很容易就看到，數列 $n, f(n), f(f(n)), f(f(f(n))), \cdots$ 最終會變成一個單一數字，且這數字會永遠重複下去。令這個個位數字記為 $g(n)$ 。

如考慮 $n = 1234567892$ ，則：

因此， $g(1234567892) = 2$ 。

解題思路：

這個一看就是遞迴了，具體請見範例程式碼：

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

using namespace std;

int g(long long n){
    if (n < 10) return n;
    int sum = 0;
    while (n > 0){
        int digit = n % 10;
        sum += digit;
        n /= 10;
    }
    return g(sum);
}

int main(){
    long long n;
    while (cin >> n && n){
        cout << g(n) << '\n';
    }
    return 0;
}