【Uva 題庫解題】C++ 個人解題筆記（一顆星選集） - part 1
===
[TOC]
一篇十題讓你看到爽！
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 的家，因此總距離為：
$$\sum^r_{i - 1} |x - s_i|$$
這題的重點是 $x$ 要取什麼，直接說結論好了，就是取中位數。
為什麼是中位數？這就需要會一點微分的概念去做數學證明了。
但是本系列僅止於解題，這部分不多贅述，反倒是有個方法能夠直覺地看出為什麼是中位數：
假設其中一個輸入測資是 `[1, 2, 4, 8, 10]`，此時我們將這些數字一個個代入上面那個公式，即可列表：
| x 值 | 總距離 |
|------|------------------------------|
| 1 | 0+1+3+7+9 = 20 |
| 2 | 1+0+2+6+8 = 17 |
| 4 | 3+2+0+4+6 = 15 |
| 8 | 7+6+4+0+2 = 19 |
| 10 | 9+8+6+2+0 = 25 |
唉呦，可以發現在中位數的地方就是最小值 15。
如果你不信的話，可以拿範例測資來試試看：
`2 4`
| x 值 | 總距離 |
| -------- | -------- |
| 2 | 0 + 2 = 2 |
| 4 | 2 + 0 = 2 |
`2 4 6`
| x 值 | 總距離 |
| -------- | -------- |
| 2 | 0 + 2 + 4 = 6 |
| 4 | 2 + 0 + 2 = 4 |
| 6 | 4 + 2 + 0 = 6 |
`1 2 5 9999`
| x 值 | 總距離 |
| -------- | -------- |
| 1 | 0 + 1 + 4 + 9998 = 10003 |
| 2 | 1 + 0 + 3 + 9997 = 10001 |
| 5 | 4 + 3 + 0 + 9994 = 10001 |
| 9999 | 9998 + 9997 + 9994 = 29989 |
範例程式碼：
```cpp=
#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。
範例程式碼：
```cpp=
#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。
範例程式碼：
```cpp=
#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.) 推測、猜測。
範例程式碼：
```cpp=
#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 倍數的事情。
範例程式碼：
```cpp=
#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 前面需要用較小的單位去表示。
高位數就用遞迴優先處理，低位數的最後再處理，於是請看範例程式碼：
```cpp=
#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() 把後面的都吃掉就好。
範例程式碼：
```cpp=
#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 就不行。
範例程式碼：
```cpp=
#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 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 輸出。
範例程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
string keyboard = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
string line;
while (getline(cin, line)){
for (const char& ch : line){
if (ch == ' ' || ch == '\n'){
cout << ch;
}
else{
size_t pos = keyboard.find(ch);
// string::npos 表示 find() 找不到
// 這個其實不用加，因為測資保證有一個或多個單字
if (pos != string::npos && pos >= 2){
cout << keyboard[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$ ，則：
$$f(n) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 2 = 47$$
$$f(f(n)) = 4 + 7 = 11$$
$$ f(f(f(n))) = 1 + 1 = 2$$
因此， $g(1234567892) = 2$ 。
解題思路：
這個一看就是遞迴了，具體請見範例程式碼：
```cpp=
#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;
}
```
Sign in with Wallet
Connect another wallet