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

一篇十題讓你看到爽！

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

41. Tell me the frequencies!

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

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

題目翻譯：

給定一行文字，你要找出 ASCII 字元出現的頻率。給定的行將不包含前 32 個或後 128 個 ASCII 字元。當然，行可以 \n 和 \r 結尾，但永遠不要考慮這些字元。

注意點：

不要用 cin，用 getline()，題目輸入測資可能一行含有空格。

map 用完後轉成 vector <pii>，依據題目要求做自訂排序。

範例程式碼：

2025/09/29 修改：改為若非第一組測資就輸出空行，避免 Presentations-Error。

2025/09/29 二改：在 for(char c : s) 的部分需額外判斷 if (ascii >= 32 && ascii <= 127 && ascii != 13 && ascii != 10)，這樣才能在瘋狂程設中通過。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    bool first = true;
    
    while (getline(cin, s)) {
        if (!first) {
            cout << "\n";
        }
        first = false;
        
        map<int, int> freq;
        
        for (char c : s) {
            int ascii = (int)c;
            if (ascii >= 32 && ascii <= 127 && ascii != 13 && ascii != 10) {
                freq[ascii]++;
            }
        }
        
        vector<pair<int, int>> result(freq.begin(), freq.end());
        
        sort(result.begin(), result.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.second != b.second) {
                return a.second < b.second;
            }
            return a.first > b.first;
        });
        
        for (const auto& p : result) {
            cout << p.first << " " << p.second << "\n";
        }
    }
    
    return 0;
}

42. Train Swapping

PDF Source：https://onlinejudge.org/external/2/299.pdf

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

題目翻譯：

在一個老舊的火車站，你或許仍會遇到最後幾位「列車交換員」之一。列車交換員是鐵路公司的員工，他們唯一的工作就是重新排列火車的車廂。

一旦車廂按照最佳順序排列好，列車司機所需做的就是依序將車廂卸下，按照目的地一個接一個地卸貨。

「列車交換員」這個名稱源自於第一位執行這項任務的人，他在靠近鐵路橋的一個車站工作。那座橋不是垂直升起，而是繞著河中央的一根柱子旋轉。當橋旋轉 90 度時，船隻可以從左邊或右邊通過。

第一位列車交換員發現，該橋最多可以承載兩節車廂。當橋旋轉 180 度時，兩節車廂的位置就會對調，使他能重新排列車廂（順帶一提，車廂在此過程中會面對相反方向，但車廂無論面向哪邊都能行駛，所以這沒差）。

如今，幾乎所有的列車交換員都已經逐漸消失了，鐵路公司希望能將此作業自動化。你要撰寫的一部分程式，是一個用來判斷某列火車需進行最少次數的相鄰車廂交換，以使車廂順序排列正確的程式。你的任務就是建立這個例程。

精選單字：

• carriage (n.) 車廂、貨運
• stem from something (phr. v.) 源自;由…造成
• pillar (n.) （建築物的）柱子，支柱;墩
• died out (phr v.) 逐漸消失；滅絕
• adjacent (adj.) 鄰近的

解題思路：

其實就是泡沫排序法在交換的時候，就用變數 count++。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int bubble_sort(vector<int>& arr){
    int count = 0;
    int n = arr.size();
    
    for (int i = 0; i < n - 1; ++i){
        for (int j = 0; j < n - 1 - i; ++j){
            
            if (arr[j] > arr[j + 1]){
                swap(arr[j], arr[j + 1]);
                count++;
            }
            
        }
    }
    
    return count;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    for (int i = 0; i < N; ++i){
        
        int L;
        cin >> L;
        
        vector <int> num(L);
        for (int j = 0; j < L; ++j){
            cin >> num[j];
        }
        
        cout << "Optimal train swapping takes " << bubble_sort(num) << " swaps." << "\n";
    }
    return 0;
}

43. Hardwood Species

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

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

題目不翻譯，好長。

