# C++ 基礎語法練習題：Unit-11 STL 標準模板庫
講義不是我寫的，原文連結為 [Yui Huang 演算法學習筆記：C++ 基礎語法](https://yuihuang.com/syntax/)
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年11月17日
## [ZeroJudge: e529. 00482 - Permutation Arrays](https://zerojudge.tw/ShowProblem?problemid=e529)
### Python 程式碼
因為輸出時資料格式要按照輸入資料格式，用字串儲存資料比較方便。執行時間最久約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
T = int(input())
for _ in range(T):
_ = input()
idx = list(map(int, input().split()))
xs = list(input().split())
arr = sorted([(i, x) for i, x in zip(idx, xs)])
for a in arr: print(a[1])
print()
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 352 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T; cin.ignore(); // 最後要用 cin.ignore() 跳過 \n
string s; stringstream ss; // 暫存資料用的字串 s，儲存空格分隔資料的 ss
for(int t=0; t<T; t++) { // 執行 T 次
getline(cin, s); // 讀取空行
vector<int> idx; // 資料索引值
vector<string> xs; // 資料字串
getline(cin, s); ss.clear(); ss << s; // 讀行一行資料存入 s，清空 ss，再將 s 存入 ss
while(ss >> s) idx.push_back(stoi(s)); // 由 ss 讀取資料、轉成 int 再放入 idx，直到 ss 沒有資料為止
getline(cin, s); ss.clear(); ss << s; // 讀行一行資料存入 s，清空 ss，再將 s 存入 ss
while(ss >> s) xs.push_back(s); // 由 ss 讀取資料放入 ixs，直到 ss 沒有資料為止
vector<pair<int, string>> arr; // 陣列，資料為 (i, x)
for(int i=0; i<(int)idx.size(); i++) arr.push_back(make_pair(idx[i], xs[i])); // 依序由 idx 及 xs 讀取資料存入 arr
sort(arr.begin(), arr.end()); // 依照 i 由小到大排序
for(auto a : arr) cout << a.second << "\n"; // 依序由 arr 讀取資料 a，印出 a.second
cout << "\n"; // 換行
}
return 0;
}
```
## [ZeroJudge: e155. 10935 - Throwing cards away I](https://zerojudge.tw/ShowProblem?problemid=e155)
### Python 程式碼
寫法1，使用 list 儲存卡片資料，理論上這樣寫並不好，因為 pop(0) 時間複雜度是 $O(n)$，效率不好，不過此題測資不大，這樣寫還是能通過測試。執行時間最久約為 18 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
while True:
n = int(input()) # 卡片數量
if n == 0: break # 如果是 0 中止迴圈
print("Discarded cards: ", end="")
deck = list(range(1, n+1)) # 卡片串列
dis = [] # 丢棄的卡片
while len(deck) > 1: # 如果卡片數量大於 1 繼續執行
dis.append(deck.pop(0)) # 移除最前面的卡片再加到 dis
deck.append(deck.pop(0)) # 移除最前面的卡片再加到最後面
print(*dis, sep=", ") # 印出丢棄的卡片，以 ", " 分隔
print(f"Remaining card: {deck[0]:d}")
```
寫法2，使用 collections.deque 儲存卡片資料，執行速度跟 list 差不多，執行時間最久約為 21 ms，使用記憶體最多約為 3.6 MB，通過測試。
```python=
from collections import deque
while True:
n = int(input()) # 卡片數量
if n == 0: break # 如果是 0 中止迴圈
print("Discarded cards: ", end="")
deck = deque(range(1, n+1)) # 卡片雙向佇列
dis = [] # 丢棄的卡片
while len(deck) > 1: # 如果卡片數量大於 1 繼續執行
dis.append(deck.popleft()) # 移除最前面的卡片再加到 dis
deck.append(deck.popleft()) # 移除最前面的卡片再加到最後面
print(*dis, sep=", ") # 印出丢棄的卡片，以 ", " 分隔
print(f"Remaining card: {deck[0]:d}")
```
### C++ 程式碼
寫法1，使用 vector 儲存卡片資料，執行時間最久約為 2 ms，使用記憶體最多約為 324 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
while(true) {
int n; cin >> n; // 卡片數量
if (n == 0) break; // 如果是 0 中止迴圈
cout << "Discarded cards: ";
if (n == 1) { // 只有一張卡片的特例
cout << "\n" << "Remaining card: 1\n";
} else {
vector<int> deck, dis; // deck 卡片，dis 丢棄的卡片
for(int i=1; i<=n; i++) deck.push_back(i);
while(deck.size() > 1) { // 如果卡片數量大於 1 繼續執行
dis.push_back(deck[0]); // 最前面的卡片加到 dis
deck.erase(deck.begin()); // 移除最前面的卡片
deck.push_back(deck[0]); // 最前面的卡片加到最後面
deck.erase(deck.begin()); // 移除最前面的卡片
}
for(int i=0; i<n-1; i++) { // 印出丢棄的卡片，以 ", " 分隔，最後一張換行
cout << dis[i] << (i == n-2 ? "\n" : ", ");
}
cout << "Remaining card: " << deck[0] << "\n";
}
}
return 0;
}
```
寫法2，由寫法1修改而成，直接印出移除的卡片。執行時間最久約為 2 ms，使用記憶體最多約為 316 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
while(true) {
int n; cin >> n; // 卡片數量
if (n == 0) break; // 如果是 0 中止迴圈
cout << "Discarded cards: ";
if (n == 1) { // 只有一張卡片的特例
cout << "\n" << "Remaining card: 1\n";
} else {
vector<int> deck; // 卡片
for(int i=1; i<=n; i++) deck.push_back(i);
while(deck.size() > 1) { // 如果卡片數量大於 1 繼續執行
cout << deck[0] << (deck.size() == 2 ? "\n" : ", ");; // 印出最前面的卡片，剩2張時換行，否則用 ", " 分隔
deck.erase(deck.begin()); // 移除最前面的卡片
deck.push_back(deck[0]); // 最前面的卡片加到最後面
deck.erase(deck.begin()); // 移除最前面的卡片
}
cout << "Remaining card: " << deck[0] << "\n";
}
}
return 0;
}
```
寫法3，由寫法2修改而成，但改用 deque 儲存卡片資料。執行時間最久約為 2 ms，使用記憶體最多約為 316 kB，通過測試。
```cpp=
#include <iostream>
#include <deque>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
while(true) {
int n; cin >> n; // 卡片數量
if (n == 0) break; // 如果是 0 中止迴圈
cout << "Discarded cards: ";
if (n == 1) { // 只有一張卡片的特例
cout << "\n" << "Remaining card: 1\n";
} else {
deque<int> deck; // 卡片
for(int i=1; i<=n; i++) deck.push_back(i);
while(deck.size() > 1) { // 如果卡片數量大於 1 繼續執行
cout << deck.front() << (deck.size() == 2 ? "\n" : ", ");; // 印出最前面的卡片，剩2張時換行，否則用 ", " 分隔
deck.pop_front(); // 移除最前面的卡片
deck.push_back(deck.front()); // 最前面的卡片加到最後面
deck.pop_front(); // 移除最前面的卡片
}
cout << "Remaining card: " << deck.front() << "\n";
}
}
return 0;
}
```
## [ZeroJudge: e564. 00540 - Team Queue](https://zerojudge.tw/ShowProblem?problemid=e564)
### Python 程式碼
執行時間最久約為 25 ms，使用記憶體最多約為 4 MB，通過測試。
```python=
ca = 0 # 測資編號
while True:
ca += 1 # 測資編號加 1
t = int(input()) # 團隊數量
if t == 0: break # 如果是 0 中止迴圈
print(f"Scenario #{ca:d}") # 印出 Scenario #ca
people = dict() # 每個人所屬的組別，{編號:組別}
que = [] # 二維串列，同團隊成員放在同一個一維串列中
last = [-1]*t # 每一組於 que 之中的索引值，如果不在 que 之中為 -1
for i in range(t): # 讀取 t 行
data = list(input().split()) # 團隊成員編號
for d in data[1:]: # 依序讀取團隊成員編號
people[d] = i # 以成員編號為 key，存入團隊編號 i
# end of for loop
while True: # 讀取指令
line = list(input().split()) # 用空格分隔存入串列
if line[0] == "STOP": break # 如果是 STOP 中止迴圈
elif line[0] == "ENQUEUE": # 如果是 ENQUEUE
p = line[1] # 排入的成員編號 p
idx = last[people[p]] # p 所屬團隊於 que 中的索引值 idx
if idx == -1 or len(que) == 0: # 如果 idx 是 -1 或是 que 沒有資料
que.append([p]) # 將 p 放入一維串列，接在 que 最後面
last[people[p]] = len(que)-1 # p 所屬團隊於 que 中的索引值為 que 長度減 1
else: # 其它狀況
que[idx].append(p) # 於 que[idx] 加入 p
elif line[0] == "DEQUEUE": # 如果是 DEQUEUE
p = que[0].pop(0) # 從 que 開頭的一維串列中移除最前面一項項存入 p
print(p) # 印出 p
if len(que[0]) == 0: # 如果 que 開頭的一維串列是空的
que.pop(0) # 移除 que 開頭的一維串列
for i in range(t): # 更新 last
if i == people[p]: last[i] = -1 # p 所屬團隊於 que 中的索引值為 -1
elif last[i] != -1: last[i] -= 1 # 如果 last[i] 不是 -1 則減 1
# end of while loop
print() # 換行
```
### C++ 程式碼
執行時間最久約為 4 ms，使用記憶體最多約為 696 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int ca = 0; // 測資編號
while(true) {
ca++; // 測資編號加 1
int t; cin >> t; // 團隊數量
if (t == 0) break; // 如果是 0 中止迴圈
cout << "Scenario #" << ca << "\n"; // 印出 Scenario #ca
unordered_map<string, int> people; // 每個人所屬的組別，{編號:組別}
vector<vector<string>> que; // 二維陣列，同團隊成員放在同一個一維陣列中
vector<int> last (t, -1); // 每一組於 que 之中的索引值，如果不在 que 之中為 -1
for(int i=0; i<t; i++) { // 讀取 t 行
int n; cin >> n; // 團隊成員人數
string d; // 團隊成員編號
for(int j=0; j<n; j++) { // 依序讀取團隊成員編號
cin >> d; people[d] = i; // 以成員編號為 key，存入團隊編號 i
}
}
while(true) {
string s; cin >> s; // 讀取指令
if (s == "STOP") break; // 如果是 STOP 中止迴圈
else if (s == "ENQUEUE") { // 如果是 ENQUEUE
string p; cin >> p; // 排入的成員編號 p
int idx = last[people[p]]; // p 所屬團隊於 que 中的索引值 idx
if (idx == -1 || que.empty()) { // 如果 idx 是 -1 或是 que 沒有資料
que.push_back(vector<string> (1, p)); // 將 p 放入一維串列，接在 que 最後面
last[people[p]] = (int)que.size()-1; // p 所屬團隊於 que 中的索引值為 que 長度減 1
} else { // 其它狀況
que[idx].push_back(p); // 於 que[idx] 加入 p
}
} else if (s == "DEQUEUE") { // 如果是 DEQUEUE
string p = que[0][0]; // 從 que 開頭的一維串列中移除最前面一項項存入 p
que[0].erase(que[0].begin());
cout << p << "\n"; // 印出 p
if (que[0].empty()) { // 如果 que 開頭的一維串列是空的
que.erase(que.begin()); // 移除 que 開頭的一維串列
for(int i=0; i<t; i++) { // 更新 last
if (i == people[p]) last[i] = -1; // p 所屬團隊於 que 中的索引值為 -1
else if (last[i] != -1) last[i]--; // 如果 last[i] 不是 -1 則減 1
}
}
}
}
cout << "\n"; // 換行
}
return 0;
}
```
## [ZeroJudge: b838. 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838)
### Python 程式碼
執行時間最久約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
t = int(input()) # 測資組數
for _ in range(t): # 執行 t 次
s = input().strip() # 測資字串，要用 strip() 刪除結尾的 \n
left = 0 # 左括號數量
cnt = 0 # 成對括號數量
flag = True # 是否成對
for c in s: # 依序由 s 讀取字元存入 c
if c == "(": # 如果是 (
left += 1 # 左括號數量加 1
else: # 如果是 ）
if left >= 1: # 如果左括號數量大於等於1，可以成對
cnt += 1 # cnt 加 1
left -= 1 # left 減 1
else: # 否則不能成對
flag = False # 設定為 False
break # 中止迴圈
if flag and left == 0: # 如果 flag 為 True 且左括號都用完
print(cnt) # 印出 cnt
else: print(0) # 否則印出 0
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 336 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; // 測資組數
for(int i=0; i<t; i++) { // 執行 t 次
string s; cin >> s; // 測資字串
int left = 0, cnt = 0; // left 左括號數量，cnt 成對括號數量
bool flag = true; // 是否成對
for(char c : s) { // 依序由 s 讀取字元存入 c
if (c == '(') { // 如果是 (
left++; // 左括號數量加 1
} else { // 如果是 ）
if (left >= 1) { // 如果左括號數量大於等於1，可以成對
cnt++; // cnt 加 1
left--; // left 減 1
} else { // 否則不能成對
flag = false; // 設定為 False
break; // 中止迴圈
}
}
}
cout << (flag && left == 0 ? cnt : 0) << "\n"; // 如果 flag 為 True 且左括號都用完印出 cnt，否則印出 0
}
return 0;
}
```
## [ZeroJudge: c123. 00514 - Rails](https://zerojudge.tw/ShowProblem?problemid=c123)
### Python 程式碼
執行時間最久約為 0.2 s，使用記憶體最多約為 3.7 MB，通過測試。
```python=
while True:
n = int(input()) # 車廂數量
if n == 0: break # 如果是 0 中止迴圈
while True:
line = input() # 讀取一行資料
if line == "0": break # 如果是 "0" 中止迴圈
target = list(map(int, line.split())) # 目標排列方式
A = list(range(1, n+1)) # A 軌道上的列車
B = [] # B 軌道上的列車
S = [] # 車站軌道上的列車
now = 0 # 正在檢測的 target 索引值
while True:
if A and A[0] == target[now]: # 如果 A 有資料而且 A[0] 等於目標
B.append(A.pop(0)) # 移除 A 開頭資料加到 B 最後面
now += 1 # now 加 1
elif S and S[-1] == target[now]: # 如果 S 有資料而且 S[-1] 等於目標
B.append(S.pop()) # 移除 S 最後一項加到 B 最後面
now += 1 # now 加 1
elif A: # 如果 A 有資料
S.append(A.pop(0)) # 移除 A 開頭資料加到 S 最後面
else: break # 其它狀況，中止迴圈
print("Yes" if len(B) == n else "No") # 如果 B 的長度等於 n 印出 Yes
# end of while loop
print() # 換行
```
使用 collections.deque，執行時間最久約為 0.2 s，使用記憶體最多約為 4.2 MB，通過測試。
```python=
from collections import deque
while True:
n = int(input()) # 車廂數量
if n == 0: break # 如果是 0 中止迴圈
while True:
line = input() # 讀取一行資料
if line == "0": break # 如果是 "0" 中止迴圈
target = tuple(map(int, line.split())) # 目標排列方式
A = deque(range(1, n+1)) # A 軌道上的列車
B = deque() # B 軌道上的列車
S = deque() # 車站軌道上的列車
now = 0 # 正在檢測的 target 索引值
while True:
if A and A[0] == target[now]: # 如果 A 有資料而且 A[0] 等於目標
B.append(A.popleft()) # 移除 A 開頭資料加到 B 最後面
now += 1 # now 加 1
elif S and S[-1] == target[now]: # 如果 S 有資料而且 S[-1] 等於目標
B.append(S.pop()) # 移除 S 最後一項加到 B 最後面
now += 1 # now 加 1
elif A: # 如果 A 有資料
S.append(A.popleft()) # 移除 A 開頭資料加到 S 最後面
else: break # 其它狀況，中止迴圈
print("Yes" if len(B) == n else "No") # 如果 B 的長度等於 n 印出 Yes
# end of while loop
print() # 換行
```
### C++ 程式碼
執行時間最久約為 20 ms，使用記憶體最多約為 360 kB，通過測試。
```cpp=
#include <iostream>
#include <deque>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
while(true) {
int n; cin >> n; // 車廂數量
if (n == 0) break; // 如果是 0 中止迴圈
while(true) {
int t; cin >> t; // 讀取一個數字
if (t == 0) break; // 如果是 0 中止迴圈
deque<int> target; target.push_back(t); // 目標排列方式
for(int i=1; i<n; i++) {
cin >> t;
target.push_back(t);
}
deque<int> A, B, S; // A 軌道、B 軌道、車站軌道上的列車
for(int i=1; i<=n; i++) A.push_back(i);
while(true) {
if (!A.empty() && A.front() == target.front()) { // 如果 A 有資料而且 A.front() 等於目標
B.push_back(A.front()); // A 開頭資料加到 B 最後面
A.pop_front(); // 移除 A 開頭資料
target.pop_front(); // 移除 target 開頭資料
} else if (!S.empty() && S.back() == target.front()) { // 如果 S 有資料而且 S.back() 等於目標
B.push_back(S.back()); // S 最後一項加到 B 最後面
S.pop_back(); // 移除 S 最後一項
target.pop_front(); // 移除 target 開頭資料
} else if (!A.empty()) { // 如果 A 有資料
S.push_back(A.front()); // A 開頭資料加到 S 最後面
A.pop_front(); // 移除 A 開頭資料
} else {
break; // 其它狀況，中止迴圈
}
}
cout << ((int)B.size() == n ? "Yes" : "No") << "\n"; // 如果 B 的長度等於 n 印出 Yes
}
cout << "\n"; // 換行
}
return 0;
}
```
## [ZeroJudge: f640. 函數運算式求值](https://zerojudge.tw/ShowProblem?problemid=f640)
### Python 程式碼
使用 list 作為堆疊儲存數值，執行時間最久約為 41 ms，使用記憶體最多約為 3.3 MB，通過測試。另外有[遞迴寫法](https://hackmd.io/@yizhewang/B1w_uVGzke#ZeroJudge-f640-%E5%87%BD%E6%95%B8%E9%81%8B%E7%AE%97%E5%BC%8F%E6%B1%82%E5%80%BC)。
```python=
def f(x):
return 2*x - 3
def g(x, y):
return 2*x + y - 7
def h(x, y, z):
return 3*x - 2*y + z
s = list(input().split())
nums = []
while s:
c = s.pop()
if c == 'f':
x = nums.pop()
nums.append(f(x))
elif c == 'g':
x = nums.pop()
y = nums.pop()
nums.append(g(x, y))
elif c == 'h':
x = nums.pop()
y = nums.pop()
z = nums.pop()
nums.append(h(x, y, z))
else: nums.append(int(c))
print(nums[0])
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 360 kB，通過測試。
```cpp=
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int f(int x) {
return 2*x - 3;
}
int g(int x, int y) {
return 2*x + y - 7;
}
int h(int x, int y, int z) {
return 3*x - 2*y + z;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
string s; stack<string> ss;
while(cin >> s) ss.push(s);
stack<int> nums;
while(!ss.empty()) {
s = ss.top(); ss.pop();
if (s == "f") {
int x = nums.top(); nums.pop();
nums.push(f(x));
} else if (s == "g") {
int x = nums.top(); nums.pop();
int y = nums.top(); nums.pop();
nums.push(g(x, y));
} else if (s == "h") {
int x = nums.top(); nums.pop();
int y = nums.top(); nums.pop();
int z = nums.top(); nums.pop();
nums.push(h(x, y, z));
} else {
nums.push(stoi(s));
}
}
cout << nums.top() << "\n";
return 0;
}
```
## [ZeroJudge: f607. 3. 切割費用](https://zerojudge.tw/ShowProblem?problemid=f607)
### Python 程式碼
執行時間最久約為 1.1 s，使用記憶體最多約為 34.3 MB，通過測試。
```python=
from bisect import bisect_left
n, L = map(int, input().split()) # 切割次數 n，長度 L
cost = 0 # 成本
points = [0, L] # 已切割點位置，先放入兩端
# 讀取 n 行資料，每行組成數組 (x, i)，依照 i 由小到大排序
xi = sorted([tuple(map(int, input().split())) for _ in range(n)], key = lambda x : x[1])
for x, i in xi: # 依序讀取切割點 x、序號 i，但是 i 用不到
idx = bisect_left(points, x) # 用二分搜尋法找 x 於 points 中插入的位置
cost += points[idx] - points[idx-1] # 成本加上 x 兩側端點距離
points.insert(idx, x) # 於 idx 位置插入 x
print(cost) # 印出成本
```
### C++ 程式碼
本題的答案很大，在 $2^{31}$ 到 $2^{60}$ 之間，使用 int 會溢位，要使用 long long。執行時間最久約為 0.1 s，使用記憶體最多約為 6.9 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
LL n, L; cin >> n >> L; // 切割次數 n，長度 L
LL cost = 0; // 成本
vector<LL> points = {0, L}; // 已切割點位置，先放入兩端
/* 讀取 n 行資料，每行組成 pair (i, x)，依照 i 由小到大排序 */
vector<pair<LL, LL>> xi (n, pair<LL, LL> ());
for(LL i=0; i<n; i++) cin >> xi[i].second >> xi[i].first;
sort(xi.begin(), xi.end());
for(auto p : xi) { // 依序讀取切割點
LL x = p.second; // 切割點位置 x
LL idx = lower_bound(points.begin(), points.end(), x) - points.begin(); // 用二分搜尋法找 x 於 points 中插入的位置
cost += points[idx] - points[idx-1]; // 成本加上 x 兩側端點距離
points.insert(idx + points.begin(), x); // 插入 x
}
cout << cost << "\n"; // 印出成本
return 0;
}
```
## [ZeroJudge: d123. 11063 - B2-Sequence](https://zerojudge.tw/ShowProblem?problemid=d123)
因為條件為 $b_i + b_j$ 皆不相等而且 $i \leq j$，要檢測 $i = j$ 的狀況。
### Python 程式碼
使用 set，執行時間最久約為 29 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
import sys
ca = 0 # 第幾個測試的 case
for line in sys.stdin:
ca += 1 # ca 加 1
n = int(line)
arr = list(map(int, input().split()))
found = set() # 已被找到過的任意兩數加總
flag = True # 是否為 B2-Sequence
for i in range(n): # 依序産生 0 ~ n-1
if not flag: break # 如果已經確定不是 B2-Sequence，中止迴圈
for j in range(i, n): # 依序産生 i ~ n-1
isum = arr[i] + arr[j] # 計算任意兩數的加總
if isum in found: # 如果加總已被找到過
flag = False # 不是 B2-Sequence
break # 中止迴圈
else: found.add(isum) # isum 加入 found
print(f"Case #{ca:d}: It is ", end="")
print("a B2-Sequence.\n" if flag else "not a B2-Sequence.\n")
```
使用 collections.defaultdict，執行時間最久約為 33 ms，使用記憶體最多約為 3.7 MB，通過測試。
```python=
import sys
from collections import defaultdict
ca = 0 # 第幾個測試的 case
for line in sys.stdin:
ca += 1 # ca 加 1
n = int(line)
arr = list(map(int, input().split()))
found = defaultdict(bool) # 任意兩數加總是否有被找到過
flag = True # 是否為 B2-Sequence
for i in range(n): # 依序産生 0 ~ n-1
if not flag: break # 如果已經確定不是 B2-Sequence，中止迴圈
for j in range(i, n): # 依序産生 i ~ n-1
isum = arr[i] + arr[j] # 計算任意兩數的加總
if found[isum]: # 如果加總已被找到過
flag = False # 不是 B2-Sequence
break # 中止迴圈
else: found[isum] = True # 設定 isum 狀態為已找到
print(f"Case #{ca:d}: It is ", end="")
print("a B2-Sequence.\n" if flag else "not a B2-Sequence.\n")
```
### C++ 程式碼
使用 set，執行時間最久約為 4 ms，使用記憶體最多約為 324 kB，通過測試。
```cpp=
#include <iostream>
#include <set>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, ca = 0; // # 第幾個測試的 case
while(cin >> n) {
ca++; // ca 加 1
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
set<int> found; // 已被找到過的任意兩數加總
bool flag = true; // 是否為 B2-Sequence
for(int i=0; i<n; i++) { // 依序産生 0 ~ n-1
if (!flag) break; // 如果已經確定不是 B2-Sequence，中止迴圈
for(int j=i; j<n; j++) { // 依序産生 i ~ n-1
int isum = arr[i] + arr[j]; // 計算任意兩數的加總
if (found.count(isum) == 1) { // 如果加總已被找到過
flag = false; // 不是 B2-Sequence
break; // 中止迴圈
} else found.insert(isum); // isum 加入 found
}
}
cout << "Case #" << ca << ": It is ";
cout << (flag ? "a" : "not a") << " B2-Sequence.\n\n";
}
return 0;
}
```
使用 unordered_map，執行時間最久約為 4 ms，使用記憶體最多約為 364 kB，通過測試。
```cpp=
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, ca = 0; // # 第幾個測試的 case
while(cin >> n) {
ca++; // ca 加 1
int arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
unordered_map<int, bool> found; // 已被找到過的任意兩數加總
bool flag = true; // 是否為 B2-Sequence
for(int i=0; i<n; i++) { // 依序産生 0 ~ n-1
if (!flag) break; // 如果已經確定不是 B2-Sequence，中止迴圈
for(int j=i; j<n; j++) { // 依序産生 i ~ n-1
int isum = arr[i] + arr[j]; // 計算任意兩數的加總
if (found[isum]) { // 如果加總已被找到過
flag = false; // 不是 B2-Sequence
break; // 中止迴圈
} else found[isum] = true; // found[isum] 設定為 true
}
}
cout << "Case #" << ca << ": It is ";
cout << (flag ? "a" : "not a") << " B2-Sequence.\n\n";
}
return 0;
}
```
## [ZeroJudge: d442. 10591 - Happy Number](https://zerojudge.tw/ShowProblem?problemid=d442)
### Python 程式碼
執行時間最久約為 0.8 s，使用記憶體最多約為 3.3 MB，通過測試。
```python=
def ssum(n): # 計算各位數字平方和
tot = 0
while n > 0:
d = n%10
tot += d*d
n //= 10
return tot
N = int(input()) # 測資數量
for i in range(1, N+1): # 執行 N 次
n = int(input()) # 要測試的數字
print(f"Case #{i:d}: {n:d} is ", end="") # 印出開頭
flag = False # 是否為 happy number
tested = set() # 已測試的數字
while True:
if n == 1: # 如果 n 等於 1
flag = True # 是 happy number
break # 中止迴圈
elif n in tested: # 如果 n 在 tested 之中，不是 happy number
break # 中止迴圈
else: # 其它狀況
tested.add(n) # 將 n 加入 tested
n = ssum(n) # 計算各位數字平方和，更新 n
print("a Happy number." if flag else "an Unhappy number.")
```
### C++ 程式碼
執行時間最久約為 59 ms，使用記憶體最多約為 348 kB，通過測試。
```cpp=
#include <iostream>
#include <set>
using namespace std;
int ssum(int n) { // 計算各位數字平方和
int tot = 0;
while(n > 0) {
int d = n%10;
tot += d*d;
n /= 10;
}
return tot;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N; cin >> N; // 測資數量
for(int i=1; i<=N; i++) { // 執行 N 次
int n; cin >> n; // 要測試的數字
cout << "Case #" << i << ": " << n << " is "; // 印出開頭
bool flag = false; // 是否為 happy number
set<int> tested; // 已測試的數字
while(true) {
if (n == 1) { // 如果 n 等於 1
flag = true; // 是 happy number
break; // 中止迴圈
} else if (tested.count(n) == 1) { // 如果 n 在 tested 之中，不是 happy number
break; // 中止迴圈
} else { // 其它狀況
tested.insert(n); // 將 n 加入 tested
n = ssum(n); // 計算各位數字平方和，更新 n
}
}
cout << (flag ? "a Happy number.\n" : "an Unhappy number.\n");
}
return 0;
}
```
## [ZeroJudge: a135. 12250 - Language Detection](https://zerojudge.tw/ShowProblem?problemid=a135)
### Python 程式碼
執行時間最久約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
lan = {"HELLO": "ENGLISH",
"HOLA": "SPANISH",
"HALLO": "GERMAN",
"BONJOUR": "FRENCH",
"CIAO": "ITALIAN",
"ZDRAVSTVUJTE": "RUSSIAN"}
ca = 0
while True:
s = input()
if s == "#": break
ca += 1
print(f"Case {ca:d}: ", end="")
if s not in lan:
print("UNKNOWN")
else:
print(lan[s])
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 356 kB，通過測試。
```cpp=
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
unordered_map<string, string> lan = {{"HELLO", "ENGLISH"},
{"HOLA", "SPANISH"},
{"HALLO", "GERMAN"},
{"BONJOUR", "FRENCH"},
{"CIAO", "ITALIAN"},
{"ZDRAVSTVUJTE", "RUSSIAN"}};
int ca = 0;
while(true) {
string s; cin >> s;
if (s == "#") break;
ca++;
cout << "Case " << ca << ": ";
if (lan[s] == "") cout << "UNKNOWN\n";
else cout << lan[s] << "\n";
}
return 0;
}
```
## [ZeroJudge: e641. 10260 - Soundex](https://zerojudge.tw/ShowProblem?problemid=e641)
**注意：相同發音編號的字母如果相連只輸出一次編號，即使字母之間有空格也視為相連。**
### Python 程式碼
因為 Python 可以用 in 判斷字元是否存在於字串之中，以下的寫法反而比用 dict 還要好懂。執行時間最久約為 17 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
import sys
for line in sys.stdin:
pre = 0
for c in line:
if c in "BFPV" and pre != 1:
print("1", end="")
pre = 1
elif c in "CGJKQSXZ" and pre != 2:
print("2", end="")
pre = 2
elif c in "DT" and pre != 3:
print("3", end="")
pre = 3
elif c in "L" and pre != 4:
print("4", end="")
pre = 4
elif c in "MN" and pre != 5:
print("5", end="")
pre = 5
elif c in "R" and pre != 6:
print("6", end="")
pre = 6
elif c in "AEIOUHWY":
pre = 0
print()
```
由於 Python 的 dict 如果讀到不存在的 key 會回傳錯誤，必須使用 collections.defaultdict 才行。以下的程式碼第4到8行先建立每個字母對應的編碼，為了輸出時比較方便，編碼也採用字元格式；第9行再轉換成 defaultdict，預設格式為 str，如果輸入不存在的 key 值會回傳空字串。
```python=
import sys
from collections import defaultdict
table = {'A': '0', 'B': '1', 'C': '2', 'D': '3', 'E': '0', 'F': '1',
'G': '2', 'H': '0', 'I': '0', 'J': '2', 'K': '2', 'L': '4',
'M': '5', 'N': '5', 'O': '0', 'P': '1', 'Q': '2', 'R': '6',
'S': '2', 'T': '3', 'U': '0', 'V': '1', 'W': '0', 'X': '2',
'Y': '0', 'Z': '2'}
table = defaultdict(str, table)
for line in sys.stdin:
pre = '0'
for c in line:
if table[c] != pre:
if table[c] != '0': # 編碼不是 '0' 才需要輸出
print(table[c], end="")
pre = table[c]
print()
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 328 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
map<char, char> table = {{'A', '0'}, {'B', '1'}, {'C', '2'}, {'D', '3'}, {'E', '0'}, {'F', '1'},
{'G', '2'}, {'H', '0'}, {'I', '0'}, {'J', '2'}, {'K', '2'}, {'L', '4'},
{'M', '5'}, {'N', '5'}, {'O', '0'}, {'P', '1'}, {'Q', '2'}, {'R', '6'},
{'S', '2'}, {'T', '3'}, {'U', '0'}, {'V', '1'}, {'W', '0'}, {'X', '2'},
{'Y', '0'}, {'Z', '2'}};
string line;
char pre = '0';
while(cin >> line) {
for(char c : line) {
if (table[c] != pre) {
if (table[c] != '0') cout << table[c];
pre = table[c];
}
}
cout << "\n";
}
return 0;
}
```
## [ZeroJudge: d267. 11577 - Letter Frequency](https://zerojudge.tw/ShowProblem?problemid=d267)
不使用 map 的寫法請參考[這個頁面](https://hackmd.io/@yizhewang/BJEvlKxf1x#ZeroJudge-d267-11577---Letter-Frequency)。
### Python 程式碼
以下是比較具有 Python 風格的寫法，執行時間最久約為 24 ms，使用記憶體最多約為 3.6 MB，通過測試。
```python=
import sys
from collections import Counter
n = int(input())
for _ in range(n):
s = (input()).lower() # 全部轉成小寫字母
cnt = Counter(s) # 計數器
imax = 0
ans = ""
for k, v in cnt.items(): # 讀取數量最多的字母
if k.isalpha():
if v > imax: ans = k; imax = v
elif v == imax: ans += k
print("".join(sorted(ans))) # 排序後接成字串再輸出
```
### C++ 程式碼
執行時間最久約為 3 ms，使用記憶體最多約為 352 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <map>
#include <cctype> // isalpha, tolower
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; cin.ignore();
for(int i=0; i<n; i++) {
string s; getline(cin, s); // 讀取一行字串
map<char, int> cnt; // 計數器
for(char c : s) { // 依序由 s 讀取字元 c，如果 c 是字母，轉成小寫，數量加 1
if (isalpha(c)) cnt[tolower(c)]++;
}
int imax = 0; // 數量最大值
string ans = ""; // 儲存答案用的空字串
for(auto cn : cnt) { // 讀取數量最多的字母
if (cn.second > imax) {
ans = cn.first;
imax = cn.second;
} else if (cn.second == imax) {
ans += cn.first;
}
}
sort(ans.begin(), ans.end()); // 排序後再輸出
cout << ans << "\n";
}
return 0;
}
```
## [ZeroJudge: d221. 10954 - Add All](https://zerojudge.tw/ShowProblem?problemid=d221)
我另外寫的筆記〈[Python 及 C++ 優先佇列 (priority queue)](https://hackmd.io/@yizhewang/S1EBLEAvT)〉。
### Python 程式碼
Python 的 priority queue 名稱為 heapq，需要引入函式庫 heapq，而且是最小值放上面的最小堆積樹。執行時間最久約為 0.2 s，使用記憶體最多約為 4.6 MB，通過測試。
```python=
import heapq as hq
while True:
n = int(input())
if n == 0: break
pq = list(map(int, input().split())) # 讀取一行資料轉成 list
hq.heapify(pq) # 轉成 priority queue，最小值放在上面
cost = 0 # 成本
while len(pq) > 1: # 當 pq 長度大於 1 繼續執行
a = hq.heappop(pq) # 取出最小值 a
b = hq.heappop(pq) # 取出最小值 c
c = a+b # 相加的成本 c
cost += c # 更新 cost
hq.heappush(pq, c) # 將 c 放入 pq
print(cost) # 印出 cost
```
### C++ 程式碼
要使用 long long 才不會溢位，執行時間最久約為 23 ms，使用記憶體最多約為 464 kB，通過測試。
```cpp=
#include <iostream>
#include <queue>
#include <vector>
#include <string>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
while(true) {
int n; cin >> n;
if (n == 0) break;
priority_queue<LL, vector<LL>, greater<LL>> pq; // priority queue，最小值放在上面
for(int i=0; i<n; i++) {
LL m; cin >> m; pq.push(m);
}
LL cost = 0; // 成本
while(pq.size() > 1) { // 當 pq 長度大於 1 繼續執行
LL a = pq.top(); pq.pop(); // 取出最小值 a
LL b = pq.top(); pq.pop(); // 取出最小值 c
LL c = a+b; // 相加的成本 c
cost += c; // 更新 cost
pq.push(c); // 將 c 放入 pq
}
cout << cost << "\n"; // 印出 cost
}
return 0;
}
```
## [ZeroJudge: c875. 107北二2.裝置藝術](https://zerojudge.tw/ShowProblem?problemid=c875)
### Python 程式碼
第20筆測資，程式碼第5行遇到 MemoryError。
```python=
import heapq as hq
A, B, C = map(int, input().split()) # 飲料塔數量 A，一個飲料罐的高度 B，最大高度差 C
C = (C - C%B) // B # 改成對應的飲料罐數量，例如 B = 2, C = 5，修改成 C = 2
hs = list(map(int, input().split())) # 每個飲料塔原來的高度
hs = [h//B for h in hs] # 修改成原來的飲料罐數量
pq = [(h, i) for i, h in enumerate(hs)] # 組成 tuple
hq.heapify(pq) # 轉成 priority queue，依照高度由小到大排序
ans = 0 # 要移除的罐子數量
while pq:
h, i = hq.heappop(pq) # 取出目前最低的飲料塔高度 h、位置 i
if i != A-1 and hs[i+1] - h > C: # 跟右邊比較高度差，如果右邊較高則降低高度
num = (hs[i+1] - h - C) # 要移除的罐子數量
ans += num
hs[i+1] -= num
hq.heappush(pq, (hs[i+1], i+1))
if i != 0 and hs[i-1] - h > C: # 跟左邊比較高度差，如果左邊較高則降低高度
num = (hs[i-1] - h - C)
ans += num
hs[i-1] -= num
hq.heappush(pq, (hs[i-1], i-1))
# end of while loop
print(ans)
```
如果改成用自訂函式分割字串，第20筆測資變成在程式碼第16行遇到 MemoryError。
```python=
import heapq as hq
def stringStream(s, sep):
start = 0
for end in range(len(s)):
if s[end] in sep:
yield s[start:end]
start = end + 1
if start < len(s):
yield s[start:]
A, B, C = map(int, input().split()) # 飲料塔數量 A，一個飲料罐的高度 B，最大高度差 C
C = (C - C%B) // B # 改成對應的飲料罐數量，例如 B = 2, C = 5，修改成 C = 2
line = input() # 讀取一行資料
hs = [int(h)//B for h in stringStream(line, " \n")] # 每個飲料塔原來的飲料罐數量
pq = [(h, i) for i, h in enumerate(hs)] # 組成 tuple
hq.heapify(pq) # 轉成 priority queue，依照高度由小到大排序
ans = 0 # 要移除的罐子數量
while pq:
h, i = hq.heappop(pq) # 取出目前最低的飲料塔高度 h、位置 i
if i != A-1 and hs[i+1] - h > C: # 跟右邊比較高度差，如果右邊較高則降低高度
num = hs[i+1] - h - C # 要移除的罐子數量
ans += num
hs[i+1] -= num
hq.heappush(pq, (hs[i+1], i+1))
if i != 0 and hs[i-1] - h > C: # 跟左邊比較高度差，如果左邊較高則降低高度
num = hs[i-1] - h - C
ans += num
hs[i-1] -= num
hq.heappush(pq, (hs[i-1], i-1))
# end of while loop
print(ans)
```
### C++ 程式碼
要使用 long long 才不會溢位，執行時間最久約為 0.3 s，使用記憶體最多約為 19.6 MB，通過測試。
```cpp=
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
LL A, B, C; cin >> A >> B >> C; // 飲料塔數量 A，一個飲料罐的高度 B，最大高度差 C
C = (C - C%B) / B; // 改成對應的飲料罐數量，例如 B = 2, C = 5，修改成 C = 2
vector<LL> hs (A); // 每個飲料塔原來的飲料罐數量
priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<pair<LL, LL>>> pq; // (h, i) 由小到大排序
for(LL i=0; i<A; i++) {
LL h; cin >> h;
hs[i] = h/B;
pq.push(make_pair(h/B, i));
}
LL ans = 0; // 要移除的罐子數量
while(!pq.empty()) {
LL h = pq.top().first, i = pq.top().second; pq.pop(); // 取出目前最低的飲料塔高度 h、位置 i
if (i != A-1 && hs[i+1] - h > C) { // 跟右邊比較高度差，如果右邊較高則降低高度
LL num = hs[i+1] - h - C; // 要移除的罐子數量
ans += num;
hs[i+1] -= num;
pq.push(make_pair(hs[i+1], i+1));
}
if (i != 0 && hs[i-1] - h > C) { // 跟左邊比較高度差，如果左邊較高則降低高度
LL num = hs[i-1] - h - C;
ans += num;
hs[i-1] -= num;
pq.push(make_pair(hs[i-1], i-1));
}
}
cout << ans << "\n";
return 0;
}
```
## [ZeroJudge: b231. TOI2009 第三題：書](https://zerojudge.tw/ShowProblem?problemid=b231)
因為只有一台印刷機，所有書藉印刷的時間都要算進答案中，決定花費總時間的關鍵為裝釘時間。如果將每本書印刷、裝釘時間組成 tuple，依照裝釘時間由大到小排序。計算答案 ans 時先預設為 0，由大到小依序取出每本書的資料，答案會是 **ans 及 (前一次印刷花費的總時間 + 這次印刷花費的時間 + 這本書裝釘需要的時間) 之中較大者** 。
### Python 程式碼
寫法1，使用 list 及 sorted，執行時間最久約為 23 ms，使用記憶體最多約為 3.4 MB，通過測試。
```python=
import sys
for line in sys.stdin:
if line.isspace(): continue # 用來跳過空行
n = int(line)
pb = sorted([tuple(map(int, input().split())) for _ in range(n)],
key=lambda x : x[1], reverse=True)
t, ans = 0, 0
for p, b in pb:
t += p
ans = max(ans, t+b)
print(ans, end="\n\n")
```
寫法2，使用 heapq，執行時間最久約為 24 ms，使用記憶體最多約為 3.4 MB，通過測試。
```python=
import sys
import heapq as hq
for line in sys.stdin:
if line.isspace(): continue
n = int(line)
pb = []
for _ in range(n):
p, b = map(int, input().split())
pb.append((-b, -p)) # 要反過來並加負號
hq.heapify(pb) # priority queue 依照裝釘時間由大到小排序
t, ans = 0, 0
while pb:
b, p = hq.heappop(pb)
b = -b; p = -p
t += p
ans = max(ans, t+b)
print(ans, end="\n\n")
```
### C++ 程式碼
寫法1，使用 vector 及 sort，執行時間最久約為 2 ms，使用記憶體最多約為 356 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
while(cin >> n) {
vector<pair<int, int>> bp;
int p, b;
for(int i=0; i<n; i++) {
cin >> p >> b;
bp.push_back(make_pair(b, p)); // 反過來在排序時比較方便
}
sort(bp.begin(), bp.end(), greater<pair<int, int>>());
int t = 0, ans = 0;
for(auto d : bp) {
t += d.second;
ans = max(ans, t + d.first);
}
cout << ans << "\n\n";
}
return 0;
}
```
如果在上方程式碼的第15行沒有把裝釘時間 b 放在前面，而是把印刷時間 p 放在前面，第17行排序時就要用 lambda function 寫比較式，會比較麻煩。執行時間最久約為 2 ms，使用記憶體最多約為 356 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
while(cin >> n) {
vector<pair<int, int>> pb;
int p, b;
for(int i=0; i<n; i++) {
cin >> p >> b;
pb.push_back(make_pair(p, b));
}
sort(pb.begin(), pb.end(), [](pair<int, int> a, pair<int, int> b) {
return a.second > b.second; });
int t = 0, ans = 0;
for(auto d : pb) {
t += d.first;
ans = max(ans, t + d.second);
}
cout << ans << "\n\n";
}
return 0;
}
```
寫法2，使用 priority queue，執行時間最久約為 2 ms，使用記憶體最多約為 348 kB，通過測試。
```cpp=
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
while(cin >> n) {
priority_queue<pair<int, int>> bp;
int p, b;
for(int i=0; i<n; i++) {
cin >> p >> b;
bp.push(make_pair(b, p)); // 一定要反過來才行
}
int t = 0, ans = 0;
while(!bp.empty()) {
int bt = bp.top().first, pt = bp.top().second;
bp.pop();
t += pt;
ans = max(ans, t + bt);
}
cout << ans << "\n\n";
}
return 0;
}
```
## [ZeroJudge: d980. 11479 - Is this the easiest problem?](https://zerojudge.tw/ShowProblem?problemid=d980)
**注意，測資中的邊長可能是 0 或負數，這樣也不能構成三角形。** 因為邊長已經由小到大排序，檢查最小的邊即可。
### Python 程式碼
執行時間最久約為 17 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
n = int(input())
for i in range(1, n+1):
print(f"Case {i:d}: ", end="")
d = sorted(list(map(int, input().split())))
if d[0] <= 0 or d[0] + d[1] <= d[2] or d[2] - d[1] >= d[0]:
print("Invalid")
elif d[0] == d[1] == d[2]:
print("Equilateral")
elif d[0] == d[1] or d[1] == d[2]:
print("Isosceles")
else:
print("Scalene")
```
### C++ 程式碼
要使用 long long，否則在計算邊長相加時會溢位。執行時間最久約為 2 ms，使用記憶體最多約為 324 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for(int i=1; i<=n; i++) {
cout << "Case " << i << ": ";
vector<LL> d (3);
for(int j=0; j<3; j++) cin >> d[j];
sort(d.begin(), d.end());
if (d[0] <= 0 || d[0] + d[1] <= d[2] || d[2] - d[1] >= d[0]) {
cout << "Invalid\n";
} else if (d[0] == d[1] && d[1] == d[2]) {
cout << "Equilateral\n";
} else if (d[0] == d[1] || d[1] == d[2]) {
cout << "Isosceles\n";
} else {
cout << "Scalene\n";
}
}
return 0;
}
```
## [ZeroJudge: e446. 排列生成](https://zerojudge.tw/ShowProblem?problemid=e446)
### Python 程式碼
遞迴解，第8筆測資開始超時。
```python=
def perm(depth, maxDepth, nums, tested):
if depth == maxDepth:
print(*nums)
return
for i in range(1, N+1):
if i in tested: continue
tested.add(i)
nums.append(i)
perm(depth+1, maxDepth, nums, tested)
tested.remove(i)
nums.pop()
N = int(input())
perm(0, N, [], set())
```
### C++ 程式碼
遞迴解，執行時間最久約為 9.3 s，使用記憶體最多約為 344 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int N;
void perm(int depth, int maxDepth, vector<int>& nums, set<int>& tested) {
if (depth == maxDepth) {
for(int i=0; i<(int)nums.size(); i++)
cout << nums[i] << " \n"[i == (int)nums.size()-1];
return;
}
for(int i=1; i<=N; i++) {
if (tested.count(i) == 1) continue;
tested.insert(i);
nums.push_back(i);
perm(depth+1, maxDepth, nums, tested);
tested.erase(i);
nums.pop_back();
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N;
vector<int> nums;
set<int> tested;
perm(0, N, nums, tested);
return 0;
}
```
使用 algorithm next_permutation 作弊，執行時間最久約為 7.8 s，使用記憶體最多約為 352 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N; cin >> N;
int nums[N];
for(int i=0; i<N; i++) {
nums[i] = i+1;
cout << i+1 << " \n"[i == N-1];
}
while(next_permutation(nums, nums+N)) {
for(int i=0; i<N; i++)
cout << nums[i] << " \n"[i == N-1];
}
return 0;
}
```
---
###### tags:`演算法`、`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet