## UVA 11689 - Soda Surpler
### [題目網址 (UVA Online Judge)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2736)
### 🔥 難度評估 : 1⭐

---

### 📖 題目描述
Tim 是一個非常愛喝汽水的人。由於他沒有錢，所以他要喝汽水的唯一方法就是收集空汽水瓶子，然後拿去回收換取錢再去買新汽水來喝。

除了他自己喝完的空瓶子，Tim 也會到街上去收集別人喝完的空瓶子。
有一天，他非常的渴，他要盡可能的喝汽水，直到他得不到任何一瓶為止。

- $e$：Tim 一開始擁有的空瓶數 ($0 \leq e < 1000$)
- $f$：Tim 在街上收集到的空瓶數 ($0 \leq f < 1000$)
- $c$：多少個空瓶可以換一瓶新的汽水 ($1 < c < 2000$)

輸入：
- 第一行輸入整數 $N$，代表有多少組測資。
- 每組測資包含三個整數 $e, f, c$。

輸出：
- 對每組測資輸出一行，代表 Tim 最多可以喝到多少瓶汽水。

---

### 🎯 本題考點
1. **模擬 + 整數運算**
- 模擬「換瓶子 → 喝掉 → 空瓶再加入」的循環過程。

2. **迴圈條件**
- 只要空瓶數 $\geq c$，就能再換新汽水。

3. **變數更新**
- 每輪計算：
- `newSoda = empties / c`
- `drinks += newSoda`
- `empties = newSoda + (empties % c)`

---

### 🧩 解題步驟
1. 讀取測資組數 $t$。
2. 對每組測資讀取 $e, f, c$。
3. 初始化：
- `empties = e + f`
- `drinks = 0`
4. 當 `empties >= c` 時：
- 換到新汽水 `newSoda = empties / c`
- 更新喝到的總瓶數 `drinks += newSoda`
- 更新空瓶數 `empties = newSoda + (empties % c)`
5. 輸出結果。

---

### ✅ 小結
- 這題是單純的「模擬換瓶子」問題。
- 關鍵是正確更新空瓶數，**不能把累積喝到的總數加回去**。
- 資料範圍小，用 `int` 足夠，但保險也可以用 `long long`。

---

### 💻 程式碼 (C++)

#include <iostream>
using namespace std;

int main() {
	int t; cin >> t;
	while (t--) {
		int e, f, c;
		cin >> e >> f >> c;

		int total = 0;
		total += (e + f) / c;
		e = (e + f) % c + total;

		while (e / c > 0) {
			total += e / c;
			int remain = e / c;
			e = e % c + remain;
		}
		cout << total << '\n';
	}
}

---
---

## UVA 10188 - Automated Judge Script
### [題目網址 (UVA Online Judge)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1129)
### 🔥 難度評估 : 1⭐

---

### 📖 題目描述
來自程式設計競賽的評審以非常刻薄和懶惰著稱。我們希望寫一個自動評審程式，來比較 **標準解答** 與 **隊伍輸出**，並給出下列三種結果之一：

1. **Accepted**
- 當隊伍輸出與標準答案 **完全逐字相同**（包含所有字元與換行）。

2. **Presentation Error**
- 當兩邊的 **數字序列完全相同**（順序一樣），但是其他字元（空格、標點、文字…）有差異。

3. **Wrong Answer**
- 不符合以上兩者，也就是連數字序列都不相同。

---
### 🎯 本題考點
1. **字串比對**
- `Accepted` → 完全字串相同。
- `Presentation Error` → 抽取所有數字後比對是否相同。
- 其餘 → `Wrong Answer`。

2. **迴圈處理多組測資**
- 直到遇到 $n = 0$ 為止。

3. **I/O 細節**
- 使用 `cin.ignore()` 搭配 `getline()`，避免讀入換行符號造成空行。

---

### 🧩 解題步驟
1. 讀取整數 $n$，若 $n=0$ 結束程式。
2. 讀取標準答案 $n$ 行，存入 `s1`。
3. 讀取整數 $m$，再讀取隊伍輸出 $m$ 行，存入 `s2`。
4. **檢查 Accepted**：
- 若 $n==m$ 且對應每行字串都相同 → 輸出 `Accepted`。
5. **檢查 Presentation Error**：
- 將 `s1` 與 `s2` 的所有行抽出數字，分別組成字串 `d1, d2`。
- 若 `d1 == d2` → 輸出 `Presentation Error`。
6. 否則 → 輸出 `Wrong Answer`。

---

### ✅ 小結
- **Accepted** = 完全逐字相同。
- **Presentation Error** = 數字正確，但格式錯誤。
- **Wrong Answer** = 數字序列也不相同，答案真的錯。

---

### ⚡️ 考點及細節
1. **vector 容器的利用**
- 用 `vector<string>` 儲存每行輸出，方便逐行比對與後續處理。

2. **cin.ignore() 與 getline() 的搭配**
- `cin >> n` 後要 `cin.ignore()` 清除緩衝區換行，再用 `getline()` 讀入完整一行。

3. **不要誤解題意**
- 題目問的是「整份輸出的所有數字排列是否一致」，而不是逐行比數字。
- 所以 `Presentation Error` 檢查時要把全部行的數字接在一起再比較。

---

### 💻 程式碼 (C++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int main() {
	int count = 0;
	while (cin >> n) {
		cin.ignore();
		vector<string> s1;
		vector<string> s2;
		if (n == 0)break;
		for (int i = 0; i < n; i++) {
			string s;
			getline(cin, s);
			s1.push_back(s);
		}

		cin >> m;
		cin.ignore();
		for (int i = 0; i < m; i++) {
			string s;
			getline(cin, s);
			s2.push_back(s);
		}

		bool check = true;
		for (int i = 0; i < n; i++) {
			if (s1[i].size() == s2[i].size()) {
				for (int j = 0; j < s1[i].size(); j++) {
					if (s1[i][j] != s2[i][j]) {
						check = false;
						break;
					}
				}
			}
			else check = false;
			if (!check)break;
		}
		if (check) {
			cout << "Run #" << ++count << ": Accepted\n";
			continue;
		}


		
		string d1, d2;                                          
		for (int i = 0; i < n; ++i)
			for (char ch : s1[i])
				if (isdigit(ch)) d1.push_back(ch);

		for (int i = 0; i < m; ++i)
			for (char ch : s2[i])
				if (isdigit(ch)) d2.push_back(ch);


		if (d1 == d2)  {
			cout << "Run #" << ++count << ": Presentation Error\n";
		}
		else {
			cout << "Run #" << ++count << ": Wrong Answer\n";
		}
	}
}

---
---

## UVA 10415 - Eb Alto Saxophone Player
### [題目網址 (UVA Online Judge)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1356)
### 🔥 難度評估 : 1⭐

---

### 📖 題目描述
你喜歡薩克斯風嗎？在這題中，我們要模擬一位 **Eb 中音薩克斯風手**在演奏一首歌曲時，計算 **每根手指頭按下鍵的次數**。

- 音符由 `c d e f g a b C D E F G A B` 組成。
- 小寫：低八度
- 大寫：高八度
- 每個音符對應的「指法」已在題目給定，例如：
- `c`：手指 2~4, 7~10
- `D`：手指 1~4, 7~9
- 當某個手指需要從「沒按 → 按下」時，計數器 +1。
- 如果手指在前一個音符已經按著，下一個音符也要按，就 **不再重複計數**。
- 若下一個音符不需要此手指，則視為放開。

輸入：
- 第一行整數 $t$，表示測資數量 ($1 \leq t \leq 1000$)。
- 接下來每組測資一行字串，長度 $\leq 200$，代表歌曲音符序列（可為空字串）。

輸出：
- 對每組測資輸出 10 個數字，以空格分隔，表示 **手指 1~10 各自按下的次數**。

---

### 🎯 本題考點
1. **模擬 (Simulation)**
- 依照每個音符的指法逐一模擬手指按鍵情況。

2. **狀態紀錄**
- 使用 `last[11]` 紀錄上一次哪些手指按著。
- 使用 `cnt[11]` 紀錄每個手指按下次數。

3. **資料結構**
- 用 `map<char, vector<int>>` 對應每個音符與它的手指狀態（0/1）。

---

### 🧩 解題步驟
1. 建立一個 **對照表** `map<char, vector<int>>`，每個音符對應一個長度 11 的陣列（index 1~10 表示手指是否需要按）。
2. 讀取測資數 $t$。
3. 對每首歌字串逐一模擬：
- 初始化 `last[11] = 0`。
- 對每個音符：
- 檢查每個手指 $j$ (1~10)：
- 若 `mp[ch][j] == 1` 且 `last[j] == 0` → 表示手指剛按下，`cnt[j]++`。
- 若 `mp[ch][j] == 0` → 表示手指放開，`last[j] = 0`。
- 更新 `last[j]`。
4. 輸出 `cnt[1..10]`。

---

### ✅ 小結
- 本題屬於簡單模擬，難點在於 **正確紀錄手指狀態**。
- 利用 `map<char, vector<int>>` 建立指法表，程式碼可讀性佳。
- 記得：只有「由放開變成按下」才需要計數。

---

### 💻 程式碼 (C++)

// CPE 一星題
// e531. 10415 - Eb Alto Saxophone Player

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main() {
    map<char, vector<int>> mp;
    // index 0 不用，1~10 表示手指
    mp['c'] = {0,0,1,1,1,0,0,1,1,1,1}; // c：2~4, 7~10
    mp['d'] = {0,0,1,1,1,0,0,1,1,1,0}; // d：2~4, 7~9
    mp['e'] = {0,0,1,1,1,0,0,1,1,0,0}; // e：2~4, 7~8
    mp['f'] = {0,0,1,1,1,0,0,1,0,0,0}; // f：2~4, 7
    mp['g'] = {0,0,1,1,1,0,0,0,0,0,0}; // g：2~4
    mp['a'] = {0,0,1,1,0,0,0,0,0,0,0}; // a：2~3
    mp['b'] = {0,0,1,0,0,0,0,0,0,0,0}; // b：2
    mp['C'] = {0,0,0,1,0,0,0,0,0,0,0}; // C：3
    mp['D'] = {0,1,1,1,1,0,0,1,1,1,0}; // D：1~4, 7~9
    mp['E'] = {0,1,1,1,1,0,0,1,1,0,0}; // E：1~4, 7~8
    mp['F'] = {0,1,1,1,1,0,0,1,0,0,0}; // F：1~4, 7
    mp['G'] = {0,1,1,1,1,0,0,0,0,0,0}; // G：1~4
    mp['A'] = {0,1,1,1,0,0,0,0,0,0,0}; // A：1~3
    mp['B'] = {0,1,1,0,0,0,0,0,0,0,0}; // B：1~2

    int t;
    string s;
    cin >> t;
    cin.ignore();
    while (t--) {
        getline(cin, s);

        int cnt[11] = {0};  // 每根手指的按下次數
        int last[11] = {0}; // 上一次的狀態

        for (char ch : s) {
            for (int j = 1; j <= 10; j++) {
                if (mp[ch][j] == 1) {
                    if (last[j] == 0) {
                        cnt[j]++;
                        last[j] = 1;
                    }
                } else {
                    last[j] = 0;
                }
            }
        }

        for (int j = 1; j <= 10; j++) {
            cout << cnt[j] << (j == 10 ? '\n' : ' ');
        }
    }
}

---
---

## UVA 11536 - Smallest Sub-Array
### [題目網址 (UVA Online Judge)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2531)
### 🔥 難度評估 : 2⭐～3⭐

---

### 📖 題目描述
給定長度為 `N` 的序列 `X`，其前 3 項固定，之後依遞迴式產生：
- `X1 = 1, X2 = 2, X3 = 3`
- `Xi = (X(i-1) + X(i-2) + X(i-3)) mod M + 1`（`i ≥ 4`）

輸入一個 `K`，請找出最短的連續子陣列 `[L..R]`，**使得 1..K 的每個整數都至少出現一次**。
若不存在，輸出 `sequence nai`。

**限制**（常見版本）：
- `2 < N ≤ 1,000,000`
- `0 < M ≤ 1000` → 注意序列值域僅為 `[1..M]`
- `1 < K ≤ 100`

---

### 🎯 本題考點
1. **滑動視窗（two pointers / minimum window subarray）**
- 右指標擴張到滿足條件，左指標極限收縮以最短化。

2. **值域限制的前置剪枝**
- 序列值只會在 `[1..M]`，若 `K > M` ⇒ 必不可能，直接輸出 `sequence nai`。

3. **`queue` 的觀念與基本用法**（本題的一種寫法）
- `queue<int> q;` 內放目前視窗的**索引**，每步 `q.push(i)` 擴張右端。
- 透過「**最後出現位置**」快速判斷左端是否可丟：
- 若左端值不在 `[1..K]`，或左端不是該值的最後一次出現（右邊還有），就 `q.pop()`。
- `q.front()` 即當前視窗能保證覆蓋的**最小左端**。

4. **`<climits>` 的 `INT_MAX` vs `<cstdint>`/`<limits>` 的 `INT8_MAX`**
- **`INT_MAX`**（來自 `<climits>`）可安全當「無窮大」初始化（約 2e9）。
- **`INT8_MAX` = 127**，太小（且在部份 Judge 可能未定義/衝突），**不要**拿來當無窮大。
- 本題最短長度 ≤ `N`（可至 1e6），要用 `INT_MAX`。

---

### 🧠 解題核心（以 `queue + last` 寫法）
- `last[v]`：紀錄值 `v (1..K)` 在目前掃描到的**最後一次出現位置**。
- `covered`：目前視窗內已覆蓋了幾種不同的 `1..K`。
- 每來一個 `i`：
1. 把 `i` 丟進 `q`（右擴）。
2. 若 `X[i]` 在 `1..K`：更新 `last[X[i]]`；若是第一次看到，`covered++`。
3. **收縮左端**：只要 `q.front()` 對覆蓋沒貢獻（不在 `1..K`），或它不是該值的最後一次出現（`front < last[val]`），就丟掉。
4. 若 `covered == K`，此時 `q.front()..i` 已是以 `i` 結尾的**最短合法視窗**，更新答案長度。

> 也可用經典「雙指標 + freq[]」做法，邏輯等價。

---

### 🧩 解題步驟
1. 讀取 `T` 組測資。
2. 對每組讀 `N, M, K`；若 `K > M` → 直接輸出 `sequence nai`。
3. 以遞迴式 O(N) 產生整個序列 `a[1..N]`。
4. 準備：`last[1..K] = 0`、`covered = 0`、`queue<int> q`、`ans = INT_MAX`。
5. 迴圈 `i=1..N`：右擴、更新 `last`/`covered`、用 while 極限丟掉左端可丟索引。
6. 當 `covered == K` 時，`ans = min(ans, i - q.front() + 1)`。
7. 若 `ans` 未被更新 → `sequence nai`，否則輸出 `ans`。

---

### 💻 程式碼 (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main() {
	int t; cin >> t;
	int count = 0;
	while (t--) {
		int N, mod, k;
		cin >> N >> mod >> k;


		vector<int>num(N + 1);
		num[1] = 1, num[2] = 2, num[3] = 3;
		for (int i = 4; i <= N; i++) {
			num[i] = (num[i - 1] + num[i - 2] + num[i - 3]) % mod + 1;
		}
		vector<int>last(k + 1, 0);
		int covered = 0;
		queue<int>q;
		int ans = INT_MAX;

		for (int i = 1; i <= N; i++) {
			int x = num[i];
			if (1 <= x && x <= k) {
				if (last[x] == 0)covered++;
				last[x] = i;  // 更新1~k每位最後出現位置
			}
			q.push(i);

			// 檢查左端的數字能不能丟
			while (!q.empty()) {
				int last_idx = q.front();
				int v = num[last_idx];

				if (v < 1 || v > k || last_idx < last[v])q.pop();
				else break;
			}

			if (covered == k && !q.empty()) {
				ans = min(ans, i - q.front() + 1);
			}
		}

		if (ans == INT_MAX) {
			cout << "Case " << ++count << ": sequence nai\n";
		}
		else {
			cout << "Case " << ++count << ": " << ans << '\n';
		}
	}
}

---
---

## UVA 11960 - Divisor Game
### [題目網址 (UVA Online Judge)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3111)
### 🔥 難度評估：1⭐ ~ 3⭐（數論＋搜尋/預處理取捨）

---

### 📖 題目描述
給定上界 \(N\)（可能很大，甚至到 `INT_MAX`），在所有 \(1\le n\le N\) 中找出**因數個數 \(d(n)\)** 最大的那個數；若有多個，常見規則為**取最小的 \(n\)**。
若 $(n=\prod p_i^{a_i})$（質因數分解），則

$d(n)=\prod (a_i+1).$

---

### 🎯 本題考點
1. **數論結構**：因數函數 \(d(n)\) 與質因數指數的關係。
2. **演算法選擇**：比較「回溯搜尋（小質數冪）」、「篩式預處理（加倍數法）」、「逐一枚舉＋因數函式」。
3. **時間複雜度理解**：\(\Theta(n\log n)\) 與 \(\Theta(N\sqrt N)\) 的由來，以及回溯樹的「小狀態空間」優勢。

---

### 三種典型做法總覽（重點比較）

| 方法 | 核心想法 | 時間複雜度（概略） | 空間 | 優點 | 缺點 | 適用情境 |
|---|---|---|---|---|---|---|
| **A. DFS：小質數冪＋指數遞減** | 只枚舉 $(n=2^{a_1}3^{a_2}5^{a_3}\cdots)$，且 $(a_1\ge a_2\ge a_3\ge\cdots)$，一路保持乘積 $(le N)$，最大化 $(prod(a_i+1))$ | 實務上節點數「幾千～幾萬」，對 `N ≤ INT_MAX` 很快 | 很小 | 不遍歷 1..N；能處理超大 \(N\)；上限不固定也可 | 需理解回溯與剪枝；若要**每個** \(n\) 的 \(d(n)\) 不適合 | 單筆或上限很大、不固定，只需「最佳 \(n\)」 |
| **B. 篩式預處理（加倍數法）** | 對 \(i=1..U\)，把 \(i\) 加到其所有倍數的計數上得 \(d(1..U)\)，再做「前綴最佳」 | \(\Theta(U\log U)\)（見下節推導） | \(O(U)\) | 一次建表，之後查詢 \(O(1)\) | 需要**固定且不大**的上限 \(U\)（如 \(10^6\)） | 多筆查詢且上限固定不大（如 UVA 11960） |
| **C. 逐一枚舉 1..N＋因數函式** | 對每個 \(n\) 用 \(\sqrt n\) 或 SPF 分解算 \(d(n)\) | $(sum_{n\le N}O(\sqrt n)=O(N\sqrt N))$；SPF 需 \(O(N)\) 記憶體 | 視作法而定 | 最直觀、好理解 | 大 \(N\) 非常慢；SPF 對大上限記憶體吃不消 | 只在 \(N\) 很小或純練習時 |

---

### A. DFS：小質數冪＋指數遞減（俗稱「大神思路」）
- **形狀限制**：

$n=2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3}\cdot 7^{a_4}\cdots,\qquad a_1\ge a_2\ge a_3\ge\cdots$

把大的指數放在小質數上，可在不減少因數的前提下讓 \(n\) 更小、較不易超過 \(N\)。
- **搜尋**：依序嘗試小質數（通常到 43 或 47 就足夠），在每層枚舉可行指數 \(e\)，**只要乘上去會超過 \(N\) 就停止該分支**；每得到新 \(n\) 都以 \(d(n)\) 嘗試更新最佳（平手取較小 \(n\)）。
- **為何快**：小質數冪成長快、指數遞減強烈壓縮狀態；節點數與 \(N\) 幾乎**不是線性關係**。

---

### B. 篩式預處理（加倍數法）為何是 \(\Theta(n\log n)\)
- **做法**：
對 \(i=1..n\)，把 \(i\) 加到所有倍數 $(j=i,2i,3i,\ldots\le n)$ 的計數上，最後得到 \(d(j)\)。
- **外圈觀點**：第 \(i\) 次外圈內圈次數為 $\big\lfloor \frac{n}{i}\big\rfloor)$。

$T(n)=\sum_{i=1}^{n}\Big\lfloor \frac{n}{i}\Big\rfloor
\le n\sum_{i=1}^{n}\frac{1}{i}
= n\,H_n=\Theta(n\log n).$

- **等價觀點**：\(\sum_{j\le n} d(j)=n\log n+(2\gamma-1)n+o(n)\)。
- **特色**：一次建好 \(d(1..n)\) 與「前綴最佳」，之後每個查詢 \(O(1)\) 回答；但前提是上限 \(n\) **固定且不大**。

---

### C. 逐一枚舉 1..N ＋ 因數函式
- **\(sqrt n\) 因數法**：單個 \(n\) 用 $i=1..\lfloor\sqrt n\rfloor$ 檢查整除，完全平方只算一次。
總時間 $sum_{n\le N}O(\sqrt n)=O(N\sqrt N)$ —— 對 \(N=10^6\) 也常吃不消。
- **SPF（最小質因數）版本**：可把單個 \(n\) 的分解降到 \(O(\log n)\)，但需要事先建長度 \(N\) 的表（記憶體 \(O(N)\)），因此只適用於上限不大且固定的情境。

---

### 三者差異與選擇建議
- **我只有一筆、而且 \(N\) 可能很大或不固定** → 選 **DFS（小質數冪＋指數遞減）**。
- **很多查詢、上限固定且不大（如 \(10^6\)）** → 選 **篩式預處理**，先建 \(d\) 與前綴最佳，查詢 \(O(1)\)。
- **只是練習或 \(N\) 很小** → **枚舉＋因數函式** 也行，但要知道它的極限。

> **Tie-break 提醒**：平手常見是「取較小的 \(n\)」。若做前綴最佳，條件要寫成平手保留較小（或依題意調整）。

---

### 名詞小抄
- \(d(n)\)：因數個數函數。若 \(n=\prod p_i^{a_i}\)，則 \(d(n)=\prod (a_i+1)\)。
- \(\prod\)：乘積記號；\(\sum\)：加總記號。
- \(H_n\)：調和數，\(H_n=\sum_{i=1}^{n}\frac{1}{i}=\ln n+\gamma+o(1)\)。

---

### ✅ 小結
- **DFS**：直接搜「高因數的形狀」，不看 1..N，能輕鬆處理 `INT_MAX` 級的 \(N\)。
- **篩式預處理**：\(\Theta(n\log n)\) 一次算好，之後秒回查詢，但需要小而固定的上限。
- **枚舉＋因數函式**：最直觀、但時間 \(\Theta(N\sqrt N)\)；只適合很小的 \(N\) 或教學用途。

---

### 🧠解題心得
這題如果想的到預先建立1~N的總因數表的話並不難，問題是想不到，如果單純用一般方法又會TLE。但dfs+小質數篩法又太難，難度會到3星。 所以我這題的難度跨度才會是罕見的1~3星。

---

### 💻 程式碼 (C++)

#include <iostream>
using namespace std;

int table[1000001];
int Ans[1000001];

void Create() {
	table[1000001] = { 0 };
	int max = 0, ans = 0;

	// 統計每數的因數總數
	for (int i = 1; i <= 1000000; i++) {
		for (int j = i; j <= 1000000; j = j + i)  {
			table[j] += 1;
		}
	}

	for (int i = 1; i <= 1000000; i++) {
		if (max <= table[i]) {
			max = table[i];
			ans = i;
			Ans[i] = ans;
		}
		else {
			Ans[i] = ans;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Create();

	int T; cin >> T;
	while (T--) {
		int N;
		cin >> N;

		cout << Ans[N] << '\n';
	}
}