重點就是那一句話：（From Lucky貓）美國國家資源局使用衛星影像技術來調查森林中的樹種，你的任務就是根據輸入的樹木名稱，計算各樹種所佔的百分比。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n;
    string line;
    getline(cin, line);
    n = stoi(line);
    getline(cin, line);
    
    for (int i = 0; i < n; ++i){
        map <string, int> count;
        int total = 0;
        
        while (getline(cin, line)){
            if (line.empty()) break;
            count[line]++;
            total++;
        }
        
        for (auto &p : count){
            cout << fixed << setprecision(4);
            cout << p.first << " " << (p.second * 100.0 / total) << "\n";
        }
        
        if (i != n - 1){
            cout << "\n";
        }
        
    }
    return 0;
}

44. Minesweeper

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

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

題目翻譯：

你有玩過踩地雷（Minesweeper）嗎？這是款可愛的小遊戲，曾內建於某個作業系統裡，但我們記不太得是哪個了。嗯，這款遊戲的目標是找出一個 $M \times N$ 區域中所有地雷的位置。為了幫你，遊戲會在某些格子中顯示數字，告訴你相鄰格子中有多少地雷。例如，考慮以下這個 $4 × 4$ 的區域，其中有 $2$ 顆地雷（以 * 字元表示）：

*...
....
.*..
....

若我們以提示數字的方式來表示這個區域，結果會是：

*100
2210
1*10
1110

如你可能已經注意到的，每一格最多可能有 $8$ 個相鄰的格子。

精選單字：

• come within (phr.) 隨…附帶在其中。

解題思路：

可用一個 vector <int> result 去存要輸出的地圖。

再來這 8 個相鄰的格子，就是上下左右、各斜角一個單位：

(-1, -1)  (-1, 0)  (-1, +1)
( 0, -1)  ( 0, 0)  ( 0, +1)
(+1, -1)  (+1, 0)  (+1, +1)

當前格 $(x,y)$ 相鄰座標為 $(x+dx[i], y+dy[i])$ ，其中 $dx$ 、 $dy$ 分別為以上圖示的偏移量。

然後整理一下要設哪些變數：

• int n, m; 地圖大小
• int field_num = 1; 輸出格式用
• int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; x 軸偏移量（不一定照這個填，順序不一樣皆可）
• int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; y 軸偏移量（不一定照這個填，順序不一樣皆可）

最後最重要的就是暴力解的邏輯了：

（計算每格周圍地雷數目）

遍歷地圖每一格 $(i,j)$ ：

• 若為空格「.」，需計算周圍 8 個方格中「*」的數量。
  • 遍歷 8 格鄰格方向。
    • 邊界檢查 ( 0 ≤ nx < n && 0 ≤ ny < m )。
    • 若鄰格為「*」 -> count++。
    • count 轉 char，存入 result。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n, m;
    int field_num = 1;
    
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    while (cin >> n >> m && (n != 0 && m != 0)){
        vector <string> field(n);
        
        for (int i = 0; i < n; ++i){
            cin >> field[i];
        }
        
        vector <string> result = field;
        
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (field[i][j] != '*'){
                    int count = 0;
                    for (int dir = 0; dir < 8; ++dir){
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];
                        if (nx >= 0 && nx < n && ny >=0 && ny < m){
                            if (field[nx][ny] == '*'){
                                count++;
                            }
                        }
                    }
                    result[i][j] = count + '0';
                }
            }
        }
        
        if (field_num > 1){
            cout << "\n";
        }
        
        cout << "Field #" << field_num++ << ":\n";
        
        for (const string& s : result){
            cout << s << "\n";
        }
        
    }
    
    return 0;
}

45. Die Game

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

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

題目翻譯：

人生並不容易，有時甚至會超出你的掌控之中。現在，作為 ACM ICPC 的參賽者，你們或許正嘗到人生的苦澀。但別擔心！不要只看人生黑暗的一面，也要看看光明的一面。人生也許是一場充滿樂趣的機遇遊戲，就像擲骰子一樣。要嘛拚到底，要嘛一敗塗地！最終，你也許能找到通往勝利的道路。

這個問題源自一個使用骰子的遊戲。順帶一提，你知道 “die” 是什麼嗎？它跟「死亡（death）」無關。 “die” 是指一個立方體形狀的物體，有六個面，每個面代表一個從一到六的不同數字，並標記有相對應數量的點。由於通常是成對使用，因此單數形「a die」較少見。不過，你可能聽過一句著名的話：「the die is cast（骰子已擲下→引申為木已成舟、大局已定）」。

當遊戲開始時，骰子靜止地放在平坦的桌面上。遊戲過程中，骰子會被莊家往各個方向滾動。如果你能預測當骰子停止滾動時，頂部所顯示的數字，那你就能贏得這場遊戲。

現在，你的任務是撰寫一個模擬骰子滾動的程式。為了簡化，我們假設骰子不會滑動也不會跳動，只會在桌面上朝四個方向（北、東、南、西）滾動。每局遊戲開始時，莊家將骰子放在桌子的中心，並將其方向調整為：1 號數字朝上（頂面）、2 號數字朝北（北面）、3 號數字朝西（西面）。至於另外三個面的數字，雖未明確指定，但你要記住一個黃金法則：任兩個對面上的數字總和恆為 7。

你的程式應該接受一連串的指令，每個指令為 “north”、 “east”、 “south” 或 “west” 其中之一。指令 “north” 表示骰子朝北滾動，即頂面會變成新的北面，北面變成新的底面，依此類推。更精確地說，骰子會繞著其北邊的底緣旋轉 90 度，向北方向滾動。其他指令亦會根據其方向對骰子進行相應的滾動。你的程式應該計算出執行完所有指令後，頂面所顯示的數字為多少。請注意，桌面足夠大，遊戲期間骰子絕不會掉落桌面外。

解題思路：

題目其實沒有很難，需要靠你的腦袋去想像模擬的情形。

骰子有六面，題目給以下三面了初始狀態：

• 頂面（Top）：1
• 北面（North）：2
• 西面（West）：3

根據上述的黃金法則，每對對面的總和為 7，因此可推算出以下的完整表：

位置	數字
top	1
bottom	6
north	2
south	5
west	3
east	4

在這邊程式設計上，用六個變數（top, bottom, north, south, west, east）去指定每個方位的初始狀態。

四個方位滾動的情況如下：

1. 向北滾 north

在腦中想一下，一顆骰子向北滾的話，是不是就是北面朝底面，南面朝頂面？

然後東西兩個方位是不變的，因此只有四個面需要更動。

這時候就可以寫下以下的程式：

if (command == "north"){
    temp = top;
    top = south;
    south = bottom;
    bottom = north;
    north = temp;
}

1. 向南滾 south

向南滾的情況就相反了，變成北面朝頂面，南面朝底面。

1. 向西滾 west

向西的話，要變的方位也是一樣四面，top、bottom、west、east，然後是西面朝底面、東面朝頂面。

1. 向東滾 east

與 3. 相反。

範例程式碼：

#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 top = 1;
        int bottom = 6;
        int north = 2;
        int south = 5;
        int west = 3;
        int east = 4;
        
        for (int i = 0; i < n; ++i){
            string cmd = "";
            cin >> cmd;
            int temp;
            if (cmd == "north"){
                temp = top;
                top = south;
                south = bottom;
                bottom = north;
                north = temp;
            }
            else if (cmd == "south"){
                temp = top;
                top = north;
                north = bottom;
                bottom = south;
                south = temp;
            }
            else if (cmd == "west"){
                temp = top;
                top = east;
                east = bottom;
                bottom = west;
                west = temp;
            }
            else{
                temp = top;
                top = west;
                west = bottom;
                bottom = east;
                east = temp;
            }
        }
        
        cout << top << '\n';
    }
    return 0;
}

46. Eb Alto Saxophone Player

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

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

題目翻譯：

你喜歡薩克斯風嗎？我有個降 E 中音薩克斯風，如圖所示。

當我彈奏某些音樂時，我的手指會大幅度地移動，我對每根手指按下按鍵的次數感到相當有興趣。假設這段音樂僅由 8 種音符組成，分別是：C D E F G A B 在一個八度，以及 C D E F G A B 在更高一個八度。我們用 c, d, e, f, g, a, b, C, D, E, F, G, A, B 來表示這些音符。

我對每個音符使用的手指如下：

• c：第 2∼4 指、第 7∼10 指
• d：第 2∼4 指、第 7∼9 指
• e：第 2∼4 指、第 7、8 指
• f：第 2∼4 指、第 7 指
• g：第 2∼4 指
• a：第 2、3 指
• b：第 2 指
• C：第 3 指
• D：第 1∼4 指、第 7∼9 指
• E：第 1∼4 指、第 7、8 指
• F：第 1∼4 指、第 7 指
• G：第 1∼4 指
• A：第 1∼3 指
• B：第 1∼2 指

（請注意，每根手指對應特定的按鍵，不同手指控制不同的按鍵。）

請撰寫一個程式來協助計算每根手指按下按鍵的次數。當某音符需要使用某手指，而該手指在前一個音符中未被使用時，則該手指需按下按鍵一次。此外，若該音符是整首曲子的第一個音符，則所有該音符需要的手指都會各按下一次。

解題思路：

建一個 map 映射表，音高對應第幾根手指。

因為可能會有空的輸入，所以保險起見用 cin.ignore() + getline(cin, line)。

每次迴圈中初始化 int press_count[10] bool prev_pressed[10]，一個是紀錄手指按壓的次數，一個是前一音高的手指是否按壓。

另外遍歷每個音高的時候，也初始化一個 array bool curr_pressed[10]，表示目前音高的手指是否按壓。

最後更新 prev_pressed = curr_pressed。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    map <char, set<int>> finger_map = {
        {'c', {2, 3, 4, 7, 8, 9, 10}},
        {'d', {2, 3, 4, 7, 8, 9}},
        {'e', {2, 3, 4, 7, 8}},
        {'f', {2, 3, 4, 7}},
        {'g', {2, 3, 4}},
        {'a', {2, 3}},
        {'b', {2}},
        {'C', {3}},
        {'D', {1, 2, 3, 4, 7, 8, 9}},
        {'E', {1, 2, 3, 4, 7, 8}},
        {'F', {1, 2, 3, 4, 7}},
        {'G', {1, 2, 3, 4}},
        {'A', {1, 2, 3}},
        {'B', {1, 2}}
    };
    
    int t;
    cin >> t;
    
    cin.ignore();
    
    for (int i = 0; i < t; ++i){
        string line;
        getline(cin, line);
        
        int press_count[10] = {0};
        bool prev_pressed[10] = {false};
        
        for (char c : line){
            bool curr_pressed[10] = {false};
            
            for (int f : finger_map[c]){
                curr_pressed[f - 1] = true;
                
                if (!prev_pressed[f - 1]){
                    press_count[f - 1]++;
                }
            }
            
            for (int i = 0; i < 10; ++i) {
                prev_pressed[i] = curr_pressed[i];
            }
        }
        
        for (int j = 0; j < 10; ++j){
            cout << press_count[j];
            if (j != 9) cout << " ";
        }
        
        cout << "\n";
    }
    
    return 0;
}

47. Mutant Flatworld Explorers

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

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

題目翻譯：

機器人學、機器人運動規劃，以及機器學習是跨越許多電腦科學子領域的研究領域：人工智慧、演算法與複雜度、電機與機械工程等僅是其中幾個範疇。此外，機器人如「烏龜」（靈感來自 Papert、Abelson 與 diSessa 的作品）以及“beeper-pickers”（靈感來自 Pattis 的作品）長年被學生作為程式設計的入門學習主題。

本題目涉及一個問題：確定探索前哥倫布時代平坦世界的機器人的位置。

給定一個矩形網格的尺寸，以及一連串機器人位置與指令，請撰寫一個程式來決定每個機器人初始位置與指令序列之後的最終位置。

