【Uva 題庫解題】CPE 二顆星選集 - part1

本筆記及該系列主要以每篇 5 題為主，也僅供筆者個人學習用途，斟酌參考。

若你喜歡本筆記，不妨為文章按下一顆愛心，或是追蹤我的個人公開頁，感謝您點入本篇筆記。

CPE 二顆星選集來源：https://par.cse.nsysu.edu.tw/~advprog/star.php

Uva 151 - Power Crisis

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

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

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

該題為約瑟夫問題的變體。

題目架構：

  • 共 NN 個地區（ 11 到 NN ）
  • 地區 11 總是第一個被切斷。
  • 剩下 N−1N-1 個地區，從地區 22 開始，每數到第 mm 個地區就切斷它。
  • 目標：找出最小的 mm，使得地區 13 是最後一個被切斷的。

轉化成約瑟夫問題的形式：

首先由於地區 11 都是第一個被切斷的，只需考慮 N−1N - 1 的地區即可，因此就變成長度為 N−1N - 1 的約瑟夫問題。

另外為方便計算，將地區給重新編號：

  • 地區 2→02 \rightarrow 0
  • 地區 3→13 \rightarrow 1
  • ⋯\cdots
  • 地區 13→1113 \rightarrow 11

這樣就需要找到一個 mm，使得在這 N−1N-1 個人的環中，最後被切斷的索引為 11。

約瑟夫問題公式：$$f(n, m) =
\begin{cases}
0 & \text{if } n = 1 \
(f(n-1, m) + m) % n & \text{if } n > 1
\end{cases}$$

範例程式碼：

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 <iostream>

using namespace std;

int ans(int n, int k){
    int s = 0;
    for (int i = 2; i <= n; ++i){
        s = (s + k) % i;
    }
    return s;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    int N;
    while (cin >> N && N != 0){
        int m = 1;
        while (true){
            int last = ans(N - 1, m);
            if (last == 11){
                cout << m << '\n';
                break;
            }
            m++;
        }
    }
}

Uva 245 - Uncompress

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

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

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

題目翻譯：

有一種用來建立文檔壓縮版本的簡單方法，可用於不包含任何數字字元的檔案。此壓縮方法需要先建立一份「未壓縮檔中出現過的單字」清單。

當在未壓縮檔中遇到非字母字元時，就直接將該字元複製到壓縮檔中。

當在未壓縮檔中遇到一個單字時，只有在該單字第一次出現時，才會將它直接複製到壓縮檔；並在此情況下，把該單字放到清單的最前端。

若不是第一次出現，則不把該單字複製到壓縮檔；改為把它在清單中的位置（編號）寫入壓縮檔，並將該單字移到清單最前端。清單位置的編號從 1 開始。

請撰寫一個程式，輸入為一個壓縮檔，輸出為原本未壓縮檔的還原結果。

解題思路：

基本上就是按照題目要求做事。

  1. 遇到單字時：直接印出該單字，把這個單字放到清單的最上面，原本清單裡的單字全部往後擠一位。
  2. 遇到數字時（如 3）：數字 3 表示到清單裡面去找第 3 個單字，接著把那單字印出來，最重要的是，用完之後要把單字移到清單最上面去。
  3. 遇到標點符號或空格時：直接印出即可。

輸入方式可用 cin.get(ch)，其他方式有可能會將標點符號或空格給讀掉（例如 sstream）。

透過 isalpha() 判斷字元是否為字母，以及 isdigit() 判斷字元是否為數字。

演算法流程（供參）：

  1. 建立一個字串 buffer 以及單字清單 wlist。
  2. 用 cin.get(ch) 一個一個讀入字元。
  3. 判斷為字母 -> buffer += ch。
  4. 判斷為數字 -> buffer += ch。
  5. 以上皆非，則先判斷 buffer 是否為空。
  6. buffer 非空 -> 表示裡面有單字或是數字之類的。
    • 透過 isalpha() 判斷 buffer 開頭是否為字母，得知是否為單字。是的話直接印出，並 wlist.insert(wlist.begin(), buffer) 把單字放到最前面去。
    • 若不是字母，就表示他是一個數字，可用 stoi(buffer) 轉整數，判斷是否為 0，是的話就結束，否則繼續。
    • 若要繼續，則印出 wlist[數字 - 1] 這個單字，接著把它刪了。 wlist.erase(wlist.begin() + (數字 - 1)) ，然後再把單字插入到最前面。
  7. 上述流程跑完後清空 buffer。
  8. 若上述沒有一個條件成立，就表示是標點符號或空格，直接輸出即可：cout << ch。

範例程式碼：

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

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    vector <string> wlist;
    
    char ch;
    string buffer = "";
    
    while (cin.get(ch)){
        if (isalpha(ch)){
            buffer += ch;
        }
        else if (isdigit(ch)){
            buffer += ch;
        }
        else{
            if (!buffer.empty()){
                if (isalpha(buffer[0])){
                    cout << buffer;
                    wlist.insert(wlist.begin(), buffer);
                }
                else{
                    int index = stoi(buffer);
                    
                    if (index == 0) return 0;
                    
                    string s = wlist[index - 1];
                    
                    cout << s;
                    
                    wlist.erase(wlist.begin() + (index - 1));
                    wlist.insert(wlist.begin(), s);
                }
                buffer = "";
            }
            cout << ch;
        }
    }
}

Uva 255 - Correct Move

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

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

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

題目翻譯：

我們有一個 64 個格子的正方形棋盤，從 0 到 63 編號，如圖 1 所示。

有兩個棋子：國王和皇后。國王所在格子與皇后所在格子這一對位置稱之為「國家」（state）。

  • 如果兩個棋子不在同一個格子上，則該狀態是合法的（legal）。
  • 國王與皇后輪流移動。
  • 國王可以在水平方向或垂直方向走一步，只要它不會走到皇后所在的位置。
  • 皇后可以在水平方向或垂直方向走一步或多步，只要它在移動途中不會碰到國王。
  • 所有這些移動都稱為合法移動（legal）。
  • 請注意，棋子不能沿對角線移動。

image

圖 1。

例如，假設我們有一個狀態：國王在第 17 格、皇后在第 49 格，如圖 2 所示。

國王的合法走法可以到第 9、16、18、25 格；而皇后合法地可以走到第 25、33、41、48、50、51、52、53、54、55 或 57 格。

不過，我們另外加上一個額外限制：棋子不可以移動到「另一個棋子也能移動到」的位置。

滿足這個限制的合法走法稱為「允許」（allowed）的走法。

在圖 2 中，國王與皇后各自透過一個允許走法所能到達的所有位置，分別用空心圓（○）與實心點（●）表示。

在圖 3 中，國王不能移動，它被困住了（locked in）。

image

圖 2。

image

圖 3。

此問題要你寫一個程式，對女王的移動進行一些檢查。

解題思路：

一個 8×88 \times 8 棋盤，可以用以下的方法來做表示：

  • r = pos / 8
  • c = pos % 8

接著就是去設計每一個條件的程式：

  1. Illegal state：當 k == q，國王跟皇后在同一格，表示狀態不合法。
  2. Illegal move：皇后走法不合法。
    • q == q2 皇后都沒動，違反「至少動一步」的規則。
    • 判斷是否同列（qr == nr）、同行（qc == nc），若皆非表示是斜著走，因此也不合法。
    • 若同列或同行，沿移動方向（如 step = (nr > qr ? 1 : -1)）一格一格掃過路徑（從下一格開始，含終點），若掃到 k 表示皇后會碰到國王，因此也不合法。
  3. Move not allowed：不能走到國王能走的格子。
    • 若皇后新位置 q2 恰好是國王從 k 出發「上下左右一步」能到的格（即曼哈頓距離為 1），則輸出 Move not allowed。
  4. Continue / Stop：當皇后成功走到 q2（而且是 allowed）後，輪到國王行動，此時要判斷國王是否至少有一個 allowed 的一步。
    • 國王能走的只有四步 (-1,0), (1,0), (0,-1), (0,1)，因此窮舉這幾步。（r = kr + d[0], c = kc + d[1]）
    • 建立 k2 = r*8 + c 表示新狀態的國王。
      1. 檢查 k2 是否出界。
      2. 檢查是否 k2 == q2
      3. 檢查 k2 是否為皇后在 q2 的位置可以走到的格（用 queen_attacks(q2, k, k2) 判斷）
        • 皇后能攻擊/到達的格：同列或同行，且從 q2 走到該格的路徑上不能先撞到國王（國王會擋住皇后的直線）。
      4. 若上述條件皆成立，表示 Stop 國王被卡死了，否則 Continue 國王可繼續走。

範例程式碼：

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>

using namespace std;


bool queen_attacks(int qpos, int kpos, int target){
    if (target == qpos) return false;
    
    int qr = qpos / 8, qc = qpos % 8;
    int tr = target / 8, tc = target % 8;
    
     if (qr == tr){
        int step = (tc > qc ? 1 : -1);
        for (int c = qc + step; c != tc + step; c += step){
            int cur = qr * 8 + c;
            if (cur == kpos) return false;
            if (cur == target) return true;
        }
    } else if (qc == tc){
        int step = (tr > qr ? 1 : -1);
        for (int r = qr + step; r != tr + step; r += step){
            int cur = r * 8 + qc;
            if (cur == kpos) return false;
            if (cur == target) return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int k, q, q2;
    while (cin >> k >> q >> q2){
        if (k == q){
            cout << "Illegal state\n";
            continue;
        }
        
        int kr = k / 8, kc = k % 8;
        int qr = q / 8, qc = q % 8;
        int nr = q2 / 8, nc = q2 % 8;
        
        if (q == q2){
            cout << "Illegal move\n";
            continue;
        }
        
        bool illegal = false;
        
        if (qr == nr){
            int step = (nc > qc ? 1 : -1);
            for (int c = qc + step; c != nc + step; c += step){
                if (qr == kr && c == kc) illegal = true;
            }
        }
        else if (qc == nc){
            int step = (nr > qr ? 1 : -1);
            for (int r = qr + step; r != nr + step; r += step)
                if (qc == kc && r == kr) illegal = true;
        }
        else{
            illegal = true;
        }
        if (illegal){
            cout << "Illegal move\n";
            continue;
        }
        
        if (abs(kr - nr) + abs(kc - nc) == 1){
            cout << "Move not allowed\n";
            continue;
        }
        
        bool allowed = false;
        int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (auto &d : dir){
            int r = kr + d[0], c = kc + d[1];
            
            if (r < 0 || r >= 8 || c < 0 || c >= 8) continue;
            
            int k2 = r*8 + c;
            
            if (k2 == q2) continue;
            if (queen_attacks(q2, k, k2)) continue;
            
            allowed = true;
            break;
        }
        
        cout << (allowed ? "Continue\n" : "Stop\n");
    }
}

Uva 294 - Divisors

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

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

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

題目翻譯：

數學家喜歡研究各種數字的奇特性質。

例如，他們認為 945 是個有趣的數，因為它是第一個其因數總和大於它本身的奇數。

為了幫助他們尋找有趣的數字，你要撰寫一個程式，掃描一段數字範圍，並找出在該範圍內擁有最多因數的數字。

不幸的是，數字本身的大小以及範圍的大小，使得過於簡單的做法可能需要花太多時間才能跑完。

因此，請確保你的演算法足夠聰明，能在短短幾秒內處理最大的可能範圍。

筆者註：Divisors 稱為除數，也稱為我們最熟悉的因數。

解題思路：

要最快計算一個數字 nn 的因數個數，最快的方法是使用「質因數分解」（Prime Factorization）。

假設 nn 的標準分解式為：$$n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$$

則 nn 的因數個數 d(n)d(n) 為：$$d(n) = (a_1 + 1) \times (a_2 + 1) \times \dots \times (a_k + 1)$$

個數就是拿原本質因數的指數來做計算，至於 + 1 部分，則是表示指數的選法（0 ~ aka_k）。

解題步驟：

  1. 建立質數表（用埃拉托斯特尼篩法, Sieve of Eratosthenes）：因為 UU 最大為 10910^9，只需測到 109≈31622\sqrt{10^9} \approx 31622 的質數即可，先預先篩選出 11 到 3200032000 之間的所有質數。
  2. 區間掃描：對每組測資 LL 和 UU，遍歷 ii 從 LL 到 UU。
  3. 計算因數個數：對區間內的每個數字 ii：
    • 用預存的質數表進行試除。
    • 統計每個質因數的冪次（exponent）。
    • 套用公式計算總因數個數。
    • 若試除完所有 ≤i\le \sqrt{i} 的質數後，ii 仍然大於 1，代表剩下的 ii 本身就是一個大質數，因數個數需再乘以 (1+1)=2(1+1)=2。
  4. 找出最大值：若因數個數相同，題目要求輸出較小的那個數。

範例程式碼：

質數篩法優化部分：

1
2
for (int i = p * p; i <= MAXSQRT; i += p)
    is_prime[i] = false;

這段優化目的在於把目前質數 pp 的所有倍數都標記為非質數（false）。

i += p （pp 的倍數）即當找到質數 pp 後，刪掉所有pp 的倍數：2p,3p,4p,…2p, 3p, 4p, \dots 等等。

這樣做的想法是如果 ii 是 pp 的倍數（且 i>pi > p），那 ii 肯定不是質數，因為能被 pp 整除。

int i = p * p：在上層迴圈就將比 p2p^2 小的倍數都篩選過了，因此到這邊從 p2p^2 開始是合理的，不用從頭到尾遍歷一次，縮短耗時。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

using namespace std;

const int MAXSQRT = 32000;

vector <int> prime;

// 埃拉托斯特尼篩法
void sieve(){
    vector <bool> is_prime(MAXSQRT + 1, true);
    
    is_prime[0] = is_prime[1] = false;
    
    for (int p = 2; p * p <= MAXSQRT; ++p){
        if (is_prime[p]){
            for (int i = p * p; i <= MAXSQRT; i += p)
                is_prime[i] = false;
        }
    }
    
    for (int p = 2; p <= MAXSQRT; ++p)
        if (is_prime[p])
            prime.push_back(p);
}

// 數有幾個因數
int countDivisor(int n){
    int total = 1;
    
    for (int p : prime){
        // 若質數平方大於 n 就不用再除
        if (p * p > n) break;
        
        if (n % p == 0){
            int count = 0;
            while (n % p == 0){
                count ++;
                n /= p;
            }
            // 當 n 無法被 p 整除時
            // count 即為 p 的指數
            total *= (count + 1);
        }
    }
    
    if (n > 1) total *= 2;
    
    return total;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    sieve();
    
    int T;
    cin >> T;
    while (T--){
        int L, U;
        cin >> L >> U;
        
        int max_num = -1;
        int max_num_count = -1;
        
        for (int i = L; i <= U; ++i){
            int d = countDivisor(i);
            
            if (d > max_num_count){
                max_num_count = d;
                max_num = i;
            }
        }
        
        cout << "Between " << L << " and " << U << ", " << max_num << " has a maximum of " << max_num_count << " divisors.\n";
    }
}

Uva 337 - Interpreting Control Sequences

PDF Source：https://onlinejudge.org/external/3/337.pdf

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

No Zerojudge

題目翻譯：

幾乎所有的文字模式終端（text-mode terminal）都是專用電腦系統，包含一個序列埠（serial port，用於與數據機或其他電腦系統通訊）、鍵盤、陰極射線管顯示器（CRT，cathode-ray tube），當然還有一顆微處理器（microprocessor）、一些隨機存取記憶體（RAM）與存放控制程式的唯讀記憶體（ROM）。

當一個字元從鍵盤或序列埠送到終端時，終端的軟體會將它分類為要顯示在 CRT 上的顯示字元（display character），或是引入控制序列（control sequence）的字元。控制序列用來指示終端執行特殊動作，例如清除螢幕、以指定方式移動游標，或改變字型等。

在此題中，假設你正在為一個小型終端撰寫軟體，該終端有一個 10 行 × 10 列的顯示（例如用於銷售點終端，point-of-sale terminal）。行（row）與列（column）編號皆為 0 到 9。引入控制序列的字元為「∧」（circumflex，插入符號）。緊接在該控制序列引導字元之後的一個字元（或在一種情況下的兩個字元）會指示你的軟體執行特殊功能。以下為你需要解讀的完整控制序列清單：

∧b
將游標移到當前行的開頭；游標的行（row）不變。

∧c
清除整個螢幕；游標的行與列皆不變。

∧d
若可能，將游標下移一行；游標的列（column）不變。

∧e
擦除游標所在行中游標列及其右側的字元；游標的行與列皆不變。

∧h
將游標移到第 0 行、第 0 列；螢幕內容不改變。

∧i
進入插入模式（insert mode，見下）。

∧l
若可能，將游標左移一列；游標的行不變。

∧o
進入覆寫模式（overwrite mode，見下）。

∧r
若可能，將游標右移一列；游標的行不變。

∧u
若可能，將游標上移一行；游標的列不變。

∧∧
在目前游標位置寫出一個脫字符「∧」，其行為與該字元並非特殊字元時相同；此寫入仍受目前模式（插入或覆寫）的影響。

∧##
將游標移到所指定的行與列；# 代表一個十進位數字；第一個 # 表示新的行號，第二個 # 表示新的列號。

系統保證不會送來非法的控制序列。游標不得移出允許的螢幕位置範圍（亦即介於第 0 行第 0 列到第 9 行第 9 列之間）。

當一個一般字元（非控制序列的一部分）送到終端時，其在螢幕上的顯示方式取決於終端的模式。

當終端處於覆寫模式（開機時即為覆寫模式）時，接收到的字元會取代游標位置處的字元。

若處於插入模式時，游標位置及其右方的字元會整體向右移一列，然後將新字元放在游標位置；游標所在行中最右邊的字元會因此遺失。

無論是哪一種模式，游標都會在可能的情況下向右移一列。

Input

輸入資料將包含多組對你終端軟體的測試。

每一組測試以一行整數 N 開始，接下來會有 N 行資料；這些資料中的每一個字元，都必須依照讀取的順序，視同輸入到你的終端軟體中來處理。

輸入資料中不會包含定位字元（tab），而輸入中的換行符號必須被忽略。

請注意，輸入資料中的空白字元（blank）是一般字元，必須顯示在終端螢幕上。

最後一組測試之後，會接著出現一行只包含整數 0 的資料，表示輸入結束。

任何控制序列都不會被拆分到兩行輸入資料之中。

在每一個測資開始時，請假設終端螢幕是清空的（也就是整個畫面都填滿空白字元）、終端處於覆寫模式（overwrite mode），且游標位於螢幕的第 0 行、第 0 列。

Output

對於每一個輸入測資，請輸出一行，包含該測資的編號（自 1 起依序編號），以及在完成該測資所有資料處理後，螢幕最終呈現的畫面內容。請將螢幕畫面以一個「方框」包圍；所需的輸出格式請參考下方範例說明。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
7
This is bad^h^c
^05^^
^14/ \^d^b / \
^u^d^d^l^l^l^l^l^l^l^l^l
^r^r< ACM >^l^l^d/^b \
^b^d \ /
^d^l^lv
7
^i9^l8^l7^l6^l5^l4^l3^l2^l1^l0
^o^d^lThis is #1^d^bThis is #2
^d^bThis is #3^d^bThis is #4
^d^bThis is #5^d^bThis is #6
^d^bThis is #7^d^bThis is #8
^i^d^bThis is #9^d^bThis is #10
^54^e Hello^d^l^l^l^lWorld
0

Sample Output

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
Case 1
+----------+
|     ^    |
|    / \   |
|   /   \  |
|  < ACM > |
|   \   /  |
|    \ /   |
|     v    |
|          |
|          |
|          |
+----------+
Case 2
+----------+
|0123456789|
|This is #1|
|This is #2|
|This is #3|
|This is #4|
|This Hello|
|This World|
|This is #7|
|This is #8|
|This is #0|
+----------+

解題思路：

這題其實沒有很難，就是題目長了點，基本上都按照題目的去做即可。

在思路上，可以先設定一個 vector <string> scr(10, string(10, ' ')) ，表示一個 10×1010 \times 10 的螢幕畫面。

接著 int r = 0, c = 0 表示目前的游標（cursor）位置。

可以建立兩個函數：putChar(ch)、clearScreen()，把程式碼包裝起來，後續就不用全擠在一個 for 迴圈裡面。

範例程式碼：

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N, test_case = 1;
    while (cin >> N && N != 0) {
        cin.ignore();
        
        vector<string> scr(10, string(10, ' '));
        int r = 0, c = 0;
        bool insertMode = false;
        
        // [&](char ch) 匿名函數
        // putChar 本身就會是一個函數
        // clearScreen 也一樣
        // [&] 即為捕捉到的變數以 reference 的方式傳遞
        auto putChar = [&](char ch){
            if (!insertMode){
                scr[r][c] = ch;
            }
            else{
                // 進入插入模式
                // 在位置 (r, c) 做插入的話
                // 其位置後續字元都要往後挪移
                // 因而用 for(int j = 9; j > c; --j)
                // e.g. : abcdefg, 插入 x -> abcdxefg
                // x 插入在其中, efg 要往後挪移
                for (int j = 9; j > c; --j) scr[r][j] = scr[r][j - 1];
                scr[r][c] = ch;
            }
            if (c < 9) c++; // 邊界檢查
        };
        
        auto clearScreen = [&]() {
            // assign 為 string 標頭檔的方法
            // row.assign(10, ' ')
            // 即在字串 row 中, 用長度 10 的 ' ' 空白字元
            // 覆蓋掉原本的內容
            for (auto &row : scr) row.assign(10, ' ');
        };
        
        for (int k = 0; k < N; ++k){
            string line;
            getline(cin, line);
            
            for (int i = 0; i < line.size(); ++i){
                char ch = line[i];
                
                if (ch != '^'){
                    putChar(ch);
                    continue;
                }
                
                char cmd = line[++i]; // ++i 取得 ^ 的下一個字元
                
                if (cmd == '^'){
                    putChar('^');
                }
                else if (isdigit(cmd)){
                    int nr = cmd - '0';
                    int nc = line[++i] - '0';
                    r = nr, c = nc;
                }
                else{
                    switch (cmd){
                        case 'b': c = 0; break;
                        case 'c': clearScreen(); break;
                        case 'd': if (r < 9) ++r; break;
                        case 'e': for (int j = c; j < 10; ++j) scr[r][j] = ' '; break;
                        case 'h': r = 0, c = 0; break;
                        case 'i': insertMode = true; break;
                        case 'l': if (c > 0) --c; break;
                        case 'o': insertMode = false; break;
                        case 'r': if (c < 9) ++c; break;
                        case 'u': if (r > 0) --r; break;
                    }
                }
            }
        }
        
        cout << "Case " << test_case++ << '\n';
        cout << "+----------+\n";
        for (int i = 0; i < 10; ++i) cout << "|" << scr[i] << "|\n";
        cout << "+----------+\n";
    }
}