---
# System prepended metadata

title: 113 進階程式設計個人筆記

---

<style>
	#doc pre {
		tab-size: 4;
		overflow: auto;
	}
</style>
{%hackmd @debbylin/theme-matcha %}

# 113 進階程式設計個人筆記
期待最「優雅」的方式解決，盡可能兼具可讀性、簡潔、效能。（可讀性 >> 簡潔 > 效能）

若有任何建議或想法歡迎留言賜教。

::: spoiler TODO

- [x] 讓明天的自己能看懂
- [x] 使變數命名皆盡可能有意義
- [x] 良好 Coding Style
- [x] Morden C++（no C-style array、pefer `static_cast`...）
- [x] 清理編譯器警告（最高等級，含隱式符號轉換）
- [ ] 補全思路與計算過程
:::

<!--
|  目錄  |
| ----- |
| [TOC] |
-->
<table>
<thead>
<tr>
<th>目錄</th>
</tr>
</thead>
<tbody>
<tr>
<td><ul>
<li><a href="#1-基礎CC程式設計複習" title="1. 基礎C/C++程式設計複習">1. 基礎C/C++程式設計複習</a><ul>
<li><a href="#a064-成績指標" title="a064: 成績指標">a064: 成績指標</a></li> 
<li><a href="#a096-時間差計算" title="a096: 時間差計算">a096: 時間差計算</a></li>
<li><a href="#a104-雪花片片" title="a104: 雪花片片">a104: 雪花片片</a></li>
</ul>
</li>
<li><a href="#2-函式-公用函式、自定函式" title="2. [函式] 公用函式、自定函式">2. [函式] 公用函式、自定函式</a><ul>
<li><a href="#a114-找出最小的完全平方數" title="a114: 找出最小的完全平方數">a114: 找出最小的完全平方數</a></li>
<li><a href="#a116-一起回家的日子" title="a116: 一起回家的日子">a116: 一起回家的日子</a></li>
<li><a href="#a115-賓果遊戲" title="a115: 賓果遊戲">a115: 賓果遊戲</a></li>
</ul>
</li>
<li><a href="#3-函式-遞迴函式" title="3. [函式] 遞迴函式">3. [函式] 遞迴函式</a><ul>
<li><a href="#a157-費波那契數列" title="a157: 費波那契數列">a157: 費波那契數列</a></li>
<li><a href="#a158-F91" title="a158: F91">a158: F91</a></li>
<li><a href="#a288-執行路徑數" title="a288: 執行路徑數">a288: 執行路徑數</a></li>
<li><a href="#a117-三色河內塔" title="a117: 三色河內塔">a117: 三色河內塔</a></li>
<li><a href="#a118-2k與四個自然數平方和" title="a118: 2^k與四個自然數平方和">a118: 2^k與四個自然數平方和</a></li>
</ul>
</li>
<li><a href="#4-基本資料型態-指標、多維陣列、串列" title="4. [基本資料型態] 指標、多維陣列、串列">4. [基本資料型態] 指標、多維陣列、串列</a><ul>
<li><a href="#a147-促銷活動" title="a147: 促銷活動">a147: 促銷活動</a></li>
<li><a href="#a159-錯誤更正" title="a159: 錯誤更正">a159: 錯誤更正</a></li>
<li><a href="#a105-爺爺種樹" title="a105: 爺爺種樹">a105: 爺爺種樹</a></li>
<li><a href="#a106-賓果遊戲" title="a106: 賓果遊戲">a106: 賓果遊戲</a></li>
<li><a href="#a107-加密解密" title="a107: 加密解密">a107: 加密解密</a></li>
<li><a href="#a287-文件解壓縮" title="a287: 文件解壓縮">a287: 文件解壓縮</a></li>
</ul>
</li>
<li><a href="#5-基本資料型態-字串" title="5. [基本資料型態] 字串">5. [基本資料型態] 字串</a><ul>
<li><a href="#a065-秘密差" title="a065: 秘密差">a065: 秘密差</a></li>
<li><a href="#a067-ROT13" title="a067: ROT13">a067: ROT13</a></li>
<li><a href="#a109-跑長編碼與資料壓縮" title="a109: 跑長編碼與資料壓縮">a109: 跑長編碼與資料壓縮</a></li>
<li><a href="#a108-計算字串間隔距離" title="a108: 計算字串間隔距離">a108: 計算字串間隔距離</a></li>
<li><a href="#a110-棒球遊戲" title="a110: 棒球遊戲">a110: 棒球遊戲</a></li>
</ul>
</li>
<li><a href="#6-基本資料型態-結構" title="6. [基本資料型態] 結構">6. [基本資料型態] 結構</a><ul>
<li><a href="#a150-多邊形面積" title="a150: 多邊形面積">a150: 多邊形面積</a></li>
<li><a href="#a113-99遊戲" title="a113: 99遊戲">a113: 99遊戲</a></li>
<li><a href="#a111-排隊" title="a111: 排隊">a111: 排隊</a></li>
<li><a href="#a112-動物數量統計" title="a112: 動物數量統計">a112: 動物數量統計</a></li>
</ul>
</li>
<li><a href="#7-基礎資料結構-I--堆疊、佇列" title="7. [基礎資料結構 I ] 堆疊、佇列">7. [基礎資料結構 I ] 堆疊、佇列</a><ul>
<li><a href="#a151-後序式求值" title="a151: 後序式求值">a151: 後序式求值</a></li>
<li><a href="#a120-中置式轉後置式" title="a120: 中置式轉後置式">a120: 中置式轉後置式</a></li>
<li><a href="#a119-括號問題" title="a119: 括號問題">a119: 括號問題</a></li>
<li><a href="#a276-撲克牌遊戲：手風琴" title="a276: 撲克牌遊戲：手風琴">a276: 撲克牌遊戲：手風琴</a></li>
<li><a href="#a074-單線鐵路" title="a074: 單線鐵路">a074: 單線鐵路</a></li>
<li><a href="#a163-印表機佇列" title="a163: 印表機佇列">a163: 印表機佇列</a></li>
<li><a href="#a164-團體佇列" title="a164: 團體佇列">a164: 團體佇列</a></li>
</ul>
</li>
<li><a href="#8-基礎資料結構-I--樹狀結構" title="8. [基礎資料結構 I ] 樹狀結構">8. [基礎資料結構 I ] 樹狀結構</a><ul>
<li><a href="#a077-小球落下" title="a077: 小球落下">a077: 小球落下</a></li>
<li><a href="#a076-二元搜尋樹高度" title="a076: 二元搜尋樹高度">a076: 二元搜尋樹高度</a></li>
<li><a href="#a122-血緣關係" title="a122: 血緣關係">a122: 血緣關係</a></li>
<li><a href="#a123-樹狀圖分析" title="a123: 樹狀圖分析">a123: 樹狀圖分析</a></li>
</ul>
</li>
<li><a href="#9-基礎資料結構-I--圖形結構" title="9. [基礎資料結構 I ] 圖形結構">9. [基礎資料結構 I ] 圖形結構</a><ul>
<li><a href="#a051-城市旅遊" title="a051: 城市旅遊">a051: 城市旅遊</a></li>
<li><a href="#a102-油田" title="a102: 油田">a102: 油田</a></li>
<li><a href="#a103-小群體" title="a103: 小群體">a103: 小群體</a></li>
<li><a href="#a124-二分圖" title="a124: 二分圖">a124: 二分圖</a></li>
<li><a href="#a125-觀光景點" title="a125: 觀光景點">a125: 觀光景點</a></li>
<li><a href="#a126-馬步問題" title="a126: 馬步問題">a126: 馬步問題</a></li>
</ul>
</li>
<li><a href="#10-基礎演算法-I--複雜度分析、排序" title="10. [基礎演算法 I ] 複雜度分析、排序">10. [基礎演算法 I ] 複雜度分析、排序</a><ul>
<li><a href="#a127-連號或不連號" title="a127: 連號或不連號">a127: 連號或不連號</a></li>
<li><a href="#a148-字元頻率" title="a148: 字元頻率">a148: 字元頻率</a></li>
<li><a href="#a128-Agar.io" title="a128: Agar.io">a128: Agar.io</a></li>
<li><a href="#a129-飛天桑妮" title="a129: 飛天桑妮">a129: 飛天桑妮</a></li>
</ul>
</li>
<li><a href="#11-基礎演算法-I--排序與搜尋" title="11. [基礎演算法 I ] 排序與搜尋">11. [基礎演算法 I ] 排序與搜尋</a><ul>
<li><a href="#a152-二分搜尋" title="a152: 二分搜尋">a152: 二分搜尋</a></li>
<li><a href="#a153-二分法求解" title="a153: 二分法求解">a153: 二分法求解</a></li>
<li><a href="#a290-完美購書計畫" title="a290: 完美購書計畫">a290: 完美購書計畫</a></li>
<li><a href="#a130-人員調動" title="a130: 人員調動">a130: 人員調動</a></li>
<li><a href="#a131-大黑馬" title="a131: 大黑馬">a131: 大黑馬</a></li>
<li><a href="#a132-主機排程" title="a132: 主機排程">a132: 主機排程</a></li>
</ul>
</li>
<li><a href="#12-基礎演算法-I--窮舉法" title="12. [基礎演算法 I ] 窮舉法">12. [基礎演算法 I ] 窮舉法</a><ul>
<li><a href="#a088-最大乘積" title="a088: 最大乘積">a088: 最大乘積</a></li>
<li><a href="#a133-採蘑菇攻略問題" title="a133: 採蘑菇攻略問題">a133: 採蘑菇攻略問題</a></li>
<li><a href="#a154-除法" title="a154: 除法">a154: 除法</a></li>
<li><a href="#a134-回文日期問題" title="a134: 回文日期問題">a134: 回文日期問題</a></li>
<li><a href="#a135-巧克力擺盒" title="a135: 巧克力擺盒">a135: 巧克力擺盒</a></li>
</ul>
</li>
<li><a href="#13-基礎資料結構-II-及基礎演算法-II--貪婪法" title="13. [基礎資料結構 II 及基礎演算法 II ] 貪婪法">13. [基礎資料結構 II 及基礎演算法 II ] 貪婪法</a><ul>
<li><a href="#a091-加總的代價" title="a091: 加總的代價">a091: 加總的代價</a></li>
<li><a href="#a071-排隊買飲料" title="a071: 排隊買飲料">a071: 排隊買飲料</a></li>
<li><a href="#a141-基地台" title="a141: 基地台">a141: 基地台</a></li>
<li><a href="#a139-背包置物問題" title="a139: 背包置物問題">a139: 背包置物問題</a></li>
<li><a href="#a075-醜數" title="a075: 醜數">a075: 醜數</a></li>
</ul>
</li>
<li><a href="#14-基礎資料結構-II-及基礎演算法-II--分而治之與回溯法" title="14. [基礎資料結構 II 及基礎演算法 II ] 分而治之與回溯法">14. [基礎資料結構 II 及基礎演算法 II ] 分而治之與回溯法</a><ul>
<li><a href="#a165-最近點對問題" title="a165: 最近點對問題">a165: 最近點對問題</a></li>
<li><a href="#a089-蘇丹王位繼承者" title="a089: 蘇丹王位繼承者">a089: 蘇丹王位繼承者</a></li>
<li><a href="#a090-質數環" title="a090: 質數環">a090: 質數環</a></li>
<li><a href="#a286-23" title="a286: 23">a286: 23</a></li>
<li><a href="#a142-無刻度容器倒水問題" title="a142: 無刻度容器倒水問題">a142: 無刻度容器倒水問題</a></li>
</ul>
</li>
<li><a href="#15-基礎資料結構-II-及基礎演算法-II--動態規劃" title="15. [基礎資料結構 II 及基礎演算法 II ] 動態規劃">15. [基礎資料結構 II 及基礎演算法 II ] 動態規劃</a><ul>
<li><a href="#a098-計算方法數" title="a098: 計算方法數">a098: 計算方法數</a></li>
<li><a href="#a155-雙子星塔" title="a155: 雙子星塔">a155: 雙子星塔</a></li>
<li><a href="#a144-農作物採收問題" title="a144: 農作物採收問題">a144: 農作物採收問題</a></li>
<li><a href="#a101-分銅幣" title="a101: 分銅幣">a101: 分銅幣</a></li>
<li><a href="#a143-關鍵字搜尋模擬" title="a143: 關鍵字搜尋模擬">a143: 關鍵字搜尋模擬</a></li>
<li><a href="#a145-搬家規畫問題" title="a145: 搬家規畫問題">a145: 搬家規畫問題</a></li>
</ul>
</li>
<li><a href="#16-基礎資料結構-II-及基礎演算法-II--樹狀圖形結構演算法" title="16. [基礎資料結構 II 及基礎演算法 II ] 樹狀/圖形結構演算法">16. [基礎資料結構 II 及基礎演算法 II ] 樹狀/圖形結構演算法</a><ul>
<li><a href="#a136-元件測試排程問題" title="a136: 元件測試排程問題">a136: 元件測試排程問題</a></li>
<li><a href="#a137-勇者冒險" title="a137: 勇者冒險">a137: 勇者冒險</a></li>
<li><a href="#a138-最小花費的航空之旅" title="a138: 最小花費的航空之旅">a138: 最小花費的航空之旅</a></li>
</ul>
</li>
<li><a href="#17-題目解析-APCS-程式開發環境、題目解析" title="17. [題目解析] APCS 程式開發環境、題目解析">17. [題目解析] APCS 程式開發環境、題目解析</a><ul>
<li><a href="#a160-線段覆蓋長度" title="a160: 線段覆蓋長度">a160: 線段覆蓋長度</a></li>
<li><a href="#a140-物品堆疊" title="a140: 物品堆疊">a140: 物品堆疊</a></li>
</ul>
</li>
</ul>
</td>
</tr>
</tbody>
</table>

## 1. 基礎C/C++程式設計複習
### a096: 時間差計算
這題仔細看範例，可以知道是要後減前，再以一天為除數[取模](https://zh.wikipedia.org/zh-tw/模除)。不過很遺憾，C++ 中 `%` 運算子是求餘，結果正負跟隨被除數，所以多加了一個 86400 避免負結果。
```cpp=
#include <iomanip>
#include <iostream>
#include <string>

int main () {
	std::string str;
	int n = 86400;

	std::cin >> str;
	n -= std::stoi(str.substr(0, 2)) * 3600 +
		std::stoi(str.substr(3, 2)) * 60 +
		std::stoi(str.substr(6, 2));
	std::cin >> str;
	n += std::stoi(str.substr(0, 2)) * 3600 +
		std::stoi(str.substr(3, 2)) * 60 +
		std::stoi(str.substr(6, 2));
	n %= 86400;

	std::cout << std::setfill('0') <<
		std::setw(2) << n / 3600 << ':' <<
		std::setw(2) << n % 3600 / 60 << ':' <<
		std::setw(2) << n % 60 << std::endl;
	return 0;
}
```

### a064: 成績指標

沒什麼好說的。

```cpp=
#include <algorithm>
#include <iostream>
#include <vector>

int main () {
	int n {};
	std::cin >> n;
	std::vector<int> scores(n);
	int wc {101};
	int bc {-1};
	for (auto& score : scores) {
		std::cin >> score;
		if (score >= 60) {
			if (score < wc) wc = score;
		} else if (score > bc) bc = score;
	}
	std::sort(scores.begin(), scores.end());
	for (const auto& score : scores) std::cout << score << ' ';
	std::cout << "\n";
	if (bc == -1) std::cout << "best case\n";
	else std::cout << bc << "\n";
	if (wc == 101) std::cout << "worst case\n";
	else std::cout << wc << "\n";
	return 0;
}
```

### a104: 雪花片片

首先使用瞪眼法，易發現三角形數是 4 的次方，解決。（大誤

設第 $n$ 個圖形有 $f(n)$ 個邊，$g(n)$ 個三角形。不難得出：
$$
\begin{align}
f(1)&=3\\
f(n)&=f(n-1)\times4\\
g(1)&=1\\
g(n)&=g(n-1)+f(n-1)
\end{align}
$$
透過級數公式和數學歸納法可得：
$$
\begin{align}
f(n) &= 3 \times 4^{n-1}\\
g(n) &= 1 + 3(4^0+4^1+4^2+\dots+4^{n-3}+4^{n-2})\\
     &= 1 + 3 \times \frac{4^{n-1}-1}{4-1}\\
     &= 1 + 4^{n-1} - 1\\
     &= 4^{n-1}
\end{align}
$$
設累積三角形數（即題目要求的答案）為 $h(n)$。
$$
\begin{align}
h(n) &= g(1) + g(2) + \dots + g(n-1) + g(n)\\
     &= 1 + 4 + 16 + \dots + 4^{n-2} + 4^{n-1}\\
     &= \frac{4^n-1}{4-1}\\
     &= \frac{4^n-1}3
\end{align}
$$
好，雖然推導複雜了點，但蠻簡單的嘛？程式就一段 `(pow(4,n)+1)/3`，怎麼會說是最難的呢？
> 測試資料只有一行，只有一個數字 N，其值為 1 至 <u>120</u> 的整數。

$$
\begin{align}
h(120) &= 1 + 4 + 16 + \dots + 4^{118} + 4^{119}\\
       &> 4^{119} = 2^{238}\\
       &\gg 2^{64}
\end{align}
$$

> `uint64_t` 的取值為 0 ~ 2^64^-1。

爆炸！由於 C/C++ 沒有內建大整數（是的 Python、Java都有），那就只能手搓大數運算了。也即儲存每一數位，自己做直式運算。

所以我們要做 N 次乘法（迭代$4^n$）、一個減法（$-1$）、再一個除法（$\frac{}3$）直式運算？不，這不優雅。仔細觀察：

$$
\begin{align}
h(n) &= 1 + 4 + 16 + \dots + 4^{n-3} + 4^{n-2} + 4^{n-1} \\
     &= 1 + 4\left(1 + 4 + 16 + \dots + 4^{n-3} + 4^{n-2}\right) \\
     &= 1 + 4h(n-1) \\
h(1) &= 1
\end{align}
$$

$x \leftarrow 4x+1$ <ruby>遞迴<rp>(</rp><rt style="font-size:0.6em;">疊代</rt><rp>)</rp></ruby>，漂亮！

```cpp=
#include <iostream>
#include <vector>

int main () {
	// 倒序存（最高位在最後）比較好計算，故最後輸出時要反過來。
	std::vector<int> bigNum {0};
	int n {};
	std::cin >> n;
	while (n--) {
		int c {1};
		for (auto& x : bigNum) {
			const int temp {x * 4 + c};
			c = temp / 10;
			x = temp % 10;
		}
		if (c) bigNum.push_back(c);
	}
	for (auto i {bigNum.rbegin()}; i != bigNum.rend(); i++) std::cout << *i;
	std::cout << '\n';
	return 0;
}
```

另外其實裡面的 10 可以換成大一點的數字以大幅提升計算效率（只要是十的次方並確保不超過上限），但那樣還要用 `std::setprecision()` 確保 0 不會被吃掉，而我懶就沒弄了。

## 2. [函式] 公用函式、自定函式
### a114: 找出最小的完全平方數
一個一格數字確認是否是符合條件的數肯定會爆的，那該如何最佳化呢？
* 由底數找平方數而非反過來檢查
* 跳過奇數，因其平方必亦為奇數
* 若且唯若 $\sqrt{10^{n+1}} \le x < \sqrt{10^{n+2}}$，$x^2$ 的位數為 $n$ 
* 平方差 $(n+2)^2-n^2 = (2)(2n+2) = 4n+4$
* $\sqrt{10^{2k}} = 10^k$，$\sqrt{10^{2k+1}} = 10^k\sqrt{10}$
* ~~這題才 10 種可能，最好的解法應該是硬編碼才對 XD~~
  - 但還是要先寫個程式算過就是（`constexpr`：叫我？）

```cpp=
#include <iostream>

bool all_even (int n, int length) {
	while (length--) {
		if (n % 2) break;
		n /= 10;
	}
	return !n;
}

int main () {
	constexpr double sqrt10 {3.1622776602};
	int n {};
	std::cin >> n;
	while (n--) {
		int length {};
		std::cin >> length;
		int base {1};
		for (int i = 0; i < (length - 1) / 2; i++) base *= 10;
		if (length % 2 == 0) base *= sqrt10;
		base += base % 2;
		long long square {base * base};
		while (!all_even(square, length)) {
			square += 4 * base + 4;
			base += 2;
		}
		std::cout << square << '\n';
	}
	return 0;
}
```

### a116: 一起回家的日子
> <ruby>不要重新發明輪子<rt>Don't reinvent the wheel</rt></ruby>

這一章叫做公用函式，而傳說有種東西叫[標準庫](https://en.cppreference.com)。

不得不吐槽一下，Python 時就知道要引庫，怎麼變成 C++ 就都不會了。

```cpp=
#include <ctime>
#include <iomanip>
#include <iostream>

int gcd (int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main () {
	int timelong {1};
	int n {};
	std::cin >> n;
	while (n--) {
		int in {};
		std::cin >> in;
		timelong *= in / gcd(in, timelong);
	}

	std::tm date {};
	std::cin >> std::get_time(&date, "%Y/%m/%d");
	date.tm_mday += timelong;
	std::mktime(&date);
	std::cout << std::put_time(&date, "%Y/%m/%d") << "\n";
	return 0;
}
```

要不是 [`std::lcm`](https://en.cppreference.com/w/cpp/numeric/lcm) C\++17 才加入，而我們系統很爛的只支援 C\++14，還可以寫得更漂亮。

### a115: 賓果遊戲
記錄每行列斜的狀態及每個數字所在的座標，最後比對每數字所在之處，有多少臨門一腳的行列斜。

然後我不加 `#pragma` 它不會幫我 `inline`。

```cpp=
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>

template <typename T>
constexpr std::size_t u(T i) {
	return static_cast<std::size_t>(i);
}

int main () {
	std::vector<int> x_state(5), y_state(5);
	int slash_state {0}, bslash_state {0};
	std::vector<int> x_pos(25), y_pos(25);

	bool state[25] = {};
	for (int y = 0; y < 5; y++) {
		for (int x = 0; x < 5; x++) {
			int number {};
			std::cin >> number;
			number--;
			x_pos[u(number)] = x;
			y_pos[u(number)] = y;
		}
	}

	int number {};
	std::cin >> number;
	while (number != -1) {
		number--;
		x_state[u(x_pos[u(number)])]++;
		y_state[u(y_pos[u(number)])]++;
		if (x_pos[u(number)] == y_pos[u(number)]) bslash_state++;
		if (x_pos[u(number)] + y_pos[u(number)] == 4) slash_state++;
		state[number] = true;
		std::cin >> number;
	}

	int max_score {};
	int answer {};
	for (int i = 24; i >= 0; i--) {
		if (state[i]) continue;
		int score {
			(x_state[u(x_pos[u(i)])] == 4) +
			(y_state[u(y_pos[u(i)])] == 4) +
			(x_pos[u(i)] == y_pos[u(i)] && bslash_state == 4) +
			(x_pos[u(i)] + y_pos[u(i)] == 4 && slash_state == 4)
		};
		if (score >= max_score) {
			max_score = score;
			answer = i;
		}
	}

	std::cout << answer + 1 << std::endl;
	return 0;
}
```

## 3. [函式] 遞迴函式
### a157: 費波那契數列
題目叫你用遞迴就用遞迴。

遞迴爆炸？[尾遞迴](https://zh.wikipedia.org/zh-tw/尾调用)是種好東西。

```cpp=
#include <iostream>

int f (int n, int f_nm1 = 1, int f_nm2 = 0) {
	return n == 0 ? f_nm2 : f(n - 1, f_nm1 + f_nm2, f_nm1);
}

int main () {
	int n {};
	while (std::cin >> n) std::cout << f(n) << std::endl;
	return 0;
}
```

### a158: F91
瞪眼法：名字裡有 91 答案自然是 91。（誤&times;2）

設 $90 \le n \le 100$，歸納法得證：
$$
\begin{align}
F91(100) &= F91(F91(111))\\
         &= F91(101)\\
         &= 91\\
F91(n) &=F91(F91(n+11))\\
       &=F91(n + 11 - 10)\\
       &=F91(n+1)\\
       &= 91\\
\end{align}
$$
設 $n \le 89$，假設 $F91(n) = 91$ 歸納法得證：
$$
\begin{align}
F91(89) &= F91(F91(100))\\
         &= F91(91)\\
         &= 91\\
F91(n) &=F91(F91(n+11))\\
       &=F91(91)\\
       &= 91\\
\end{align}
$$
可得：
$$
F91(n) = \left\{ \begin{array}{cl}
91 & : \ n \le 100 \\
n-10 & : \ n \ge 101
\end{array} \right.
$$

```cpp=
#include <iostream>

int f91 (int n) {
	return n <= 100 ? 91 : n - 10;
}

int main () {
    int n;
    std::cin >> n;
    while (n != 0) {
        std::cout << "f91(" << n << ") = " << f91(n) << "\n";
        std::cin >> n;
    }
    return 0;
}
```

### a288: 執行路徑數
將輸入的所有 `S` 刪去，`IF` 換成 `(1`，`ELSE` 換成 `+1`，`END_IF` 換成 `)`，就能得出答案的算式。例如：

```
IF
ELSE
	IF
	ELSE
	END_IF
END_IF
IF
	IF
	ELSE
	END_IF
	IF
	ELSE
	END_IF
ELSE
	IF
	ELSE
	END_IF
END_IF
```

以上輸入的答案即為 `(1+1(1+1))(1(1+1)(1+1)+1(1+1))`，原理學排列組合時已講過，此不再贅述。

再觀察以下計算過程：

```
(1+1(1+1))(1(1+1)(1+1)+1(1+1))
(1+1(2))(1(1+1)(1+1)+1(1+1))
(1+2)(1(1+1)(1+1)+1(1+1))
3(1(1+1)(1+1)+1(1+1))
3(1(2)(1+1)+1(1+1))
3(2(1+1)+1(1+1))
3(2(2)+1(1+1))
3(4+1(1+1))
3(4+1(2))
3(4+2)
3(6)
18
```

轉換成程式碼就是：
```cpp=
#include <iostream>
#include <stack>
#include <string>
#include <utility>

int main () {
	int n {};
	std::cin >> n;
	while (n--) {
		std::stack<std::pair<long long, long long>> stack {};
		stack.push({1, 0});
		while (true) {
			std::string keyword {};
			std::cin >> keyword;
			if (keyword == "S") {
				continue;
			} else if (keyword == "IF") {
				stack.push({1, 0});
			} else if (keyword == "ELSE") {
				stack.top().second = stack.top().first;
				stack.top().first = 1;
			} else if (keyword == "END_IF") {
				const auto& temp {stack.top()};
				stack.pop();
				stack.top().first *= temp.first + temp.second;
			} else if (keyword == "ENDPROGRAM") {
				break;
			}
		}
		std::cout << stack.top().first << '\n';
	}
	return 0;
}
```

雖然本題叫遞迴，但遞迴時語句歸屬可能有些燒腦，這邊採用較易理解的堆疊。

另外該寫法還有個好處：雖原題目必有且僅有一個 `ELSE`，只要為本程式碼加一個符號就能使其接受任意多的 `ELSE`……。

:::spoiler 任意多 `ELSE`
第 20 行`=`改為`+=`：

```cpp=20
stack.top().second += stack.top().first;
```
:::

### a117: 三色河內塔
畫圖解，我懶得把圖放上來了。

由於自始移動都是拿最上面的 n 個環，可以直接數出環的編號。故實際上不需存儲塔的狀態，徑輸出即可。
```cpp=
#include <iostream>

int moveTopOneRing (char from, char to, int id){
	std::cout << "ring " << id << " : " << from << " => " << to << "\n";
	return 1;
}

int moveTopNRings (int n, char from, char to, char through) {
	if (n == 1) return moveTopOneRing(from, to, n);
	int steps {0};
	steps += moveTopNRings(n - 1, from, through, to);
	steps += moveTopOneRing(from, to, n);
	steps += moveTopNRings(n - 1, through, to, from);
	return steps;
}

int distributeTopNRings (int n, char from, char a, char b) {
	if (n == 0) return 0;
	if (n == 1) return moveTopOneRing(from, b, n);
	int steps {0};
	steps += moveTopNRings(n - 1, from, a, b);
	steps += moveTopOneRing(from, b, n);
	steps += distributeTopNRings(n - 2, a, b, from);
	return steps;
}

int main () {
	int n {};
	std::cin >> n;
	const int steps{ distributeTopNRings(n, 'A', 'B', 'C') };
	std::cout << "共需" << steps << "個移動\n";

	return 0;
}
```

### a118: 2^k與四個自然數平方和
> 想到「若」很簡單，但欲證明「唯若」就要費很大一番功夫了。

假設 $a_1,a_2,a_3,a_4$ 皆為奇數，設 $a_i=2b_i+1$，則：
<!--
&=4b_1^2+4b_1+1+4b_2^2+4b_2+1+4b_3^2+4b_3+1+4b_4^2+4b_4+1\\-->
$$
\begin{align}
2^k &=(2b_1+1)^2+(2b_2+1)^2+(2b_3+1)^2+(2b_4+1)^2\\
&=4(b_1^2+b_1+b_2^2+b_2+b_3^2+b_3+b_4^2+b_4 + 1)\\
2^{k-2} &=b_1^2+b_1+b_2^2+b_2+b_3^2+b_3+b_4^2+b_4 + 1\\
\end{align}
$$
對於任何自然數 $x$，$x\equiv x^2 \pmod2$，可知 $x+x^2 \equiv 0\pmod2$。
$$
\displaylines{
2^{k-2} \equiv 0 \pmod2 \\
\begin{align}
2^{k-2} &\equiv (b_1^2+b_1)+(b_2^2+b_2)+(b_3^2+b_3)+(b_4^2+b_4) + 1\\
    &\equiv 0 + 0 + 0 + 0 +1\\
    &\equiv 1\\
0 &\equiv 1 \Rightarrow\!\Leftarrow\\
\end{align}\pmod2
}
$$
矛盾，故當 $k\ge3$ 時 $a_1,a_2,a_3,a_4$ 不可能皆為奇數。

再假設 $a_1,a_2,a_3,a_4$ 中共兩個奇數，不失一般性的令 $a_1=2b_1+1$、$a_2=2b_2+1$、$a_3=2b_3$、$a_4=2b_4$，則：
$$
\begin{align}
2^k&=(2b_1+1)^2+(2b_2+1)^2+(2b_3)^2+(2b_4)^2\\
  &=4(b_1^2+b_1+b_2^2+b_2+b_3^2+b_4^2)+2
\end{align}
$$
觀察到：
$$
\displaylines{
2^k \equiv 4\times2^{k-2} \equiv 0 \pmod4 \\
\begin{align}
2^k &\equiv 4(b_1^2+b_1+b_2^2+b_2+b_3^2+b_4^2)+2\\
    &\equiv 0 + 2\\
    &\equiv 2\\
0 &\equiv 2 \Rightarrow\!\Leftarrow\\
\end{align}\pmod4
}
$$
矛盾，故當 $k\ge2$ 時 $a_1,a_2,a_3,a_4$ 不可能共兩個奇數。

一個奇數及三個奇數的情況不言自明：奇數平方亦為奇數，奇數個奇數相加結果必為奇數。然 $2^k$ 為偶數，產生矛盾，不可能。

故給定 $k\ge3$，$a_1,a_2,a_3,a_4$ 必皆為偶數，設 $a_i=2b_i$：

$$
\begin{align}
2^k &=a_1^2 + a_2^2 + a_3^2 + a_4^2\\
    &=(2b_1)^2+(2b_2)^2+(2b_3)^2+(2b_4)^2\\
    &=4(b_1^2+b_2^2+b_3^2+2b_4^2)\\
2^{k-2} &= b_1^2+b_2^2+b_3^2+b_4^2\\
\end{align}
$$
不難看出，對於任意 $k\ge3$，$2^k$ 的所有解 $a_1,a_2,a_3,a_4$ 必定與 $2^{k-2}$ 的所有解 $\frac{a_1}{2},\frac{a_2}{2},\frac{a_3}{2},\frac{a_4}{2}$ 一一對應（對射）。又若 $k-2 \geq 3$，依然可確定它們仍皆為偶數，並同理進一步往下對應，直至所有解都與 $2^2$ 的或 $2^1$ 的解以差了二的冪倍之方式對應。

簡單觀察試算可得知：$2^1$ 時無解，$2^2$ 僅有唯一解 $2^2=1^2+1^2+1^2+1^2$。以上述解的一一對應性推而廣之，綜上可以證明：

$$
\displaylines{
2^k = a_1^2 + a_2^2 + a_3^2 + a_4^2\\
\iff \\
(k = 2n) \land (a_1 = a_2 = a_3 = a_4 = 2^{n-1})
}
$$

C++ 寫出來就是：

```cpp=
#include <iostream>

int main () {
	int k {};
	std::cin >> k;
	if (k % 2) {
		std::cout << "0\n";
		return 0;
	}
	const int ans{ 1 << (k / 2 - 1) };
	std::cout << ans << ' ' << ans << ' ' << ans << ' ' << ans << '\n';
	return 0;
}
```

## 4. [基本資料型態] 指標、多維陣列、串列
### a147: 促銷活動

題目要求填空，風格突變請見諒。

```cpp=
#include <iostream>
using namespace std;

void discount(double& p1, double& p2){
    if (p1 == p2) p2 /= 2;
}
int main(){
    double p1, p2;
    cout << "Original price:" << endl;
    cin >> p1 >> p2;
    discount(p1, p2);
    cout << "Price after discount:" << endl;
    cout << p1 << " " << p2 << endl;
    return 0;
}
```

### a159: 錯誤更正
關鍵字「奇偶校驗」。另外奇偶結果等於互斥或（XOR）結果，不必真的去加。
```cpp=
#include <bitset>
#include <iostream>

int main () {
	int n {};
	std::cin >> n;
	while (n != 0) {
		int flippedColumn {0};
		int flippedRow {0};

		std::bitset<100> columnSum {};
		for (int i = 0; i < n; i++) {
			bool rowSum {false};
			for (std::size_t j = 0; j < n; j++) {
				bool bit {};
				std::cin >> bit;
				rowSum ^= bit;
				if (bit) columnSum.flip(j);
			}
			if (rowSum) flippedRow = flippedRow ? -1 : i + 1;
		}
		for (int j = 0; j < n; j++) if (columnSum[static_cast<std::size_t>(j)]) {
			flippedColumn = flippedColumn ? -1 : j + 1;
		}

		if (flippedRow > 0 && flippedColumn > 0) {
			std::cout << "Change bit (" << flippedRow << "," << flippedColumn << ")\n";
		} else if (flippedRow == 0 && flippedColumn == 0) {
			std::cout << "OK\n";
		} else {
			std::cout << "Corrupt\n";
		}
		std::cin >> n;
	}
	return 0;
}
```

### a105: 爺爺種樹
~~目前該寫法尚未整理，請勿模仿！~~ 重寫完成。

由於 `std::vector<bool>` 的缺陷，這裡以另一種方式儲存。

特別感謝孟學老師提供關於利用定義步進來合併不同情況的思路。

```cpp=
#include <iostream>
#include <set>
#include <utility>

constexpr int sign (int x) {
	return (x > 0) - (x < 0);
}

int main () {
	int x_length {}, y_length {};
	std::cin >> x_length >> y_length;
	std::set<std::pair<int, int>> map {};

	int lines {};
	std::cin >> lines;
	while (lines--) {
		int start_x {}, start_y {}, end_x {}, end_y {};
		std::cin >> start_x >> start_y >> end_x >> end_y;
		const int dx {sign(end_x - start_x)};
		const int dy {sign(end_y - start_y)};
		for (int x {start_x}, y {start_y}; ; x += dx, y += dy) {
			map.emplace(x, y);
			if (x == end_x && y == end_y) break;
		}
	}
	std::cout << map.size() << '\n';
	return 0;
}
```

### a106: 賓果遊戲
很多時候會發現硬寫的優雅之處。真去寫四個迴圈不比直接邏輯式還長還醜？

~~另，可以用結構把 `names` 與 `disks` 結合，但我懶得改了。~~ 改好了。
```cpp=
#include <iostream>
#include <utility>
#include <vector>

bool is_bingo (const std::vector<int>& disk) {
	return (
		!(disk[0]  || disk[1]  || disk[2]  || disk[3] ) ||
		!(disk[4]  || disk[5]  || disk[6]  || disk[7] ) ||
		!(disk[8]  || disk[9]  || disk[10] || disk[11]) ||
		!(disk[12] || disk[13] || disk[14] || disk[15]) ||

		!(disk[0] || disk[4] || disk[8]  || disk[12]) ||
		!(disk[1] || disk[5] || disk[9]  || disk[13]) ||
		!(disk[2] || disk[6] || disk[10] || disk[14]) ||
		!(disk[3] || disk[7] || disk[11] || disk[15]) ||

		!(disk[0] || disk[5] || disk[10] || disk[15]) ||
		!(disk[3] || disk[6] || disk[9]  || disk[12])
	);
}

int main () {
	char symbol {};
	std::size_t player_num {};
	std::cin >> symbol >> player_num;

	// std::pair<name, disk>
	std::vector<std::pair<char, std::vector<int>>> 
		players(player_num, {{}, std::vector<int>(16)});

	for (auto& player : players) {
        std::cin >> player.first;
        for (auto& n : player.second) std::cin >> n;
	}

	std::cin >> symbol;
	std::vector<char> bingo {};
	for (int i {0}; i < 16; i++) {
		int said_number {};
		std::cin >> said_number;
		std::cout << said_number << ' ';
		for (auto& player : players) {
			for (auto& number : player.second) if (number == said_number) number = 0;
			if (is_bingo(player.second)) bingo.push_back(player.first);
		}
		if (!bingo.empty()) break;
	}
	for (const auto& name : bingo) std::cout << name << ' ';
	std::cout << '\n';
	return 0;
}
```

### a107: 加密解密
二維陣列平坦化。

~~目前這個解為了避免隱式符號轉換增加了些複雜。~~ 重寫完成。
```cpp=
#include <cctype>
#include <string>
#include <iostream>

int main() {
	const std::string tableLower {
		'a', 'b', 'c', 'd', 'e',
		'f', 'g', 'h', 'i', 'j',
		'k', 'l', 'm', 'n', 'o',
		'p', 'r', 's', 't', 'u',
		'v', 'w', 'x', 'y', 'z'
	};
	const std::string tableUpper {
		'E', 'X', 'A', 'M', 'P',
		'L', 'B', 'C', 'D', 'F',
		'G', 'H', 'I', 'J', 'K',
		'N', 'O', 'R', 'S', 'T',
		'U', 'V', 'W', 'Y', 'Z'
	};

	std::size_t length {};
	std::cin >> length;
	std::string input(length, '0');
	for (auto i {input.rbegin()}; i != input.rend(); i++) std::cin >> *i;
	const bool is_upper {std::isupper(input[0]) != 0};
	const auto decode {is_upper ? tableUpper : tableLower};
	const auto encode {is_upper ? tableLower : tableUpper};

	for (std::size_t i = 0; i < length; i += 2) {
		const auto a_pos {decode.find(input[i])};
		const auto b_pos {decode.find(input[i + 1])};
		std::cout << encode[a_pos / 5 * 5 + b_pos % 5] <<
			encode[b_pos / 5 * 5 + a_pos % 5];
	}
	return 0;
}
```

### a287: 文件解壓縮
題目怎麼說就怎麼做，不必多言。

```cpp=
#include <cctype>
#include <iostream>
#include <string>
#include <vector>

int main() {
	std::string reading {};
	std::string input_line {};
	std::vector<std::string> words {};
	bool reading_word {false};
	bool reading_number {false};

	while (std::getline(std::cin, input_line)) {
		if (input_line == "0") return 0;
		input_line.push_back('\n');
		for (const auto& c : input_line) {
			if (std::isalpha(c) || std::isdigit(c)) {
				reading.push_back(c);
				reading_word = std::isalpha(c);
				reading_number = std::isdigit(c);
				if (reading_number) continue;
			} else if (reading_word) {
				words.push_back(reading);
				reading.clear();
				reading_word = false;
			} else if (reading_number) {
				const auto word {std::prev(words.end(), std::stoi(reading))};
				std::cout << *word;
				words.push_back(*word);
				words.erase(word);
				reading.clear();
				reading_number = false;
			}
			std::cout << c;
		}
	}
	return 0;
}
```

## 5. [基本資料型態] 字串
### a065: 秘密差
透過不斷翻轉符號來達成一加一減，就無需另用一個變數做判斷。

冷知識：`c - '0'` 結果的正確有 C++ 標準保證。

```cpp=
#include <string>
#include <iostream>

int main () {
	std::string number {};
	std::cin >> number;
	int secrect_nmber {};
	for (const auto& c : number) secrect_nmber = -secrect_nmber + c - '0';
	if (secrect_nmber < 0) secrect_nmber *= -1;
	std::cout << secrect_nmber << '\n';
	return 0;
}
```

### a067: ROT13
`std::noskipws` 旗標能避免跳過空白。

都做 ASCII 加減了，ASCII 比大小就不用避諱了。
```cpp=
#include <iostream>

int main() {
	std::cin >> std::noskipws;
	char c {};
	while (std::cin >> c) {
		if ('a' <= c && c <= 'z') std::cout << static_cast<char>((c - 'a' + 13) % 26 + 'a');
		else if ('A' <= c && c <= 'Z') std::cout << static_cast<char>((c - 'A' + 13) % 26 + 'A');
		else std::cout << c;
	};
	return 0;
}
```

### a109: 跑長編碼與資料壓縮
注意本題有個大坑：若沒有 `>> std::ws`，`>> n` 吃掉數字後不會吃掉第一行的換行符，將導致迴圈第一次讀入空行（失去了數字的第一行）。有另一種解法是開頭迴圈外多叫一次 `std::getline` 吃掉第一行，或是使用 `std::cin.ignore()` 單獨吃掉數字後的換行符。不過 `std::ws` 本身有讓 debug 比較方便的好處。

`std::bitset<n>(x)`是個輸出二進位字串的小技巧。
```cpp=
#include <bitset>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>

enum State {
	reading_0 = '0',
	reading_1 = '1',
	not_reading,
	error
};

int main() {
	int n {};
	std::cin >> n;
	while (n--) {
		std::string line {};
		std::getline(std::cin >> std::ws, line);
		std::stringstream sstream {};
		unsigned int length {1};
		double size {1};
		State state {not_reading};
		for (const auto& c : line) {
			if (state == c && length < 7) length++;
			else if (state != not_reading) {
				sstream << static_cast<char>(state) << std::bitset<3>(length) << ' ';
				length = 1;
				size++;
			}
			if (c == '0') state = reading_0;
			else if (c == '1') state = reading_1;
			else {
				std::cout << "-1\n";
				state = error;
				break;
			}
		}
		if (state == error) continue;
		sstream << static_cast<char>(state) << std::bitset<3>(length) << ' ' <<
			std::round(size * 400. / line.size()) << "%\n";
		std::cout << sstream.rdbuf();
	}
	return 0;
}
```

### a108: 計算字串間隔距離
* 統一大小寫 = 忽略大小寫
* 善用布林標誌

```cpp=
#include <cctype>
#include <iostream>
#include <string>

int main() {
	std::string str {};
	std::cin >> str;
	char find {};
	std::cin >> find;
	for (auto& c : str) c = static_cast<char>(std::toupper(c));
	find = static_cast<char>(std::toupper(find));

	std::size_t start {0};
	bool first {true};
	while (true) {
		const auto pos {str.find(find, start)};
		if (pos == str.npos) break;
		if (!first) std::cout << pos - start + 1 << " ";
		else first = false;
		start = pos + 1;
	}
	std::cout << "\n";
	return 0;
}
```

### a110: 棒球遊戲
* 平坦化打擊至有序陣列
* 利用增長的陣列紀錄選手的跑壘紀錄

```cpp=
#include <bitset>
#include <iostream>
#include <string>
#include <vector>

enum class Hit {
	B1,
	B2,
	B3,
	B4,
	OUT,
	UNKNOWN
};

Hit prase_hit_name (const std::string& name) {
	if (name == "1B") return Hit::B1;
	else if (name == "2B") return Hit::B2;
	else if (name == "3B") return Hit::B3;
	else if (name == "HR") return Hit::B4;
	else if (name == "FO" || name == "GO" || name == "SO") return Hit::OUT;
	else return Hit::UNKNOWN;
}

int main() {
	constexpr int player_number {9};
	constexpr std::size_t max_step {27};

	std::vector<Hit> hits(max_step, Hit::UNKNOWN);
	for (int i {0}; i < player_number; i++) {
		int hit_times {};
		std::cin >> hit_times;
		for (int j {0}; j < hit_times; j++) {
			std::string hit_name {};
			std::cin >> hit_name;
			const std::size_t index {static_cast<std::size_t>(player_number * j + i)};
			if (index >= max_step) continue;
			hits[index] = prase_hit_name(hit_name);
		}
	}

	int target_num {};
	std::cin >> target_num;
	std::bitset<max_step * 4> player {};
	std::size_t move_times {0};
	int out_times {0};
	for (std::size_t i = 0; out_times < target_num; i++) {
		if (hits[i] == Hit::OUT) {
			out_times++;
			if (out_times % 3) continue;
			if (move_times <= 3) player.reset();
			else {
				player.reset(move_times - 1);
				player.reset(move_times - 2);
				player.reset(move_times - 3);
			}
			continue;
		}
		player.set(move_times);

		switch (hits[i]) {
			case Hit::B1:
				move_times += 1;
				break;
			case Hit::B2:
				move_times += 2;
				break;
			case Hit::B3:
				move_times += 3;
				break;
			case Hit::B4:
				move_times += 4;
				break;
			default:
				break;
		}
	}
	if (move_times < 3) move_times = 0;
	else move_times -= 3;
	int score {0};
	for (std::size_t i {0}; i < move_times; i++) score += player[i];
	std::cout << score << "\n";
	return 0;
}
```

## 6. [基本資料型態] 結構
### a150: 多邊形面積
外積大法好。
```cpp=
#include <iomanip>
#include <iostream>

struct Pos {
	double x {};
	double y {};
};

double cross (const Pos& a, const Pos& b) {
	return a.x * b.y - b.x * a.y;
}

int main () {
	int count {};
	std::cin >> count;
	Pos first {};
	std::cin >> first.x >> first.y;
	Pos last {first};
	double area {0};
	while (--count) {
		Pos now {};
		std::cin >> now.x >> now.y;
		area += cross(last, now);
		last = now;
	}
	area += cross(last, first);
	area /= -2;
	std::cout << std::setprecision(2) << std::fixed << area;
    return 0;
}
```

### a113: 99遊戲

```cpp=
#include <iostream>
#include <string>
#include <utility>
#include <vector>

int main () {
	constexpr std::size_t players_num {4};
	constexpr std::size_t cards {13};

	// pair<名字, 手牌>
	std::vector<std::pair<std::string, std::vector<std::string>>> players(
		players_num, {{}, std::vector<std::string>(cards)}
	);
	for (auto& player : players) {
		std::cin >> player.first;
		for (auto card {player.second.rbegin()}; card != player.second.rend(); card++) {
			std::cin >> *card;
		}
	}

	bool reversed {false};
	int num {0};
	std::size_t current_player_id {0};
	while (true) {
		auto& player {players[current_player_id]};
		const std::string card {player.second.back()};
		player.second.pop_back();

		if (card == "A") num = 0;
		else if (card == "4") reversed = !reversed;
		else if (card == "5" || card == "J") {}
		else if (card == "10") num += (num > 99 - 10) ? -10 : 10;
		else if (card == "Q") num += (num > 99 - 20) ? -20 : 20;
		else if (card == "K") num = 99;
		else num += std::stoi(card);

		if (num > 99) {
			std::cout << player.first << "\n" << player.second.size() << "\n";
			return 0;
		} else if (player.second.empty()) {
			std::cout << player.first << "\n" << num << "\n";
			return 0;
		}

		if (reversed) current_player_id += players_num - 1;
		else current_player_id += 1;
		current_player_id %= players_num;
	}
	return 0;
}
```

### a111: 排隊
```cpp=
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

int main () {
	std::size_t numberOfCustomers {};
	std::cin >> numberOfCustomers;
	std::vector<std::pair<int, int>> customers(numberOfCustomers);
	for (auto& customer : customers) {
		std::cin >> customer.first >> customer.second;
	}

	std::size_t max_line_long {0};
	int clock {0};
	std::size_t alreadyComing {0};
	for (std::size_t i {0}; i < numberOfCustomers; i++) {
		if (clock < customers[i].first) clock = customers[i].first;
		clock += customers[i].second;
		if (alreadyComing < i) alreadyComing = i;
		for (std::size_t j {alreadyComing}; customers[j].first <= clock && j < numberOfCustomers; j++) alreadyComing = j;
		if (max_line_long < alreadyComing - i) max_line_long = alreadyComing - i;
	}

	std::cout << max_line_long << "\n";
	return 0;
}
```

### a112: 動物數量統計
自己寫一個有序映射結構。

```cpp=
#include <iostream>
#include <map>
#include <vector>

template <typename Key, typename T>
struct OrderMap {
	std::map<Key, T> content {};
	std::vector<Key> order {};

	T& operator[] (const Key& key) {
		const auto& p {content.find(key)};
		if (p == content.end()) {
			order.push_back(key);
			return content[key];
		}
		return p->second;
	}
	
	const T& at (const Key& key) const {
		return content.at(key);
	}
};

int main () {
	int lines {};
	std::cin >> lines;
	OrderMap<std::string, OrderMap<std::string, int>> locations {};

	while (lines--) {
		std::string animal {};
		int numbers {};
		std::string location {};
		std::cin >> animal >> numbers >> location;
		locations[location][animal] += numbers;
	}
	for (const auto& location : locations.order) {
		std::cout << location << ":";
		const auto& animals {locations.at(location)};
		bool first {true};
		for (const auto& animal : animals.order) {
			if (first) first = false;
			else std::cout << ",";
			std::cout << animal << " " << animals.at(animal);
		}
		std::cout << "\n";
	}
	return 0;
}
```

## 7. [基礎資料結構 I ] 堆疊、佇列
### a151: 後序式求值

```cpp=
#include <cctype>
#include <iostream>
#include <stack>
#include <string>

int main () {
	std::string line {};
	while (std::getline(std::cin, line)) {
		std::stack<int> stack {};
		for (const auto& c : line) {
			if (std::isdigit(c)) {
				stack.push(c - '0');
				continue;
			}
			int b {stack.top()};
			stack.pop();
			int a {stack.top()};
			stack.pop();
			switch (c) {
			case '+':
				stack.push(a + b);
				break;
			case '-':
				stack.push(a - b);
				break;
			case '*':
				stack.push(a * b);
				break;
			case '/':
				stack.push(a / b);
				break;
			case '%':
				stack.push(a % b);
				break;
			}
		}
		std::cout << stack.top() << "\n";
	}
	return 0;
}
```

### a120: 中置式轉後置式
有些語意問題，不想改了。
```cpp=
#include <iostream>
#include <stack>

enum class Operator {
	Add,
	Minus,
	Multipy,
	Divide,
	LeftBrace,
	RightBrace,
	Err
};

bool get_op_priority (Operator left, Operator right) {
	if (
		(right == Operator::Divide || right == Operator::Multipy) &&
		(left == Operator::Add || left == Operator::Minus)
	) return false;
	if (
		left == Operator::LeftBrace ||
		right == Operator::LeftBrace
	) return false;
	return true;
}

Operator prase_op (char c) {
	return c == '+' ? Operator::Add
	: c == '-' ? Operator::Minus
	: c == '*' ? Operator::Multipy
	: c == '/' ? Operator::Divide
	: c == '(' ? Operator::LeftBrace
	: c == ')' ? Operator::RightBrace
	: Operator::Err;
}

char op_to_char (Operator op) {
	return op == Operator::Add ? '+'
	: op == Operator::Minus ? '-'
	: op == Operator::Multipy ? '*'
	: op == Operator::Divide ? '/'
	: '?';
}

int main() {
	std::string line {};
	std::stack<Operator> ops {};
	char c {};
	while (std::cin >> c) {
		const Operator op {prase_op(c)};
		if (op == Operator::Err) {
			std::cout << c;
			continue;
		}
		if (op == Operator::RightBrace) {
			while (ops.top() != Operator::LeftBrace) {
				std::cout << op_to_char(ops.top());
				ops.pop();
			}
			ops.pop();
			continue;
		}

		while (!ops.empty() && get_op_priority(ops.top(), op)) {
			std::cout << op_to_char(ops.top());
			ops.pop();
		}
		ops.push(op);
	}
	while (!ops.empty()) {
		std::cout << op_to_char(ops.top());
		ops.pop();
	}
	std::cout << "\n";
	return 0;
}
```
### a119: 括號問題
只有一種括號能搞出什麼花樣。（汗

僅一種取值的堆疊所剩的資訊只有長度，無異於一個整型變數。
```cpp=
#include <iostream>

int main () {
	int level {};
	int number {};
	char c {};
	while (std::cin >> c) {
		if (c == '(') {
			level++;
			number++;
		} else {
			level--;
			if (level < 0) break;
		}
	}
	if (level != 0) number = 0;
	std::cout << number << "\n";
	return 0;
}
```

### a276: 撲克牌遊戲：手風琴

順便練習一下疊代器的使用。

```cpp=
#include <iostream>
#include <stack>
#include <utility>
#include <vector>

using piles_t = std::vector<std::stack<std::pair<char, char>>>;

bool match (const piles_t::iterator& a, const piles_t::iterator& b) {
	return a->top().first == b->top().first ||
		a->top().second == b->top().second;
}

bool try_move (piles_t& piles) {
	for (auto from {piles.begin() + 1}; from != piles.end(); from++) {
		auto to {from};
		while (true) {
			const auto i {to - piles.begin()};
			if (i >= 3 && match(from, to - 3)) to -= 3;
			else if (i >= 1 && match(from, to - 1)) to -= 1;
			else break;
		}
		if (to == from) continue;
		to->push(from->top());
		from->pop();
		if (from->empty()) piles.erase(from);
		return true;
	}
	return false;
}

int main () {
	constexpr std::size_t cards_num {52};
	while (true) {
		piles_t piles(cards_num);
		for (auto& pile : piles) {
			char rank {}, suit {};
			std::cin >> rank >> suit;
			if (rank == '#') return 0;
			pile.push({rank, suit});
		}

		while (try_move(piles)) {}

		if (piles.size() == 1) std::cout << "1 pile remaining:";
		else std::cout << piles.size() << " piles remaining:";
		for (const auto& pile : piles) {
			std::cout << " " << pile.size();
		}
		std::cout << "\n";
	}
}
```

### a074: 單線鐵路
無需儲存 A 端狀態，因為固定順序且無法回頭。亦無需儲存 B，因為完成的已與後續無關。

這是第一個 `fastio()` 能給出顯著提升的題目，就順道加了。


```cpp=
#include <iostream>
#include <stack>

void fastio () {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
}

bool solve (int cars_num) {
	std::stack<int> station {};
	int front_car {1}; // A 端最外面一臺之編號
	bool fail {false};
	while (cars_num--) {
		int n {};
		std::cin >> n;
		if (!n) return false;
		if (fail) continue;

		if (!station.empty() && station.top() == n) {
			station.pop();
			continue;
		}
		while (front_car < n) station.push(front_car++);
		if (front_car != n) fail = true;
		else front_car++;
	}
	if (fail) std::cout << "No\n";
	else std::cout << "Yes\n";
	return true;
}


int main () {
	fastio();
	int cars_num {};
	std::cin >> cars_num;
	while (cars_num) {
		while (solve(cars_num)) {}
		std::cin >> cars_num;
	}
}
```

### a163: 印表機佇列
||~~前一題還在 90%，稍後補。~~||

頭放尾、頭放尾、條件符合不放尾，頭放尾移動整個陣列不就相當於一動視線嗎？盡管這題名叫「佇列」，但用佇列解才是最麻煩的，其操作本質上顯然是「（單向）環狀鏈結串列」。

```cpp=
#pragma GCC optimize("O3")
#include <array>
#include <forward_list>
#include <iostream>

template <typename T>
constexpr std::size_t u(T i) {
	return static_cast<std::size_t>(i);
}

int main () {
	constexpr int max_priority {9};
	int tests {};
	std::cin >> tests;
	while (tests--) {
		std::array<int, max_priority> priority_count {};
		int length {}, target_i {};
		std::cin >> length >> target_i;
		std::forward_list<int> notaqueue {};
		auto last {notaqueue.before_begin()};
		auto target {last};
		int priority {};

		for (int i = 0; i < length; i++) {
			int file {};
			std::cin >> file;
			priority_count[u(file - 1)]++;
			last = notaqueue.insert_after(last, file);
			if (i == target_i) target = last;
			if (file > priority) priority = file;
		}
		int time {0};
		while (true) {
			auto next {std::next(last)};
			if (next == notaqueue.end()) last = notaqueue.before_begin();
			else if (*next == priority) {
				time++;
				if (next == target) break;
				notaqueue.erase_after(last);
				priority_count[u(priority - 1)]--;
				while (!priority_count[u(priority - 1)]) priority--;
			} else last = next;
		}
		std::cout << time << "\n";
	}
}
```

甚至這題都還不用真的使用鏈結串列，因為並沒有必要真的「擦除」印出來的東西，優先權打掉就好。反正只有九種優先權，仔細想想就會發現循環次數並不會超過九次。

```cpp=
#pragma GCC optimize("O3")
#include <array>
#include <iostream>
#include <vector>

template <typename T>
constexpr std::size_t u(T i) {
	return static_cast<std::size_t>(i);
}

int main () {
	constexpr int max_priority {9};
	int tests {};
	std::cin >> tests;
	while (tests--) {
		std::array<int, max_priority> priority_count {};
		int length {}, target {};
		std::cin >> length >> target;
		std::vector<int> notaqueue(u(length));
		int priority {};

		for (int i = 0; i < length; i++) {
			int file {};
			std::cin >> file;
			priority_count[u(file - 1)]++;
			notaqueue[u(i)] = file;
			if (file > priority) priority = file;
		}
		int time {0};
		int index {0};
		while (true) {
			if (notaqueue[u(index)] == priority) {
				time++;
				if (index == target) break;
				notaqueue[u(index)] = 0;
				priority_count[u(priority - 1)]--;
				while (!priority_count[u(priority - 1)]) priority--;
			}
			index = (index + 1) % length;
		}
		std::cout << time << "\n";
	}
}
```

### a164: 團體佇列
```cpp=
#include <iostream>
#include <map>
#include <queue>
#include <string>

int main () {
	int id { 1 };
	while (true) {
		std::map<int, int> member_groups {};
		int group_num {};
		std::cin >> group_num;
		if (group_num == 0) return 0;
		std::cout << "Scenario #" << id++ << '\n';
		for (int group_id { 0 }; group_id < group_num; group_id++) {
			int member_num {};
			std::cin >> member_num;
			while (member_num--) {
				int member {};
				std::cin >> member;
				member_groups.emplace(member, group_id);
			}
		}
		std::map<int, std::queue<int>> grounps {};
		std::queue<int> grounp_queue {};
		while (true) {
			std::string command;
			std::cin >> command;
			if (command == "STOP") break;
			if (command == "ENQUEUE") {
				int ele {};
				std::cin >> ele;
				const int grounp_id { member_groups.at(ele) };
				auto& grounp { grounps[grounp_id] };
				if (grounp.empty()) grounp_queue.push(grounp_id);
				grounp.push(ele);
			} else if (command == "DEQUEUE") {
				auto& grounp { grounps.at(grounp_queue.front()) };
				std::cout << grounp.front() << '\n';
				grounp.pop();
				if (grounp.empty()) grounp_queue.pop();
			}
		}
		std::cout << '\n';
	}
}
```

## 8. [基礎資料結構 I ] 樹狀結構
### a077: 小球落下
解釋待補.jpg
```cpp=
#include <iostream>

int main () {
	int tests {};
	std::cin >> tests;
	while (tests--) {
		unsigned int depth {}, bolls {};
		std::cin >> depth >> bolls;
		bolls--;
		unsigned int ans {1};
		while (--depth) {
			ans <<= 1;
			ans |= bolls & 1;
			bolls >>= 1;
		}
		std::cout << ans << '\n';
	}
	return 0;
}
```

### a076: 二元搜尋樹高度
比起硬壓，真寫一個二元樹感覺才是最合適的。

```cpp=
#include <algorithm>
#include <iostream>

struct BST {
	int value {};
	BST* left {nullptr};
	BST* right {nullptr};

	int insert (int n, int deep = 1) {
		auto& next {n <= value ? left : right};
		if (next != nullptr) return next->insert(n, deep + 1);
		next = new BST {n};
		return deep + 1;
	}
};

int main () {
	int n {};
	std::cin >> n;
	BST root {n};
	int maxdeep {0};
	while (std::cin >> n) maxdeep = std::max(maxdeep, root.insert(n));
	std::cout << maxdeep << '\n';
	return 0;
}
```

### a122: 血緣關係
分治大法好。另外提醒基於樹為無環連通圖，任何一點都可做為根結點。

```cpp=
#pragma GCC optimize("O3")

#include <iostream>
#include <tuple>
#include <utility>
#include <vector>

// C++14 都十年了還用啥前處理器巨集
using tree_t = std::vector<std::vector<int>>;
constexpr void max_assign (int& a, int b) { if (a < b) a = b; }
constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }
void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

std::pair<int, int> max_distance_and_deep (const tree_t& tree, int node = 0) {
	int deep_first {0};
	int deep_second {0};
	int max_distance {0};
	for (const auto& child : tree[u(node)]) {
		int distence {}, deep {};
		std::tie(distence, deep) = max_distance_and_deep(tree, child);
		max_assign(max_distance, distence);
		if (deep >= deep_first) {
			deep_second = deep_first;
			deep_first = deep;
		} else max_assign(deep_second, deep);
	}
	max_assign(max_distance, deep_first + deep_second);
	return {max_distance, deep_first + 1};
}

int main () {
	fastio();
	int nodes_num {};
	std::cin >> nodes_num;
	tree_t tree(u(nodes_num));
	// vector<bool>
	std::vector<char> has_parent(u(nodes_num), false);
	for (int i {1}; i < nodes_num; i++) {
		int a {}, b {};
		std::cin >> a >> b;
		tree[u(a)].push_back(b);
		has_parent[u(b)] = true;
	}
	int root {-1};
	while (has_parent[u(++root)]) {}
	std::cout << max_distance_and_deep(tree, root).first << '\n';
	return 0;
}
```

### a123: 樹狀圖分析
跟上一題幾乎一模一樣，不過小改了幾個地方的寫法。

```cpp=
#pragma GCC optimize("O3")

#include <iostream>
#include <utility>
#include <vector>

using tree_t = std::vector<std::vector<int>>;
constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }
void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

std::pair<int, int> max_deepsum_and_deep (const tree_t& tree, int node) {
	int max_deep {0};
	int deep_sum_sum {0};
	for (const auto& child : tree[u(node - 1)]) {
		const auto& child_data {max_deepsum_and_deep(tree, child)};
		if (max_deep < child_data.second) max_deep = child_data.second;
		deep_sum_sum += child_data.first;
	}
	return {deep_sum_sum + max_deep, max_deep + 1};
}

int main () {
	fastio();
	int nodes_num {};
	std::cin >> nodes_num;
	tree_t tree(u(nodes_num));
	// vector<bool>
	std::vector<char> has_parent(u(nodes_num), false);
	for (auto& node : tree) {
		int child_num {};
		std::cin >> child_num;
		while (child_num--) {
			int child {};
			std::cin >> child;
			has_parent[u(child - 1)] = true;
			node.push_back(child);
		}
	}
	int root {0};
	while (has_parent[u(root++)]) {}
	std::cout << root << '\n' <<
		max_deepsum_and_deep(tree, root).first << '\n';
	return 0;
}
```

## 9. [基礎資料結構 I ] 圖形結構
### a051: 城市旅遊
此乃深度優先搜尋。

```cpp=
#pragma GCC optimize("O3")

#include <bitset>
#include <iostream>
#include <vector>

constexpr int max_cities {800};
using graph_t = std::vector<std::vector<int>>;
constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }
void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

bool dfs (const graph_t& graph, int target, int from, std::bitset<max_cities>& visited) {
	visited.set(u(from - 1));
	for (const auto& to : graph[u(from - 1)]) {
		if (
			to == target ||
			!visited.test(u(to - 1)) &&
			dfs(graph, target, to, visited)
		) return true;
	}
	return false;
}

int main () {
	fastio();
	int cities_num {}, roads_num {};
	std::cin >> cities_num >> roads_num;
	graph_t graph(u(cities_num));
	while (roads_num--) {
		int from {}, to {};
		std::cin >> from >> to;
		graph[u(from - 1)].push_back(to);
	}
	int from {}, target {};
	std::cin >> from >> target;
	std::bitset<max_cities> visited {};
	if (dfs(graph, target, from, visited)) std::cout << "Yes\n";
	else std::cout << "No\n";
	return 0;
}
```

### a102: 油田
是的，完全沒在最佳化。

```cpp=
#pragma GCC optimize("O3")

#include <bitset>
#include <iostream>

constexpr int max_width {100 + 2};
using ground_t = std::bitset<max_width * max_width>;
constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }
void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

void clear_nearby (ground_t& ground, int pos) {
	static constexpr int near[] {
		-max_width - 1, -max_width, -max_width + 1,
		-1, +1,
		+max_width - 1, +max_width, +max_width + 1
	};
	if (!ground[u(pos)]) return;
	ground[u(pos)] = false;
	for (const auto& diff : near) clear_nearby(ground, pos + diff);
}

int main () {
	fastio();
	while (true) {
		int rows {}, colums {};
		std::cin >> rows >> colums;
		if (rows == 0) return 0;
		ground_t ground {};
		for (int y {1}; y <= rows; y++) {
			for (int x {1}; x <= colums; x++) {
				char symbol {};
				std::cin >> symbol;
				if (symbol == '@') ground[u(y * max_width + x)] = true;
			}
		}
		int number {0};
		while (true) {
			int pos {};
			while (pos < ground.size() && !ground[u(pos)]) pos++;
			if (pos == ground.size()) break;
			number++;
			clear_nearby(ground, pos);
		}
		std::cout << number << '\n';
	}
}
```

### a103: 小群體
```cpp=
#pragma GCC optimize("O3")

#include <iostream>
#include <vector>

constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }
void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

int main () {
	fastio();
	int people {};
	std::cin >> people;
	std::vector<int> friend_map(people);
	for (auto& frind : friend_map) std::cin >> frind;
	int grounps {};
	for (int i = 0; i < people; i++) {
		int pos {i};
		do {
			const int temp {friend_map[u(pos)]};
			friend_map[u(pos)] = -1;
			pos = temp;
		} while (pos != -1 && pos != i);
		if (pos != -1) grounps++;
	}
	std::cout << grounps << '\n';
    return 0;
}
```

### a124: 二分圖
題目描述直接給思路是不是太過貼心了。

還有另一種更好但更麻煩的解法懶得弄了。

```cpp=
#pragma GCC optimize("O3")

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

template <typename T>
constexpr std::size_t u (T i) { return static_cast<std::size_t>(i); }
void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

int main () {
	fastio();
	int vertices_num {}, edges_num {};
	std::cin >> vertices_num >> edges_num;
	std::vector<std::vector<int>> graph(u(vertices_num));
	while (edges_num--) {
		int from {}, to {};
		std::cin >> from >> to;
		graph[u(from - 1)].push_back(to - 1);
		graph[u(to - 1)].push_back(from - 1);
	}
	// std::vector<bool>
	std::vector<char> visited(u(vertices_num));
	std::vector<char> color(u(vertices_num));
	int answer {0};
	while (true) {
		int id {-1};
		while (++id < vertices_num && visited[u(id)]) {}
		if (id == vertices_num) break;
		std::stack<int> to_visit {};
		to_visit.push(id);
		int white {1};
		int black {0};
		visited[u(id)] = true;
		while (!to_visit.empty()) {
			const int now {to_visit.top()};
			to_visit.pop();
			for (const auto& near : graph[u(now)]) {
				if (visited[u(near)] && color[u(near)] == color[u(now)]) {
					std::cout << "0\n";
					return 0;
				}
				if (visited[u(near)]) continue;
				visited[u(near)] = true;
				color[u(near)] = !color[u(now)];
				if (color[u(near)]) black++;
				else white++;
				to_visit.push(near);
			}
		}
		answer += std::min(black, white);
	}
	std::cout << answer << '\n';
	return 0;
}
```

### a125: 觀光景點

```cpp=
#pragma GCC optimize("O3")

#include <iostream>
#include <stack>
#include <utility>
#include <vector>
#include <bitset>

template <typename T>
constexpr std::size_t u (T i) { return static_cast<std::size_t>(i); }
void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

int main () {
	fastio();
	int vertices_num {}, root {}, max_cost {};
	std::cin >> vertices_num >> root >> max_cost;
	std::vector<std::vector<std::pair<int, int>>> graph(u(vertices_num));
	for (int i {0}; i < vertices_num - 1; i++) {
		int from {}, to {}, cost {};
		std::cin >> from >> to >> cost;
		graph[u(from - 1)].emplace_back(to - 1, cost);
		graph[u(to - 1)].emplace_back(from - 1, cost);
	}
	std::stack<int> to_visit {};
	std::bitset<5000> visited {};
	visited.set(u(root - 1));
	to_visit.push(root - 1);
	int answer {0};
	while (!to_visit.empty()) {
		const int vertex {to_visit.top()};
		to_visit.pop();
		for (const auto& edge : graph[u(vertex)]) {
			if (visited[u(edge.first)] || edge.second < max_cost) continue;
			answer++;
			to_visit.push(edge.first);
			visited.set(u(edge.first));
		}
	}
	std::cout << answer << '\n';
	return 0;
}
```

### a126: 馬步問題
嘛不是很好看。罷了。
```cpp=
#include <bitset>
#include <iostream>
#include <stack>
#include <vector>

constexpr inline std::size_t u (int i) { return static_cast<std::size_t>(i); }

int main () {
	static constexpr int dx[] {
		1, 1, -1, -1, 2, 2, -2, -2
	};
	static constexpr int dy[] {
		2, -2, 2, -2, 1, -1, 1, -1
	};
	constexpr int row {3};
	constexpr int max_colum {10};

	int colum {};
	std::cin >> colum;
	const int length {colum * row};
	std::vector<int> way {};
	std::vector<int> answer(u(length), 100);
	std::stack<int> chooses {};
	std::bitset<row* max_colum> visited {};
	chooses.push(-1);
	way.push_back(0);
	visited[0] = true;
	while (!chooses.empty()) {
		const int choose {++chooses.top()};
		if (choose == 8) {
			chooses.pop();
			visited[u(way.back())] = false;
			way.pop_back();
			continue;
		}
		const int x {way.back() % colum + dx[choose]};
		const int y {way.back() / colum + dy[choose]};
		const int pos {y * colum + x};
		if (x >= colum || x < 0 || y >= row || y < 0 || visited[u(pos)]) continue;
		way.push_back(pos);
		visited[u(pos)] = true;
		if (way.size() != length) {
			chooses.push(-1);
			continue;
		}
		std::vector<int> temp(u(length));
		for (int i = 0; i < length; i++) temp[u(way[u(i)])] = i + 1;
		if (temp < answer) answer = temp;
		chooses.push(7);
	}
	if (answer[0] == 100) {
		std::cout << "0\n";
		return 0;
	}
	for (const auto& x : answer) std::cout << x << ' ';
	std::cout << '\n';
	return 0;
}
```

## 10. [基礎演算法 I ] 複雜度分析、排序
### a127: 連號或不連號

我宣布這是最簡單的一題，沒有之一。

```cpp=
#include <iostream>

int main () {
	int num {};
	std::cin >> num;
	int min {1000};
	int max {0};
	for (int i = 0; i < num; i++) {
		int number {};
		std::cin >> number;
		if (max < number) max = number;
		if (min > number) min = number;
	}
	std::cout << min << ' ' << max << ' ' <<
		(max - min + 1 == num ? "yes" : "no");
	return 0;
}
```

### a148: 字元頻率
糾結了一下要用 `std::vector` + `std::sort` 還是直接用 `std::priority_queue`。

```cpp=
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

int main () {
	std::string line {};
	while (std::getline(std::cin, line)) {
		std::map<int, int> nums {};
		for (const auto& c : line) nums[c]++;
		std::vector<std::pair<int, int>> answer(nums.begin(), nums.end());
		std::sort(answer.begin(), answer.end(), [](const auto& a, const auto& b) {
			return a.second == b.second ? a.first > b.first : a.second < b.second;
		});
		for (const auto& ele : answer) std::cout << ele.first << ' ' << ele.second << '\n';
		std::cout << '\n';
	}
	return 0;
}
```

### a128: Agar.io
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>

template<typename T>
void merge (std::vector<T>& to, const std::vector<T>& from) {
	to.insert(to.end(), from.begin(), from.end());
}

int main () {
	std::size_t number {};
	int times {};
	std::cin >> number >> times;
	std::vector<std::vector<int>> cells(number);
	for (int i {0}; i < number; i++) cells[static_cast<std::size_t>(i)].push_back(i + 1);
	while (times--) {
		std::size_t a {}, b {};
		std::cin >> a >> b;
		a--;
		b--;
		if (cells[b].size() > cells[a].size()) merge(cells[b], cells[a]);
		else merge(cells[a], cells[b]);
	}
	const auto max {std::max_element(cells.begin(), cells.end(), [](const auto& a, const auto& b) {
		return a.size() < b.size();
	})};
	std::cout << max - cells.begin() + 1 << '\n';
	std::sort(max->begin(), max->end());
	for (const auto& eat : *max) std::cout << eat << ' ';
	std::cout << '\n';
	return 0;
}
```

### a129: 飛天桑妮
這題其實我少考慮情況 $d(t_1, t_{\pi(i+1)}) = d(t_1, t_{\pi(i)})$，不過顯然寫測資的人也沒考慮到，所以管他的。
```cpp=
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

int main () {
	fastio();
	std::size_t trees_num {};
	std::cin >> trees_num;
	std::vector<std::pair<int, int>> trees(trees_num);
	for (auto& tree : trees) {
		int x {}, y {}, hight {};
		std::cin >> x >> y >> hight;
		tree.first = x * x + y * y;
		tree.second = hight;
	}
	std::sort(trees.begin(), trees.end());
	int happyness {0};
	int highest {0};
	for (const auto& tree : trees) {
		highest = std::max(highest, tree.second);
		happyness = std::max(happyness, highest - tree.second);
	}
	std::cout << happyness << '\n';
	return 0;
}
```

## 11. [基礎演算法 I ] 排序與搜尋
### a152: 二分搜尋
就先不邪道了，乖乖寫。

```cpp=
#include <iostream>
#include <vector>

int main () {
	std::size_t length {};
	std::cin >> length;
	std::vector<int> numbers(length);
	for (auto& number : numbers) std::cin >> number;
	int target {};
	std::cin >> target;
	std::size_t left {0}; // closed
	std::size_t right {length}; // open
	int times {0};
	while (left != right) {
		times++;
		const std::size_t middle {(right - left + 1) / 2 + left - 1};
		if (numbers[middle] > target)  right = middle;
		else if (numbers[middle] < target) left = middle + 1;
		else {
			std::cout << middle << ' ' << times << '\n';
			return 0;
		}
	}
	std::cout << "not found " << times << '\n';
	return 0;
}
```

### a153: 二分法求解
我知道大家都有種寫 `std::log(2)` 的衝動，不過姑且假裝自己不知道函式長怎樣一下。

```cpp=
#include <cmath>
#include <iostream>

using num_t = double;

num_t f (num_t x) { return 2 - std::exp(x); }
constexpr num_t bigger {1};
constexpr num_t lower {0};
constexpr num_t TOL {1.0e-8};

int main () {
	num_t max {bigger};
	num_t min {lower};
	while (std::abs(f(max) - f(min)) > TOL) {
		const num_t middle {(min + max) / 2};
		if (f(middle) > 0 == f(min) > 0) min = middle;
		else max = middle;
	}
	std::cout << min << '\n';
	return 0;
}
```

### a290: 完美購書計畫

很醜。

```cpp=
#include <map>
#include <iostream>

int main () {
	int books_num {};
	while (std::cin >> books_num) {
		std::map<int, int> books {};
		while (books_num--) {
			int book {};
			std::cin >> book;
			books[book]++;
		}
		int target {};
		std::cin >> target;
		const int halfTarget {target / 2};
		int answer {target + 1};
		if (target % 2 == 0) {
			const auto half {books.find(halfTarget)};
			if (half != books.end()) {
				if (half->second >= 2) answer = 0;
				else books.erase(half);
			}
		}
		for (auto book {books.begin()}; book != books.end(); books.erase(book++)) {
			if (!answer || book->first > halfTarget) break;
			const auto need {books.find(target - book->first)};
			if (need == books.end()) continue;
			books.erase(need);
			answer = std::min(answer, halfTarget - book->first);
		}
		std::cout << "Peter should buy books whose prices are " <<
			halfTarget - answer << " and " << halfTarget + answer + target % 2 << ".\n\n";
	}
	return 0;
}
```

### a130: 人員調動

```cpp=
#include <iostream>
#include <set>
#include <utility>

int main () {
	int tests {};
	std::cin >> tests;
	while (tests--) {
		int peoples {};
		std::cin >> peoples;
		std::multiset<std::pair<int, int>> pairs {};
		int count {};
		while (peoples--) {
			int from {}, to {};
			std::cin >> from >> to;
			const auto reverse {pairs.find({to, from})};
			if (reverse == pairs.end()) {
				pairs.emplace(from, to);
			} else {
				count++;
				pairs.erase(reverse);
			}
		}
		std::cout << count << '\n';
	}
	return 0;
}
```

### a131: 大黑馬
來點比較舒服的寫法。

```cpp=
#include <iostream>
#include <vector>

constexpr inline std::size_t u (int i) { return static_cast<std::size_t>(i); }

struct Team {
	int seed {};
	int length {};
	std::vector<int> average {};
	std::vector<int> best {};
	std::vector<int> worse {};

	Team (int length) : length {length}, average(u(length)), best(u(length)), worse(u(length)) {}
};

bool canBeat (const Team& team, const Team& opponent, bool chance) {
	if (team.seed == opponent.seed) return true;
	const int half {team.length / 2};
	const auto& our_players {chance ? team.best : team.average};
	const auto& opponent_players {chance ? opponent.worse : opponent.average};
	for (int i {0}; i < half + 1; i++) {
		const int our_bp {our_players[u(i)]};
		const int opponent_bp {opponent_players[u(half + i)]};
		if (opponent_bp > our_bp || opponent_bp == our_bp && opponent.seed < team.seed) return false;
	}
	return true;
}

bool canWin (const Team& team, const std::vector<Team>& teams, bool chance) {
	for (const auto& opponent : teams) {
		if (!canBeat(team, opponent, chance)) return false;
	}
	return true;
}

int getBlackHorse (const std::vector<Team>& teams, bool chance) {
	int blackHorse {0};
	for (const auto& team : teams) {
		if (team.seed > blackHorse && canWin(team, teams, chance)) blackHorse = team.seed;
	}
	return blackHorse;
}

int main () {
	int players_half {}, teams_num {};
	std::cin >> players_half >> teams_num;
	std::vector<Team> teams(u(teams_num), Team(players_half * 2 + 1));
	for (auto& team : teams) {
		std::cin >> team.seed;
		for (auto& bp : team.average) std::cin >> bp;
		for (auto& bp : team.best) std::cin >> bp;
		for (auto& bp : team.worse) std::cin >> bp;
	}
	std::cout << getBlackHorse(teams, false) << ' ' << getBlackHorse(teams, true) << '\n';
	return 0;
}
```

### a132: 主機排程
```cpp=
#include <iostream>
#include <map>
#include <utility>

struct Cost {
	int core {0};
	int ram {0};
	int bw {0};

	Cost& operator+= (const Cost& b) {
		core += b.core;
		ram += b.ram;
		bw += b.bw;
		return *this;
	}

	Cost& operator-= (const Cost& b) {
		core -= b.core;
		ram -= b.ram;
		bw -= b.bw;
		return *this;
	}

	void max (const Cost& b) {
		if (core < b.core) core = b.core;
		if (ram < b.ram) ram = b.ram;
		if (bw < b.bw) bw = b.bw;
	}
};

int main () {
	int tests {}, divisor {};
	std::cin >> tests >> divisor;
	divisor *= 24;
	while (tests--) {
		int processes_num {};
		std::cin >> processes_num;
		std::map<int, Cost> costs {};
		Cost now_cost {0, 0, 0};
		while (processes_num--) {
			int start_d {}, start_h {}, time {};
			std::cin >> start_d >> start_h >> time;
			const int start {(start_d - 1) * 24 + start_h};
			const int end {start + time};
			Cost cost {};
			std::cin >> cost.core >> cost.ram >> cost.bw;
			costs[start] += cost;
			costs[end % divisor] -= cost;
			if (end >= divisor) now_cost += cost;
		}
		std::cin >> processes_num; // ignore tail 0
		Cost max_cost {now_cost};
		for (const auto& cost : costs) {
			now_cost += cost.second;
			max_cost.max(now_cost);
		}
		std::cout << max_cost.core << ' ' <<
			max_cost.ram << ' ' <<
			max_cost.bw << '\n';
	}
	return 0;
}
```

## 12. [基礎演算法 I ] 窮舉法
### a088: 最大乘積
切三段分析法，另一種比較漂亮的等價方法之後再補。

```cpp=
#include <algorithm>
#include <iostream>

int main () {
	int test {1};
	int num {};
	while (std::cin >> num) {
		long long max_product {0};
		long long middle {1}, last {1}, first {0};
		bool avalible {false};
		do {
			int next {0};
			if (num) std::cin >> next;
			if (next == 0) {
				if (avalible) max_product = std::max({max_product, first * middle, last * middle, first * last * middle});
				first = 0;
				middle = 1;
				last = 1;
				avalible = false;
			} else if (next > 0) {
				last *= next;
				avalible = true;
			} else if (!first) {
				if (avalible) max_product = std::max(max_product, last);
				first = last * next;
				last = 1;
			} else {
				middle *= last;
				last = next;
				avalible = true;
			}
		} while (num--);
		std::cout << "Case #" << test++ << ": The maximum product is " << max_product << ".\n\n";
	}
	return 0;
}
```

### a133: 採蘑菇攻略問題
```cpp=
#include <iostream>
#include <utility>

int main () {
	int num {};
	std::cin >> num;
	int sum {0};
	int max_sum {0};
	while (num--) {
		int number {};
		std::cin >> number;
		sum = std::max(0, sum + number);
		max_sum = std::max(max_sum, sum);
	}
	std::cout << max_sum << '\n';
	return 0;
}
```

### a154: 除法
使用乘法直式的概念一位一位算，進行回朔與剪枝。

嗯……`result` 和 `answers` 的用法的確很噁心，有空我再想想怎改。

```cpp=
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

void check (int target, unsigned int used, int length, int carry, std::vector<int>& result, std::vector<int>& answers) {
	if (length == 5) {
		if (carry != 0) return;
		int x {0};
		for (auto i {result.rbegin()}; i != result.rend(); i++) x = x * 10 + *i;
		answers.push_back(x);
		return;
	}
	for (int i {0}; i <= 9; i++) {
		if (used & (1 << i)) continue;
		const int product {i * target + carry};
		const int j {product % 10};
		if (i == j || used & (1 << j)) continue;
		result.push_back(j);
		check(target, used | (1 << i) | (1 << j), length + 1, product / 10, result, answers);
		result.pop_back();
	}
}

int main () {
	std::cout << std::setfill('0');
	while (true) {
		int target {};
		std::cin >> target;
		if (!target) return 0;
		std::vector<int> answers {};
		std::vector<int> result {};
		check(target, 0, 0, 0, result, answers);
		if (answers.empty()) {
			std::cout << "There are no solutions for " << target << ".\n";
			continue;
		}
		std::sort(answers.begin(), answers.end());
		for (const auto& answer : answers) {
			std::cout << std::setw(5) << answer << " / " << std::setw(5) << answer / target << " = " << target << '\n';
		}
	}
}
```

### a134: 回文日期問題

```cpp=
#include <algorithm>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>

void is_palindrome (const std::string& str, std::vector<int>& output) {
	for (std::size_t i {0}; i < str.length() / 2 + 1; i++) {
		if (str[i] != str[str.length() - i - 1]) return;
	}
	output.push_back(std::stoi(str));
}

int main () {
	int tests {};
	std::cin >> tests;
	while (tests--) {
		int year {};
		std::cin >> year;
		const std::string yearstr {std::to_string(year)};
		year = (year + 100) % 1000;
		std::tm date {};
		date.tm_year = year;
		date.tm_mday = 1;
		std::vector<int> answers {};
		while (date.tm_year == year) {
			const std::string monstr {std::to_string(date.tm_mon + 1)};
			const std::string daystr {std::to_string(date.tm_mday)};
			is_palindrome(yearstr + monstr + daystr, answers);
			if (monstr.length() == 1) is_palindrome(yearstr + "0" + monstr + daystr, answers);
			if (daystr.length() == 1) is_palindrome(yearstr + monstr + "0" + daystr, answers);
			if (monstr.length() == 1 && daystr.length() == 1) is_palindrome(yearstr + "0" + monstr + "0" + daystr, answers);
			date.tm_mday++;
			std::mktime(&date);
		}
		std::sort(answers.begin(), answers.end());
		std::cout << answers.size();
		for (const auto& answer : answers) std::cout << ' ' << answer;
		std::cout << '\n';
	}
	return 0;
}
```

### a135: 巧克力擺盒
位元運算大法好，效率特高。

```cpp=
#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

struct Row {
	std::pair<char, char> a {};
	std::pair<char, char> b {};
	std::pair<char, char> c {};
	unsigned int used {0};
	unsigned int conditions {0};
};

int main () {
	std::vector<std::pair<char, char>> chocolates {};
	for (const auto& f : {'B', 'P', 'Y'}) {
		for (const auto& s : {'C', 'S', 'T'}) chocolates.emplace_back(f, s);
	}
	std::vector<Row> rows {};
	std::vector<unsigned int> nums(9);
	std::iota(nums.begin(), nums.end(), 0);
	do {
		rows.push_back({
			chocolates[nums[0]], chocolates[nums[1]], chocolates[nums[2]],
			static_cast<unsigned int>(1 << nums[0] | 1 << nums[1] | 1 << nums[2])
		});
		std::reverse(nums.begin() + 3, nums.end());
	} while (std::next_permutation(nums.begin(), nums.end()));
	int rules_num {};
	std::cin >> rules_num;
	unsigned int pass_all {0};
	unsigned int pass {1};
	while (rules_num--) {
		int type {};
		std::cin >> type;
		if (type == 2) {
			char a_f {}, a_s {}, b_f {}, b_s {};
			std::cin >> a_f >> a_s >> b_f >> b_s;
			for (auto& row : rows) {
				if (
					(a_f == '?' || a_f == row.a.first) &&
					(a_s == '?' || a_s == row.a.second) &&
					(b_f == '?' || b_f == row.b.first) &&
					(b_s == '?' || b_s == row.b.second) ||
					(a_f == '?' || a_f == row.b.first) &&
					(a_s == '?' || a_s == row.b.second) &&
					(b_f == '?' || b_f == row.c.first) &&
					(b_s == '?' || b_s == row.c.second)
				) row.conditions |= pass;
			}
		} else {
			char a_f {}, a_s {}, b_f {}, b_s {}, c_f {}, c_s {};
			std::cin >> a_f >> a_s >> b_f >> b_s >> c_f >> c_s;
			for (auto& row : rows) {
				if (
					(a_f == '?' || a_f == row.a.first) &&
					(a_s == '?' || a_s == row.a.second) &&
					(b_f == '?' || b_f == row.b.first) &&
					(b_s == '?' || b_s == row.b.second) &&
					(c_f == '?' || c_f == row.c.first) &&
					(c_s == '?' || c_s == row.c.second)
				) row.conditions |= pass;
			}
		}
		pass_all |= pass;
		pass <<= 1;
	}
	int answer {0};
	for (auto a {rows.begin()}; a != rows.end(); a++) {
		for (auto b {a + 1}; b != rows.end(); b++) {
			if (a->used & b->used) continue;
			const unsigned int condition_ab {a->conditions | b->conditions};
			const unsigned int used_ab {a->used | b->used};
			for (auto c {b + 1}; c != rows.end(); c++) {
				if (!(used_ab & c->used) && (condition_ab | c->conditions) == pass_all) answer += 6;
			}
		}
	}
	std::cout << answer << '\n';
	return 0;
}
```

## 13. [基礎資料結構 II 及基礎演算法 II ] 貪婪法
### a091: 加總的代價

```cpp=
#include <iostream>
#include <queue>
#include <vector>

int main () {
	while (true) {
		int numbers_count {};
		std::cin >> numbers_count;
		if (!numbers_count) return 0;
		std::priority_queue<int, std::vector<int>, std::greater<int>> numbers {};
		while (numbers_count--) {
			int number {};
			std::cin >> number;
			numbers.push(number);
		}
		long long cost {0};
		while (numbers.size() > 1) {
			int sum {numbers.top()};
			numbers.pop();
			sum += numbers.top();
			numbers.pop();
			numbers.push(sum);
			cost += sum;
		}
		std::cout << cost << '\n';
	}
}
```

### a071: 排隊買飲料
真就照題目說的模擬。

```cpp=
#include <iostream>
#include <vector>

int main () {
	int customers_count {};
	std::cin >> customers_count;
	std::size_t staffs_count {};
	std::cin >> staffs_count;
	std::vector<int> staffs(staffs_count, 0);
	int clock {-1};
	bool conti {true};
	while (conti) {
		clock++;
		conti = false;
		for (auto& staff : staffs) {
			if (staff != 0) staff--;
			if (!staff && customers_count) {
				std::cin >> staff;
				customers_count--;
				conti = true;
			} else if (staff) conti = true;
		}
	}
	std::cout << clock << '\n';
	return 0;
}
```

### a141: 基地台
所以[二分法求解](#a153-二分法求解)為什麼不用這題？

```cpp=
#include <algorithm>
#include <cmath>
#include <iostream>
#include <set>
#include <stdexcept>
#include <vector>

void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }

bool is_distance_possible (const std::vector<int>& points, int max_number, int distance) {
	int number {1};
	int left_point {points[0]};
	for (const auto& point : points) {
		if (point - left_point <= distance) continue;
		number++;
		if (number > max_number) return false;
		left_point = point;
	}
	return true;
}

int main() {
	fastio();
	std::set<int> possible_disances {};
	int points_num {};
	int max_number {};
	std::cin >> points_num >> max_number;
	std::vector<int> points(points_num);
	for (auto& point : points) std::cin >> point;
	std::sort(points.begin(), points.end());
	int max {points.back() - points.front()};
	int min {0};
	while (max - min > 1) {
		const int middle {(max + min) / 2};
		if (is_distance_possible(points, max_number, middle)) max = middle;
		else min = middle;
	}
	std::cout << max;
	return 0;
}
```

### a139: 背包置物問題

```cpp=
#include <algorithm>
#include <iostream>
#include <istream>
#include <set>
#include <vector>

int main() {
	int books_num {};
	int max_carry {};
	std::cin >> books_num >> max_carry;
	std::vector<int> needs {};
	int input {};
	while (std::cin >> input) {
		needs.push_back(max_carry);
		max_carry = input;
	}
	std::set<int> bag {};
	int times {0};
	for (auto need {needs.begin()}; need != needs.end(); need++) {
		if (bag.count(*need)) continue;
		if (bag.size() < max_carry) {
			bag.insert(*need);
			continue;
		}
		bag.erase(std::max_element(bag.begin(), bag.end(), [&need, &needs](int a, int b) {
			const auto a_next_use {std::find(need, needs.end(), a)};
			const auto b_next_use {std::find(need, needs.end(), b)};
			return a_next_use < b_next_use;
		}));
		bag.insert(*need);
		times++;
	}
	std::cout << times << '\n';
	return 0;
}
```

### a075: 醜數

比較簡單的貪婪解：
```cpp=
#include <iomanip>
#include <iostream>
#include <set>

int main() {
	static const int factors[] {2, 3, 5};
	int n {};
	std::cin >> n;
	std::set<int> ugly {};
	ugly.insert(1);
	while (--n) {
		const auto first {ugly.begin()};
		for (const int x : {2, 3, 5}) ugly.insert(*first * x);
		ugly.erase(first);
	}
	std::cout << *ugly.begin();
	return 0;
}
```

較為複雜但有極小的一咪咪提升的動態規劃解：
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
	int n {};
	std::cin >> n;
	std::vector<int> ugly {1};
	ugly.reserve(n);
	auto i2 {ugly.begin()}, i3 {i2}, i5 {i2};
	while (--n) {
		const int x2 {*i2 * 2}, x3 {*i3 * 3}, x5 {*i5 * 5};
		int next = std::min({x2, x3, x5});
		ugly.push_back(next);
		if (x2 == next) i2++;
		if (x3 == next) i3++;
		if (x5 == next) i5++;
	}
	std::cout << ugly.back() << '\n';
	return 0;
}
```

## 14. [基礎資料結構 II 及基礎演算法 II ] 分而治之與回溯法
### a165: 最近點對問題
就照課本說的寫。

```cpp=
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <utility>
#include <vector>

void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); }
constexpr long long max_distance {10000 * 10000 + 1};
using Point = std::pair<long long, long long>;

long long distance (Point a, Point b) {
	const long long dx {a.first - b.first};
	const long long dy {a.second - b.second};
	return std::min(dx * dx + dy * dy, max_distance);
}

long long get_min_distance (const std::vector<Point>& points, std::size_t from, std::size_t to) {
	if (to == from) return max_distance;
	const std::size_t middle {(from + to) / 2};
	long long min_distance {std::min(get_min_distance(points, from, middle), get_min_distance(points, middle + 1, to))};
	for (std::size_t i {middle}; i >= from && i != -1; i--) {
		if (points[middle].first - points[i].first > min_distance) break;
		for (std::size_t j {middle + 1}; j <= to; j++) {
			if (points[j].first - points[middle].first > min_distance) break;
			min_distance = std::min(min_distance, distance(points[i], points[j]));
		}
	}
	return min_distance;
}

int main() {
	fastio();
	std::cout << std::fixed << std::setprecision(4);
	while (true) {
		std::size_t points_num {};
		std::cin >> points_num;
		if (!points_num) return 0;
		std::vector<Point> points(points_num);
		for (auto& point : points) std::cin >> point.second >> point.first;
		std::sort(points.begin(), points.end());
		const long long min_distance {get_min_distance(points, 0, points.size() - 1)};
		if (min_distance == max_distance) std::cout << "INFINITY\n";
		else std::cout << std::sqrt(min_distance) << '\n';
	}
}
```

### a089: 蘇丹王位繼承者
先解完八皇后再解題目。

```cpp=
#include <iomanip>
#include <iostream>
#include <vector>

constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }

bool check (const std::vector<int>& choose) {
	int y {static_cast<int>(choose.size() - 1)};
	if (y == 0) return true;
	for (int i {0}; i < y; i++) {
		if (
			choose.back() == choose[u(i)] ||
			choose.back() + y == choose[u(i)] + i ||
			choose.back() - y == choose[u(i)] - i
		) return false;
	}
	return true;
}

auto solve8qreen () {
	std::vector<std::vector<int>> results {};
	std::vector<int> choose {-1};
	while (!choose.empty()) {
		choose.back()++;
		if (choose.back() == 8) {
			choose.pop_back();
			continue;
		}
		if (!check(choose)) continue;
		if (choose.size() == 8) results.push_back(choose);
		else choose.push_back(-1);
	}
	return results;
}

int main () {
	auto soluctions {solve8qreen()};
	int tests {};
	std::cin >> tests;
	while (tests--) {
		std::vector<std::vector<int>> board (8, std::vector<int>(8));
		for (auto& row : board) for (auto& grid : row) std::cin >> grid;
		int max_sum {-1};
		for (const auto& soluction : soluctions) {
			int sum {0};
			for (int i {0}; i < 8; i++) sum += board[u(i)][u(soluction[u(i)])];
			if (sum > max_sum) max_sum = sum;
		}
		std::cout << std::setw(5) << max_sum << '\n';
	}
	return 0;
}
```

### a090: 質數環
好看什麼的之後再說。

```cpp=
#include <algorithm>
#include <iostream>
#include <vector>

constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }

bool has (const std::vector<int>& array, int element) {
	return std::find(array.begin(), array.end(), element) != array.end();
}

auto generatePrimes (int max) {
	std::vector<int> primes {2};
	const auto isPrime {[&primes](int x) {
		for (const auto& prime : primes) {
			if (x % prime == 0) return false;
		}
		return true;
	}};
	while (primes.back() < max) {
		int x {primes.back() + 1};
		while (!isPrime(x)) x++;
		primes.push_back(x);
	}
	return primes;
}

auto generatePairs (int max) {
	std::vector<int> primes {generatePrimes(max * 2 - 1)};
	std::vector<std::vector<int>> pairs(u(max));
	for (int i {1}; i <= max; i += 2) {
		for (int j {2}; j <= max; j += 2) {
			if (!has(primes, i + j)) continue;
			pairs[u(i - 1)].push_back(j);
			pairs[u(j - 1)].push_back(i);
		}
	}
	return pairs;
}


int main () {
	const auto pairs {generatePairs(16)};
	int cases {1};
	int length {};
	while (std::cin >> length) {
		std::vector<std::vector<int>> answers {};
		std::vector<int> choose {-1};
		std::vector<int> numbers {1};
		while (!choose.empty()) {
			int next {++choose.back()};
			auto& list {pairs[u(numbers.back() - 1)]};
			if (numbers.size() == length) {
				if (has(pairs[0], numbers.back())) answers.push_back(numbers);
			}
			if (numbers.size() == length || next >= list.size() || list[u(next)] > length) {
				choose.pop_back();
				numbers.pop_back();
				continue;
			};
			if (has(numbers, list[u(next)])) continue;
			numbers.push_back(list[u(next)]);
			choose.push_back(-1);
		}
		std::cout << "Case " << cases << ":\n";
		for (const auto& answer : answers) {
			for (const auto& number : answer) std::cout << number << ' ';
			std::cout << '\n';
		}
		std::cout << '\n';
		cases++;
	}
	return 0;
}
```

### a286: 23
乘法的部分還是剪的，只是要倒過來算。

```cpp=
#include <bitset>
#include <iostream>
#include <vector>

bool test (int level, int x, const std::bitset<5>& used, const std::vector<int>& numbers) {
	if (level == 5) return x == 0;
	for (std::size_t i {0}; i < 5; i++) {
		if (used[i]) continue;
		const std::bitset<5> new_used {used | std::bitset<5>(1 << i)};
		if (level < 4 && x % numbers[i] == 0 && test(level + 1, x / numbers[i], new_used, numbers)) return true;
		if (level < 4 && test(level + 1, x + numbers[i], new_used, numbers)) return true;
		if (test(level + 1, x - numbers[i], new_used, numbers)) return true;
	}
	return false;
}

int main() {
	while (true) {
		std::vector<int> numbers(5);
		for (auto& n : numbers) std::cin >> n;
		if (numbers[0] == 0) return 0;
		if (test(0, 23, std::bitset<5>{}, numbers)) std::cout << "Possible\n";
		else std::cout << "Impossible\n";
	}
}
```

### a142: 無刻度容器倒水問題
這題是圖論之廣度優先搜尋。

只有兩杯那倒法就不用迴圈寫法了。

```cpp=
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <utility>


int soluction () {
	using pii = std::pair<int, int>;

	int a_limit {}, b_limit {}, target {};
	std::cin >> a_limit >> b_limit >> target;
	std::queue<pii> visiting {}, to_visit {};
	visiting.emplace(0, 0);
	std::set<pii> visited {{0, 0}};

	const auto visit {[&visited, &to_visit, target] (pii state) {
		if (state.first == target || state.second == target) return true;
		if (visited.count(state)) return false;
		to_visit.push(state);
		visited.insert(state);
		return false;
	}};

	int depth {1};
	while (!visiting.empty()) {
		pii now {visiting.front()};
		visiting.pop();
		const int sum {now.first + now.second};
		
		if (
			visit({now.first, 0}) ||
			visit({0, now.second}) ||
			visit({now.first, b_limit}) ||
			visit({a_limit, now.second}) ||
			visit({std::max(sum - b_limit, 0), std::min(sum, b_limit)}) ||
			visit({std::min(sum, a_limit), std::max(sum - a_limit, 0)})
		) return depth;

		if (!visiting.empty()) continue;
		std::swap(visiting, to_visit);
		depth++;
	}
	return -1;
}

int main () {
	int tests {};
	std::cin >> tests;
	while (tests--) std::cout << soluction() << '\n';
	return 0;
}
```

## 15. [基礎資料結構 II 及基礎演算法 II ] 動態規劃
### a098: 計算方法數

法一：

```cpp=
#include <iostream>
#include <numeric>
#include <vector>

constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }

int main () {
	const std::vector<int> coins {1, 5, 10, 25, 50};
	// dp[sum][last use] = method types
	std::vector<std::vector<long long>> dp {{1}};
	int target {};
	while (std::cin >> target) {
		for (int i {static_cast<int>(dp.size())}; i <= target; i++) {
			dp.emplace_back(coins.size(), 0);
			for (int j {0}; j < coins.size(); j++) {
				if (coins[u(j)] == i) dp[i][j] = 1;
				if (coins[u(j)] >= i) break;
				for (int k {0}; k <= j; k++) dp[u(i)][u(j)] += dp[u(i - coins[u(j)])][u(k)];
			}
		}
		const long long answer {std::accumulate(dp[u(target)].begin(), dp[u(target)].end(), 0LL)};
		if (answer == 1) {
			std::cout << "There is only 1 way to produce ";
		} else {
			std::cout << "There are " << answer << " ways to produce ";
		}
		std::cout << target << " cents change.\n";
	}
	return 0;
}
```

法二：

```cpp=
#include <iostream>
#include <vector>

constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); }

int main () {
	std::vector<long long> methods(30000 + 1, 0);
	methods[0] = 1;
	for (const int coin : {1, 5, 10, 25, 50}) {
		for (int i {coin}; i <= 30000; i++) {
			methods[u(i)] += methods[u(i - coin)];
		}
	}
	int target {};
	while (std::cin >> target) {
		if (methods[u(target)] == 1) {
			std::cout << "There is only 1 way to produce ";
		} else {
			std::cout << "There are " << methods[u(target)] << " ways to produce ";
		}
		std::cout << target << " cents change.\n";
	}
	return 0;
}
```

### a155: 雙子星塔

```cpp=
#include <algorithm>
#include <iostream>
#include <vector>

int main () {
	for (int test {1}; ; test++) {
		std::size_t a_hight {}, b_hight {};
		std::cin >> a_hight >> b_hight;
		if (!a_hight) return 0;
		std::vector<int> a_tower(a_hight);
		for (auto& brick : a_tower) std::cin >> brick;
		std::vector<int> b_tower(b_hight);
		for (auto& brick : b_tower) std::cin >> brick;
		std::vector<int> dp1(b_hight, 0), dp2(b_hight, 0);
		for (std::size_t i {0}; i < a_hight; i++) {
			for (std::size_t j {0}; j < b_hight; j++) {
				dp2[j] = std::max({
					dp1[j],
					j == 0 ? 0 : dp2[j - 1],
					(j == 0 ? 0 :dp1[j - 1]) + (a_tower[i] == b_tower[j])
				});
			}
			std::swap(dp1, dp2);
		}
		std::cout << "Twin Towers #" << test <<
			"\nNumber of Tiles : " << dp1.back() << "\n\n";
	}
}
```

### a144: 農作物採收問題

```cpp=
#include <algorithm>
#include <iostream>
#include <vector>

int main () {
	int width {};
	std::cin >> width;
	std::vector<std::vector<int>> field(width, {0});
	for (auto& row : field) {
		for (int i {0}; i < width; i++) {
			int block {};
			std::cin >> block;
			row.push_back(row.back() + block);
		}
	}
	int max {0};
	for (std::size_t from {0}; from < width; from++) {
		for (std::size_t to {from}; to < width; to++) {
			int sum {0};
			for (const auto& row : field) {
				sum = std::max(sum + row[to + 1] - row[from], 0);
				max = std::max(max, sum);
			}
		}
	}
	std::cout << max << '\n';
}
```

### a101: 分銅幣

實在想不到，只好作弊用位元運算了。
```cpp=
#include <bitset>
#include <cmath>
#include <iostream>
#include <set>

int main () {
	constexpr std::size_t maxdiff {500 * 100};
	int tests {};
	std::cin >> tests;
	while (tests--) {
		std::bitset<maxdiff> diffs {0b1};
		int coins {};
		std::cin >> coins;
		while (coins--) {
			unsigned int coin {};
			std::cin >> coin;
			std::bitset<maxdiff> diffs_new {(diffs << coin) | (diffs >> coin)};
			for (std::size_t i {0}; i < coin; i++) {
				if (!diffs[i]) continue;
				diffs_new[coin - i] = true;
			}
			diffs = std::move(diffs_new);
		}
		for (std::size_t i {0}; i < maxdiff; i++) {
			if (!diffs[i]) continue;
			std::cout << i << '\n';
			break;
		}
	}
	return 0;
}
```

### a143: 關鍵字搜尋模擬

```cpp=
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

float getScore (const std::string& a, const std::string& b) {
	int max {0};
	std::vector<int> dp(b.size(), 0);
	for (std::size_t i {0}; i < a.size(); i++) {
		for (std::size_t j {b.size() - 1}; j != -1; j--) {
			if (a[i] == b[j]) dp[j] = (j == 0 ? 0 : dp[j - 1]) + 1;
			else dp[j] = 0;
			if (dp[j] > max) max = dp[j];
		}
	}
	return static_cast<float>(max) / a.size();
}

int main() {
	std::vector<std::string> searchs {};
	std::string input {};
	std::getline(std::cin, input);
	{
		std::stringstream sstream {input};
		while (sstream >> input) searchs.push_back(input);
	}
	int files_num {};
	std::cin >> files_num;
	std::vector<std::pair<int, int>> files {};
	bool flag {false};
	while (files_num--) {
		int id {};
		std::cin >> id;
		std::getline(std::cin, input);
		std::stringstream sstream {input};
		float scoreSum {};
		while (sstream >> input) {
			float score {};
			for (const auto& searchkeyword : searchs) score = std::max(score, getScore(searchkeyword, input));
			scoreSum += score;
		}
		if (scoreSum > 0) flag = true;
		files.emplace_back(id, std::round(scoreSum * 100));
	}
	std::sort(files.begin(), files.end(), [](const auto& a, const auto& b) {
		return a.second == b.second ? a.first < b.first : a.second > b.second;
	});
	if (!flag) {
		std::cout << "FALSE\n";
		return 0;
	}
	for (const auto& file : files) std::cout << file.first << ' ';
	std::cout << '\n';
	return 0;
}
```

### a145: 搬家規畫問題

```cpp=
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

int main () {
    std::vector<std::pair<int, int>> items {};
    {
        std::string input {};
        std::getline(std::cin, input);
        std::stringstream sstream {input};
        int weight {};
        while (sstream >> weight) items.emplace_back(weight, 0);
    }
    for (auto& item : items) std::cin >> item.second;
    int max_weight {};
    std::cin >> max_weight;

    std::vector<int> max_values(max_weight + 1, 0);
    for (const auto& item : items) {
        for (std::size_t i {max_weight}; i >= item.first && i != -1; i--) {
            max_values[i] = std::max(max_values[i], max_values[i - item.first] + item.second);
        }
    }
    std::cout << max_values.back() << '\n';
}
```

## 16. [基礎資料結構 II 及基礎演算法 II ] 樹狀/圖形結構演算法
### a136: 元件測試排程問題
```cpp=
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

int main() {
	int items_num{}, needs_num{};
	std::cin >> items_num >> needs_num;
	std::vector<int> items(items_num);
	std::vector<std::pair<int, int>> edges(needs_num);
	for (auto& edge : edges) {
		char first{}, second{};
		std::cin >> first >> second;
		edge = { first - 'A', second - 'A' };
		items[edge.second]++;
	}
	std::queue<int> to_visit{};
	std::vector<int> sorted{};
	bool noanswer{ false };
	int lastuse{ -1 };
	for (int i{ 0 }; i < items_num; i++) {
		if (items[i] == 0) to_visit.push(i);
	}
	while (sorted.size() < items_num) {
		if (to_visit.empty()) {
			const auto& edge = edges.back();
			edges.pop_back();
			if (items[edge.first] == 0) continue;
			if (--items[edge.second] > 0) continue;
			to_visit.push(edge.second);
		}
		while (!to_visit.empty()) {
			const int now{ to_visit.front() };
			to_visit.pop();
			if (!noanswer && !to_visit.empty()) noanswer = true;
			sorted.push_back(now);
			for (const auto& edge : edges) {
				if (edge.first != now) continue;
				if (--items[edge.second] != 0) continue;
				to_visit.push(edge.second);
				if (edges.size() != needs_num) continue;
				lastuse = std::max(lastuse, static_cast<int>(std::find(edges.begin(), edges.end(), edge) - edges.begin()));
			}
		}
	}
	if (edges.size() != needs_num) std::cout << "Order conflict after getting pair " << edges.size() + 1 << '\n';
	else if (noanswer) std::cout << "No answer\n";
	else {
		std::cout << "Determine the testing sequence after getting pair " << lastuse + 1 << " : ";
		for (const auto& item : sorted) std::cout << static_cast<char>('A' + item);
		std::cout << '\n';
	}
	return 0;
}
```

### a137: 勇者冒險
```cpp=
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

int main() {
	using pos_t = std::pair<int, int>;
	int rows {}, columns {};
	std::cin >> rows >> columns;
	pos_t start {}, end {};
	std::cin >> start.first >> start.second >> end.first >> end.second;
	std::vector<std::vector<int>> map (rows, std::vector<int>(columns, -1));
	map[end.first][end.second] = 0;
	int blocks_num {};
	std::cin >> blocks_num;
	while (blocks_num--) {
		pos_t pos {};
		std::cin >> pos.first >> pos.second;
		std::cin >> map[pos.first][pos.second];
	}
	std::vector<std::vector<int>> min_levels (rows + 1, std::vector<int>(columns + 1, -1));
	min_levels[start.first][start.second] = 0;
	const auto comp = [&min_levels](pos_t a, pos_t b) {
		const int a_distance {min_levels[a.first][a.second]};
		const int b_distance {min_levels[b.first][b.second]};
		return a_distance > b_distance;
	};
	std::priority_queue<pos_t, std::vector<pos_t>, decltype(comp)> to_visit {comp};
	to_visit.push(start);

	while (!to_visit.empty()) {
		const pos_t pos {to_visit.top()};
		to_visit.pop();
		const int base_level {min_levels[pos.first][pos.second]};

		pos_t dpos {0, 1};
		for (int i {0}; i < 4; i++) {
			dpos = {dpos.second, -dpos.first};
			const pos_t new_pos {pos.first + dpos.first, pos.second + dpos.second};
			if (new_pos.first < 0 || new_pos.first >= rows || new_pos.second < 0 || new_pos.second >= columns) continue;
			const auto level {map[new_pos.first][new_pos.second]};
			if (level == -1) continue;
			const int come_level {std::max(level, base_level)};

			auto& min_level {min_levels[new_pos.first][new_pos.second]};
			if (min_level != -1 && come_level >= min_level) continue;
			min_level = come_level;
			to_visit.push(new_pos);
		}
	}
	std::cout << min_levels[end.first][end.second] << '\n';
	return 0;
}
```

### a138: 最小花費的航空之旅
```cpp=
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <map>

struct State {
	int cost {};
	int city {};
	std::vector<int>::iterator complete {};
	std::vector<int> used {};
	bool is_used (int ticket_id) const {
		return std::find(used.begin(), used.end(), ticket_id) != used.end();
	}
	bool operator< (const State& other) const {
		return cost > other.cost;
	}
};
struct Ticket {
	int id {};
	int cost {};
	std::vector<int> path {};
};

int main() {
	int tickets_num {};
	std::cin >> tickets_num;
	std::map<int, std::vector<Ticket>> tickets {};
	for (int i {1}; i <= tickets_num; i++) {
		Ticket ticket {i};
		std::cin >> ticket.cost;
		int length {}, start {};
		std::cin >> length >> start;
		ticket.path.resize(length - 1);
		for (auto& city : ticket.path) std::cin >> city;
		tickets[start].push_back(ticket);
	}
	int route_length {};
	std::cin >> route_length;
	std::vector<int> route(route_length);
	for (auto& city : route) std::cin >> city;

	std::priority_queue<State> states {};
	states.push({0, route.front(), ++route.begin()});
	while (states.top().complete != route.end()) {
		const State state {states.top()};
		states.pop();
		for (const auto& ticket : tickets[state.city]) {
			if (state.is_used(ticket.id)) continue;
			State new_state {state};
			new_state.used.push_back(ticket.id);
			new_state.cost += ticket.cost;
			for (const auto& city : ticket.path) {
				if (new_state.complete == route.end()) break;
				if (city == *new_state.complete) new_state.complete++;
				new_state.city = city;
				states.push(new_state);
			}
		}
	}
	std::cout << "Cost = " << states.top().cost << ", Tickets used: ";
	bool first {true};
	for (const auto& ticket_id : states.top().used) {
		if (!first) std::cout << ", ";
		std::cout << ticket_id;
		if (first) first = false;
	}
	std::cout << "\n";
	return 0;
}
```

## 17. [題目解析] APCS 程式開發環境、題目解析
### a160: 線段覆蓋長度

```cpp=
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

int main () {
	int lines {};
	std::cin >> lines;
	std::vector<std::pair<int, int>> points {};
	while (lines--) {
		int start {}, end {};
		std::cin >> start >> end;
		points.emplace_back(start, 1);
		points.emplace_back(end, -1);
	}
	std::sort(points.begin(), points.end());
	int lastpos {};
	int length {0};
	int lines_num {0};
	for (const auto& point : points) {
		if (lines_num > 0) length += point.first - lastpos;
		lines_num += point.second;
		lastpos = point.first;
	}
	std::cout << length << '\n';
	return 0;
}
```

### a140: 物品堆疊
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>
#include <utility>

int main () {
	int items_num {};
	std::cin >> items_num;
	std::vector<std::pair<int, int>> items(items_num);
	for (auto& item : items) std::cin >> item.first;
	for (auto& item : items) std::cin >> item.second;
	std::sort(items.begin(), items.end(), [](const auto& a, const auto& b) {
		return a.first * b.second < b.first * a.second;
	});
	long long sumw {0};
	long long sumcost {0};
	for (const auto& item : items) {
		sumcost += sumw * item.second;
		sumw += item.first;
	}
	std::cout << sumcost << '\n';
	return 0;
}
```