一個機器人的位置由格子座標（一對整數：x 座標接著是 y 座標）以及方向（N, S, E, W，分別代表北、南、東、西）所組成。一個機器人的指令是一串由字母 ‘L’、’R’ 和 ‘F’ 組成的字串，分別代表下列操作：

• 左轉 (Left)：機器人左轉 90 度，並停留在目前的格子。
• 右轉 (Right)：機器人右轉 90 度，並停留在目前的格子。
• 前進 (Forward)：機器人往目前朝向的方向前進一格，方向不變。

方向 北 (North) 對應從格點 (x, y) 移動到格點 (x, y + 1) 的方向。

由於網格是矩形且有邊界，若機器人「移出」網格邊界，將會永久消失。然而，迷失的機器人會留下「氣味」（scent），防止未來的機器人從同一格、同一方向掉出世界。這個氣味會留在機器人消失前的最後一個位置上。若後來的機器人試圖從一個先前已經讓其他機器人迷失的位置往相同方向移出邊界，這樣的「移出」指令將會被忽略，機器人停留在原地。

精選單字：

• subdiscipline (n.) 子學科
• comprise (v.) 包含、包括；構成、組成
• to name a few (phr.) 舉例來說、不勝枚舉
• dimension (n.) 空間；尺度；維度
• respectively (adv.) 分別地

注意點：

左轉就是 (direction - 1) % 4，但是寫負數會有問題，換個思路，直接把 - 1 + 4 變成正數，
寫成 (direction + 3) % 4。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int max_x, max_y;
    cin >> max_x >> max_y;
    
    vector <vector <bool>> scent(max_x + 1, vector<bool>(max_y + 1, false));
    
    char dir_chars[] = {'N', 'E', 'S', 'W'};
    // N = 0, E = 1, S = 2, W = 3
    int dx[] = {0, 1, 0, -1}; // 對應向東 x + 1, 向西 x - 1
    int dy[] = {1, 0, -1, 0}; // 對應向上 y + 1, 向南 y - 1
    
    int x, y;
    char dir;
    string cmds;
    
    while (cin >> x >> y >> dir >> cmds){
        int direction;
        
        if (dir == 'N') direction = 0;
        else if (dir == 'E') direction = 1;
        else if (dir == 'S') direction = 2;
        else direction = 3;
        
        bool lost = false;
        
        for (char cmd : cmds){
            if (lost) break;
            
            if (cmd == 'L'){
                direction = (direction + 3) % 4;
            }
            else if (cmd == 'R'){
                direction = (direction + 1) % 4;
            }
            else{
                int nx = x + dx[direction];
                int ny = y + dy[direction];
                
                if (nx < 0 || nx > max_x || ny < 0 || ny > max_y){
                    if (!scent[x][y]){
                        lost = true;
                        scent[x][y] = true;
                    }
                }
                else{
                    x = nx;
                    y = ny;
                }
            }
        }
        
        cout << x << " " << y << " " << dir_chars[direction];
        if (lost) cout << " LOST";
        cout << "\n";
    }
    
    return 0;
}

48. Cola

PDF Source：https://onlinejudge.org/external/111/11150.pdf

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

題目翻譯：

你在便利商店看到以下特別優惠：

「每歸還 3 個空瓶，即可兌換 1 瓶 Choco Cola」

現在你決定從商店購買一些可樂（假設是 N 瓶）。你想知道該怎麼做才能從中獲得最多的可樂。

以下圖示說明 N = 8 的情況。方法一是標準做法：喝完你買的 8 瓶可樂後，你會有 8 個空瓶。拿其中 6 個去兌換，你可以得到 2 瓶新的可樂。喝完後你有 4 個空瓶，再拿其中 3 個去換，可再得到 1 瓶可樂。最後你剩下 2 個空瓶，已無法再兌換新可樂。因此你總共喝了 8 + 2 + 1 = 11 瓶可樂。

但其實你可以做得更好！在方法二中，你一開始向朋友（？！還是店員？？）借一個空瓶，這樣你就可以兌換成 3 瓶新可樂。如此一來你總共喝了 8 + 3 + 1 = 12 瓶可樂！當然，最後你需要將剩下的空瓶歸還給你的朋友。

精選單字：

• following (prep.) 在…之後
• the following 接下來，下面的（常用於引出名單、報告等）

解題思路：

寫兩個方法的函數，然後取兩個回傳值比大小。

方法 1 的函數設計：

設兩變數 total, empty，分別表示喝了幾瓶、有幾個空瓶，起始值都是 n。

然後我們跑一個 while (empty >= 3)，內部設一個變數 exchange = empty / 3，表示換到幾個可樂。

接下來就把這些可樂給喝完： total += exchange。

最後更新 empty = empty % 3 + exchange，這部分是換完換得的空瓶數+剩餘的空罐子。（具體請看題目圖示，method 1 蠻清楚的了）

方法 2 的函數設計：

基本上跟 method 1 類似，total, empty 都是 n + 1，因為要跟「朋友」借一瓶嘛XD，只是差別是最後 return total 的時候要 - 1，把借的還回去。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int maxCola(int n){
    int total = n;
    int empty = n;
    
    while (empty >= 3){
        int exchange = empty / 3;
        total += exchange;
        empty = empty % 3 + exchange;
    }
    
    return total;
}

int maxCola_empty_cola(int n){
    int total = n + 1;
    int empty = n + 1;
    
    while (empty >= 3){
        int exchange = empty / 3;
        total += exchange;
        empty = empty % 3 + exchange;
    }
    
    return total - 1;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n;
    while (cin >> n){
        int normal = maxCola(n);
        int borrow = maxCola_empty_cola(n);
        cout << max(normal, borrow) << '\n';
    }
    return 0;
}

49. Sort! Sort!! and Sort!!!

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

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

題目翻譯：

嗯！這是一個簡單的排序問題。你會得到 $N$ 個數字和一個正整數 $M$ 。你必須根據這 $N$ 個數字對 $M$ 取模（modulo）後的結果，依升序排列它們。

如果有兩個數對 $M$ 取模後的結果相同，且其中一個是奇數、一個是偶數，那麼奇數會排在偶數前面。

• 如果兩個數都是奇數且模值相同，則數值較大的奇數會排在前面。
• 如果兩個數都是偶數且模值相同，則數值較小的偶數會排在前面。

對於負數的餘數（modulo）運算，請遵循 C 語言的規則：負數的模值永遠不會大於零。

例如：

• -100 MOD 3 = -1，
• -100 MOD 4 = 0，

依此類推。

精選單字：

• ascending (adj.) （規模、價值等）上升的，增長的
• tie 在這邊指的是相等

解題思路：

這題就是自訂排序，比較函數基本上依照題目需求去設計即可。

基本流程大致如下：

對 a, b 取模，如果兩者不相等，依照結果去做升序，否則→

判斷 a, b 是否為奇數，若有其中之一不是，則奇數在前，否則→

兩者都奇數，降序；否則升序。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a, int b, int M){
    int ma = a % M, mb = b % M;
    
    if (ma != mb) return ma < mb; // 升序 
    
    bool a_odd = (a % 2 != 0);
    bool b_odd = (b % 2 != 0);
    
    // 一奇一偶 (假設 b_odd == false)
    if (a_odd != b_odd) return a_odd; // 奇數在前
    
    // 較大奇數在前
    if (a_odd && b_odd) return a > b; // 降序 (由大到小)
    
    // 較小偶數在前
    return a < b; // 升序 (由小到大)
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N, M;
    while (cin >> N >> M){
        if (N == 0 && M == 0){
            cout << "0 0\n";
            break;
        }
        
        vector <int> nums(N);
        for (int i = 0; i < N; ++i){
            cin >> nums[i];
        }
        
        // [M] 讓 lambda 捕捉變數 M, 以便可以用 M 傳入參數
        sort(nums.begin(), nums.end(), [M](int a, int b){
            return cmp(a, b, M);
        });
        
        cout << N << " " << M << "\n";
        for (int x : nums){
            cout << x << "\n";
        }
    }
    return 0;
}