# 高二上資訊科課程成果
> 作者：沈宗叡（暴力又被TLE）
## 課程說明
這份課程成果包含了兩門課程：資訊課和選修課運算思維，我則按照時間排序。
資訊課主要著重於基本語法的使用與程式實作，而運算思維則是推理，但我都寫程式窮舉。
若是閱讀紙本，可以到 [文件末尾](#本文的連結) 掃 QRcode 閱讀網頁版。
## 實作成果
### 實作第一支程式 2024/9/3
輸入名字，輸出打招呼訊息。
```python=
print(f"{input('你叫啥? ')}, 膩蠔~~")
```
使用 Python 的 f-string 可以輕鬆完成，至於為何要在單引號和雙引號之間切換？因為 Google Colab 使用的是 Python 3.11，在此版本以前，如果 f-string 使用同一種引號互相嵌套，編譯器只會按照單層的邏輯處理，導致 SyntaxError，而在 Python 3.12 以後則改變了其作用的邏輯，可以使用同一種引號就好了。
### BMI計算 2024/9/10
假設月球重力只有地球的六分之一，嫦娥在飛昇之前，在地球量體重為 $60$ 公斤重。身高為 $150$ 公分，請問登陸到月球時會變成多少公斤？$\text{BMI}$ 又是多少？
如果只要算嫦娥：
```python=
w, h = 60, 150 # 體重(kgw), 身高(cm)
w /= 6 # 1/6倍重力
h /= 100 # cm -> m
bmi = w / h / h # BMI 計算公式
print(f"體重: {w}kgw", f"bmi: {bmi:.2f}") # f-string 輸出
```
Python 內的除法預設是真除法，要寫整數除法的話可以寫 `a // b`，會向下取整，而 `int(a / b)` 則是會向 $0$ 取整。
如果要處理使用者輸入：
因為題目沒講使用者會輸入甚麼奇怪的東西，所以我盡量把基本的 edge case 都考慮進去。
```python=
from bisect import bisect_left
from itertools import filterfalse
from operator import itemgetter
from re import match
isvalid = lambda s: bool(match(r"^\d+(\.\d+)?$", s.strip()))
rank = ((0, "過輕"), (18.5, "正常"), (24, "過重"),
(27, "輕度肥胖"), (30, "中度肥胖"), (35, "重度肥胖"))
def main() -> None:
print("input height(m/cm) and weight(kg)")
valid = False
while not valid:
try:
input_vals = []
while len(input_vals) < 2:
tmp = input()
if not tmp: break
tmp = tmp.split()
if (invalid := next(filterfalse(isvalid, tmp), None)) is not None:
raise TypeError(f"expected numbers, got '{invalid}'")
input_vals.extend(tmp)
if len(input_vals) == 2:
h, w = map(eval, input_vals)
elif not tmp:
print("program ends")
break
else:
raise ValueError(f"expected 2 numbers, got {len(input_vals)}")
valid = True
except Exception as e:
print(e)
else:
assert valid
# cm -> m
if h > 3: h /= 100
bmi = w / h / h
print(f"BMI: {bmi:.2f},
{rank[bisect_left(rank, bmi, key=itemgetter(0)) - 1][1]}")
if __name__ == "__main__":
main()
```
輸入的部分使用 `re.match` 判斷是否使用者輸入的內容中是否有需要的資訊，若有則擷取，否則針對無效內容報錯。
為了使輸入更加簡易且泛用，可以於同一行輸入兩個數字，或換行輸入兩個數字，數字可以接受整數或浮點數。
如果輸入的身高大於 $3$ 則會將單位視為公分並自動轉換。
根據 $\text{BMI}$ 結果給予評價，使用 `bisect` 模組在具單調性的評價內二分搜，雖然常數比較大但是比較帥。
### 提高計算力(爆搜)，學會反思(剪枝?)與歸納(窮舉) 2024/9/10
有甲、乙、丙、丁、戊 $5$ 個人參加考試，都考了相同的五門課 (C#、Pyhon、Java、VB、LISP)，老師評完考卷後結果如下（成績為等第制，從低到高分別為 $1$、$2$、$3$、$4$、$5$ 分）:
一、$5$ 個人的總分各不相同，而且在同一門考試中，也沒有相同分數的人。但無論是誰，都有一門課程成績是 $5$ 個人中最好的。
二、按得分總名次排列，甲為第一名，其餘依次為乙、丙、戊、丁。
三、甲總分為 $18$ 分，乙比甲少 $2$ 分。
四、甲 C# 最好，乙 Python 最好，但乙的 Java 和 VB 均為第三名。
五、丙的 Java 為第一，LISP 為第二，C# 為第三。
六、丁的 LISP 為第一，VB 為第二。
請推論這 $5$ 個人的各科成績各是多少？總分又各是多少？
首先，發現只有 $5$ 個人，$5$ 個科目的排名窮舉起來也才 $24883200000$，好像有點大，但將題目的資訊填入表格後，就只剩下 $31104$ 種狀況需要驗證了，簡單地將條件列出來並轉換成程式碼即可。
`itertools` 特別適合窮舉，他可以惰性地產生排列組合情況，十分省記憶體。
```python=
from itertools import permutations, product, islice
from operator import itemgetter
"""
將確定的填上 剩下的窮舉
# P J V L
A 5 - - - -
B - 5 3 3 -
C 3 - 5 - 4
D - - - 4 5
E - - - - -
上面的表格行列交換 方便對行窮舉
(每行必為1~5排列)
A B C D E
0 5 - 3 - -
1 - 5 - - -
2 - 3 5 - -
3 - 3 - 4 -
4 - - 4 5 -
ANS:
# P J V L sm rk
A 5 3 4 5 1 18 1
B 2 5 3 3 3 16 2
C 3 2 5 1 4 15 3
D 1 1 1 4 5 12 5
E 4 4 2 2 2 14 4
"""
# 窮舉所有空格的情況 共 3!*3!*3!*4!*3! = 31104種
# 實際上在第13562項找到答案
it = product(
permutations((1, 2, 4)),
permutations(range(1, 5)),
permutations((1, 2, 4)),
permutations((1, 2, 5)),
permutations(range(1, 4))
)
for l in it:
# 求每人成績之和 並判斷符合
# a == 18 and b == 13 and a > b > c > e > d
a = 5 + sum(map(itemgetter(0), islice(l, 1, None)))
if a != 18: continue
b = 11 + l[0][0] + l[4][1]
if a <= b or b != 16: continue
c = 12 + l[1][1] + l[3][1]
if b <= c: continue
d = 9 + sum(map(itemgetter(-2), islice(l, 3)))
if c <= d: continue
e = sum(map(itemgetter(-1), l))
if not c > e > d: continue
break
else:
assert False # 沒搜出答案 顯式地報個錯
print(*l, sep="\n")
print(a, b, c, d, e)
```
### 等差等比 2024/9/18
多筆測資，輸入一個數列的前四項，判斷是等差還是等比後輸出第五項。
```python=
def main():
from sys import stdin
for e in stdin:
a, b, c, d = map(eval, e.split())
if a + c == b * 2:
print(d * 2 - c)
else:
d = d * d / c
if d.is_integer():
d = int(d) # 如果結果剛好是整數就轉換成int
print(d)
main()
```
如果輸入的數列並不固定是四項...？
如果只有一個數字，那就是兩種皆可，輸出 `consistent`。
否則判斷輸入的整個數列是否完全符合其中一種，若兩種都符合就輸出兩種結果（如果兩個結果相等就只輸出一次），否則輸出符合的，或者都不符合輸出 `inconsistent`。
使用 `itertools.pairwise` 可以輕鬆地枚舉任兩個相鄰數，方便判斷其關係。而 `match-case` 則是 Python 3.10 加入的新語法。
```python=
def main():
from sys import stdin
from itertools import pairwise
stdin.readline() # 測資數量不需要 丟掉
for e in map(str.strip, stdin): # 去掉結尾空白後輸入
if not e: break # 該行輸入為空白即視為結束程式
l = pairwise(map(int, e.split())) # 兩兩一組做成iterator
# 取第一組初始化 公差,公比
if (first := next(l, None)) is None:
print("consistent")
continue
a, b = first
d, r = b - a, (b / a if a != 0 else 0)
# 初始化等差等比合法紀錄bit 0位記錄等差 1位紀錄等比
bit = 1 if r == 0 else 3
for a, b in l:
if bit & 1: # 判斷是否仍等差
if b - a != d:
bit &= ~1
if bit & 2: # 判斷是否仍等比
if a == 0 or b / a != r:
bit &= ~2
if bit == 0: # 都不合法就跳出
break
match bit:
case 0: # 等差等比皆不合法
print("inconsistent")
case 1: # 只有等差合法
print(e, b + d)
case 2: # 只有等比合法
b *= r
print(e, int(b) if b.is_integer() else b)
case 3: # 等差等比皆合法
x, y = b + d, b * r
if y.is_integer():
y = int(y)
if x != y: # 可能有兩個解
print(e, f"({x} or {y})")
else: # 只有一個解
print(e, x)
case _: # 禮貌性報個錯
raise RuntimeError()
main()
```
### 計算闖關 2024/9/13
如圖所示，由出發點開始，經過每一關時，從加減乘除中選一個符號（用過不重複），對相鄰兩個數字進行運算，使到達目的地時，答案恰巧為1。請問要怎樣才能過關。
題目沒講是要先乘除後加減，還是單純由左而右運算，因此我兩種都寫了。
邏輯上就是一般的 DFS 窮舉。
使用 `operator` 模組取得加減乘除運算的函式，可以使程式碼更簡潔。只是注意 `truediv` 是預設的真除法，而 `div` 是向下取整的除法。
```python=
from operator import add, sub, mul, truediv
os = (add, sub, mul, truediv)
ns = ("+", "-", "*", "/")
def dfs(i, v, res):
if i == 6:
if v == 1:
s = "(((1{}2){}3){}4){}5==1".format(*res)
assert eval(s), s
print("1{}2{}3{}4{}5=1".format(*res))
return
for (o, n) in zip(os, ns):
res.append(n)
dfs(i + 1, o(v, i), res)
res.pop()
print("由左至右運算")
dfs(2, 1, [])
def dfs(i, res):
if i == 6:
s = "1{}2{}3{}4{}5==1".format(*res)
if eval(s) == 1:
print("1{}2{}3{}4{}5=1".format(*res))
return
for (o, n) in zip(os, ns):
res.append(n)
dfs(i + 1, res)
res.pop()
print("\n先乘除後加減")
dfs(2, [])
```
### 重新排列 2024/9/14
從 $1$ 到 $5$ 的 $25$ 個數字規規矩矩地排列。現將他們打亂，重新排列，使得縱，橫各行數目的和都相等，且同一行的數字不得出現兩次。
進階：思考一下如何讓縱、橫、斜對角看數字皆為不同、總和皆同。
簡易版數獨，使用 backtracking 的邏輯，並用 bit-mask 加速運算。
種類有 $161280$ 實在太多了，因此將答案寫入 .txt 內保存。
```python=
def main():
file = open(r"re_sort.txt", "w")
w = file.write
n = 5
cnt = 0
row, col = [0] * n, [0] * n
l = [[0] * n for _ in range(n)]
def dfs(i, j):
nonlocal cnt
if j == n:
j = 0
i += 1
if i == n:
cnt += 1
w("\n".join(" ".join(map(str, r)) for r in l) + "\n\n")
return
rb, cb = row[i], col[j]
for k in range(1, n + 1):
if rb >> k & 1 == 0 and cb >> k & 1 == 0:
l[i][j] = k
mask = 1 << k
row[i] ^= mask
col[j] ^= mask
dfs(i, j + 1)
row[i] ^= mask
col[j] ^= mask
dfs(0, 0)
w(str(cnt))
file.close()
main()
```
進階題的部分，就是再多兩個 bit 紀錄兩條對角線填了哪些數字，並加上相應的條件判斷，總共 $960$ 種。
```python=
def main():
file = open(r"re_sort.txt", "w")
w = file.write
n = 5
cnt = 0
row, col = [0] * n, [0] * n
d = ad = 0
l = [[0] * n for _ in range(n)]
def dfs(i, j):
nonlocal cnt, d, ad
if j == n:
j = 0
i += 1
if i == n:
cnt += 1
w("\n".join(" ".join(map(str, r)) for r in l) + "\n\n")
return
rb, cb = row[i], col[j]
for k in range(1, n + 1):
if (rb >> k & 1 == 0
and cb >> k & 1 == 0
and (i != j or d >> k & 1 == 0)
and (i + j != n - 1 or ad >> k & 1 == 0)):
l[i][j] = k
mask = 1 << k
row[i] ^= mask
col[j] ^= mask
if i == j: d ^= mask
if i + j == n - 1: ad ^= mask
dfs(i, j + 1)
row[i] ^= mask
col[j] ^= mask
if i == j: d ^= mask
if i + j == n - 1: ad ^= mask
dfs(0, 0)
w(str(cnt))
file.close()
main()
```
### 相鄰的數 2024/9/14
$0 \sim 5$ 這 $6$ 個自然數填入下面的圓圈中，使得每個數的所有相鄰數之和如右圖所示（相鄰為有實線直接相連）
這種圖論題最麻煩的就是建圖，只能手生，超級地獄。後面還會有更噁的，非常值得期待。
使用 `itertools.permutations` 輕鬆窮舉六個點於圖上的排列情況。
```python=
from itertools import permutations
# 鄰接圖
ix = ((1, 2), (0, 2, 3), (0, 1, 4), (1, 4), (2, 3, 5), (4, ))
# 每個節點的相鄰和
sm = (4, 12, 7, 8, 3, 4)
for l in permutations(range(6)):
getitem = l.__getitem__
if all(
sum(map(getitem, ix[i])) == sm[v]
for i, v in enumerate(l)
):
print(*l)
```
答案：
### 消防設備 2024/9/21
基地有 $9$ 座倉庫，為了防火，需在這些倉庫中放兩套消防設備。只要一座倉庫放了消防設備，凡是與它有路連著的倉庫都可以就近使用。這兩套消防設備應該放在哪裡，才能使 $9$ 座倉庫都用得上？
這題是圖論裡經典的 minimum dominating set 問題，屬於 NP-complete 問題，沒有多項式時間複雜度的解法。
DFS 窮舉，並使用 bit-mask 紀錄那些點已經被支配。
答案：選 $(1, 6)$
$Time: O(2^n), Space: O(n)$
```python=
# minimum dominating set [NP-complete]
def main():
from sys import stdin
e = stdin.readline
"""
建圖 輸入所有邊 (省略)
"""
# 考慮第i個點 支配了那些點(二進位) 取了幾個點 取了那些點(list[int])
def dfs(i, bit, cur, res):
nonlocal best
if bit == every: # 全部支配
if cur < best:
ans.clear()
best = cur
ans.append(tuple(res))
return
if i == n or cur == best: return # 到底或不可能更新答案 剪枝
i += 1
dfs(i, bit, cur, res) # 不取此點
res.append(i)
dfs(i, bit | G[i - 1], cur + 1, res) # 取此點
res.pop()
n, m = map(int, e().split())
every = (1 << n) - 1
G = [1 << i for i in range(n)]
for _ in range(m):
a, b = map(int, e().split())
a, b = a - 1, b - 1
G[a] |= 1 << b
G[b] |= 1 << a
best, ans = float("INF"), []
dfs(0, 0, 0, [])
print(best, *ans)
main()
```
若圖是樹的話則有 $O(n)$ 的 DP 解。
$Time: O(n), Space: O(n)$
```python=
"""
DP轉移式:
00: 此點不選 可能未被管轄(父節點必選) (所有子節點都已經管好各自)
01: 此點不選 確定已被管轄(其中一個子節點有選)
10: 選取此點
p[00] = sum(min(i[01], i[10]) for i in child)
p[01] = sum(min(i[01], i[10]) for i in child) +
min(i[10] - min(i[01], i[10]) for i in child)
p[10] = sum(min(i[00], i[01], i[10]) for i in child) + 1
"""
def main():
from sys import stdin
e = stdin.readline
inf = float("INF")
n = int(e())
child = [[] for i in range(n)]
for i in range(n - 1):
u, v = map(int, e().split())
u, v = u - 1, v - 1
child[u].append(v)
child[v].append(u)
pa = [False] * n
pa[0] = True
top_down = [0]
for i in top_down:
for j in child[i]:
if pa[j] is False:
pa[j] = i
top_down.append(j)
del child
dp = [(0, inf, 1)] * n
it = reversed(top_down) # bottom-up
for _ in range(n - 1):
i = next(it)
p = pa[i]
d0, d1, d2 = dp[i]
d1 += d0
m = d1 if d1 < d2 else d2
p0, p1, p2 = dp[p]
dp[p] = (p0 + m,
min(p1, d2 - m),
p2 + min(d0, d1, d2))
d0, d1, d2 = dp[0]
d1 += d0
print(d1 if d1 < d2 else d2)
main()
```
### 紅酒問題 2024/9/21
最剛開始的時候，$9$ 升杯是滿的，$5$ 升、$4$ 升、$2$ 升杯都是空的；這些杯都沒有標示計量刻度。遊戲的目的是將紅酒平均分成 $3$ 份（這將使最小的 $2$ 升杯留空）。若要能將 $9$ 升紅酒平均分成 $3$ 等份，最少倒紅酒次數是多少？
可以轉化為最短路問題，使用 BFS 求解。
比較麻煩的部分是狀態的編碼及轉移，因為數字小所以我用了好寫但燒雞的寫法。
為了求出操作順序，還需要儲存所有前置狀態，最後再反向回溯。
答案：$6$
操作過程：
```
9 5 4 2
-------
9 0 0 0
5 0 4 0
3 0 4 2
3 2 4 0
3 5 1 0
3 3 1 2
3 3 3 0
```
```python=
def main():
from sys import stdin
e = stdin.readline
lim = (9, 5, 4, 2)
des = (3, 3, 3, 0)
# state: tuple[int, int, int, int]
# dp: dict[state, tuple[int, state]
# {此狀態: 最小步數, 前置狀態}
dp = {(9, 0, 0, 0):(0, None)}
cur = [(9, 0, 0, 0)]
step = 1
end = False
while cur:
nxt = []
for l in cur:
for i in range(4):
if l[i] == 0: continue
for j in range(4):
if i == j: continue
if l[j] == lim[j]: continue
mv = min(l[i], lim[j] - l[j])
nl = list(l)
nl[i] -= mv
nl[j] += mv
nl = tuple(nl)
nv = (step, l)
if nl == des:
dp[nl] = nv
end = True
break
if (val := dp.get(nl)) is None:
dp[nl] = nv
nxt.append(nl)
if end: break
if end: break
if end: break
cur = nxt
step += 1
print(step)
path = []
cur = des
while cur is not None:
path.append(cur)
cur = dp[cur][1]
for val in reversed(path):
print(*val)
main()
```
### 義賊廖添丁 2024/9/21
廖添丁從貪官甲家偷了錢以後，挨家挨戶送，最後到乙家。路線不走第二遍，而且一家不漏。他是按照什麼樣的路線走過去的呢？
這題我會！窮舉所有邊的走訪順序就好了！
答案：
總共6解
甲abcdefdkjihgf乙
甲abcdefghijkdf乙
甲abcdfedkjihgf乙
甲abcdfghijkdef乙
甲abcdkjihgfdef乙
甲abcdkjihgfedf乙
$Time: O(e!), Space: O(e)$
```python=
def main():
from sys import stdin
e = stdin.readline
"""
建圖 輸入所有邊和起終點 (省略)
"""
def dfs(i, nb, eb, res):
if i == t and nb == nodes: # 於t結尾且經過所有點
ans.append(tuple(res))
return
for e, j in G[i]:
if (eb >> e) & 1 == 0:
res.append(j)
dfs(j, nb | (1 << j), eb | (1 << e), res)
res.pop()
return None
n, m, s, t = map(int, e().split())
nodes = (1 << n) - 1
edges = (1 << m) - 1
G = [[] for i in range(n)]
for i in range(m):
a, b = map(int, e().split())
G[a].append((i, b))
G[b].append((i, a))
ans = []
dfs(s, 1 << s, 0, [s])
get = "甲abcdefghijk乙".__getitem__
for a in ans: print("".join(map(get, a)))
main()
```
加上一些 cache 優化，使用兩個 bit 表示已經造訪過哪些邊和點。
$Time: O(e!), Space: O(e + e \times 2^{e+v})$
```python=
def main():
from sys import stdin
from functools import cache
e = stdin.readline
"""
建圖 輸入所有邊和起終點 (省略)
"""
@cache
def dfs(i, nb, eb):
if i == t and nb == nodes: # 於t結尾且經過所有點
return ((i, ), )
res = []
for e, j in G[i]:
if (eb >> e) & 1 == 0:
if (tails := dfs(j, nb | (1 << j), eb | (1 << e))) is None:
continue
for tail in tails:
res.append((i, ) + tail)
return res if res else None
n, m, s, t = map(int, e().split())
nodes = (1 << n) - 1
edges = (1 << m) - 1
G = [[] for i in range(n)]
for i in range(m):
a, b = map(int, e().split())
G[a].append((i, b))
G[b].append((i, a))
ans = dfs(s, 1 << s, 0)
get = "甲abcdefghijk乙".__getitem__
for a in ans: print("".join(map(get, a)))
main()
```
這題會不會加上一些圖論黑魔法後能有甚麼很快的解？
問問 ChatGPT，如果在起點和終點之間連上一條虛擬的邊，問題就會變成「找經過所有點恰一次的環」，使用 cycle basis 的圖論黑魔法可以將時間複雜度壓低。
首先，找到任意一顆生成樹，剩下 $E-(V-1)$ 條邊，這每一條邊各自加入到生成樹上後，都會形成一個獨一無二的環，這些環叫做「基本環基底」，總共有 $E-(V-1)$ 個。
任取數個基本環基底（$O(2^{E-(V-1)})$），對他們做 xor 操作（也就是保留出現次數為奇數的邊，次數為偶數的邊刪除），就會得到一個圖，這個圖若是連通，就將題目轉換成了「找經過所有點與所有邊恰一次的路徑」，只要窮舉所有邊的排列順序即可，而此時邊數通常已遠小於原先邊數，故速度更快。
以上這些東西我研究了一整個晚上，感謝 APCS 模擬測驗群兩位大佬 Wiwi Ho 和 WayneYam 的幫助。
$Time: O(e \times 2^{e-v+2} + (\text{e of valid_edge})!), Space: O(v + e + v \times 2^{(\text{e of valid_edge})})$
```python=
def main():
from sys import stdin
from functools import cache
e = stdin.readline
"""
建圖 輸入所有邊和起終點 (省略)
"""
n, m, s, t = map(int, e().split())
edges = [tuple(map(int, e().split())) for _ in range(m)]
# 起終點增加一條假邊 把問題變成找環 (表示複雜度時e中不包含此邊)
edges.append((s, t))
an = (1 << n) - 1
ae = (1 << m + 1) - 1
G = [[] for i in range(n)]
for i, (a, b) in enumerate(edges):
G[a].append((i, b))
G[b].append((i, a))
# bfs造生成樹 O(e)
nb, eb = 1 << s, 0
cur = [s]
while cur:
nxt = []
for i in cur:
for e, j in G[i]:
if (nb >> j) & 1: continue
eb |= 1 << e
nb |= 1 << j
nxt.append(j)
cur = nxt
re = ae ^ eb # 沒包含在生成樹的邊 共(e-v+2)個
# 找cycle_basis 不知道實際多少 絕對小於 O((e-v+2)*e)
cycle_basis = []
while re:
eeb = re & -re
re ^= eeb
a, b = edges[eeb.bit_length() - 1]
nb = 1 << a
cur = [(a, eeb)]
while True:
nxt = []
for i, eeb in cur:
for e, j in G[i]:
if (nb >> j) & 1: continue
if (eb >> e) & 1 == 0: continue
nb |= 1 << j
if j == b:
cycle_basis.append(eeb | (1 << e))
break
nxt.append((j, eeb | (1 << e)))
else: continue
break
else:
cur = nxt
continue
break
print("cycle_basis")
for i in cycle_basis:
print(bin(i).lstrip("0b").zfill(m + 1))
print()
# 窮舉所有cycle_basis的xor組合 挑出使圖連通的 O(2^(e-v+2) * e)
valid_edges = []
eb = 0
mask = [0] * (m - n + 2)
while True:
# 窮舉2^(e-v+2)種組合
for i, (v, cb) in enumerate(zip(mask, cycle_basis)):
eb ^= cb
mask[i] ^= 1
if v == 0: break
else: break
if eb.bit_count() < n: continue
# bfs看圖是否連通 O(e)
nb = 1
cur = [0]
while cur:
nxt = []
for i in cur:
for e, j in G[i]:
if (nb >> j) & 1: continue
if (eb >> e) & 1 == 0: continue
nb |= 1 << j
nxt.append(j)
cur = nxt
if nb == an and eb >> m: valid_edges.append(eb & ~(1 << m))
print("valid_edges")
for i in valid_edges:
print(bin(i).lstrip("0b").zfill(m + 1))
print()
@cache
def dfs(i, eb):
if i == t and eb == valid_edge: # 於t結尾 用到所有valid_edge
return ((i, ), )
res = []
for e, j in G[i]:
if (eb >> e) & 1 == 0:
if (tails := dfs(j, eb | (1 << e))) is None: continue
for tail in tails:
res.append((i, ) + tail)
return res if res else None
# 從valid_edges找路徑
ans = []
for valid_edge in valid_edges:
ans.extend(dfs(s, 0))
dfs.cache_clear()
get = "甲abcdefghijk乙".__getitem__
print("ans")
for a in ans: print("".join(map(get, a)))
main()
```
### 彩券 I 2024/9/22
某彩券公司推出一種新型的刮刮樂，規則如下：每張刮刮樂上面有兩個 $0 \sim 9$ 的數字。如果第一個數字是奇數，則可以得到 $100$ 元。如果第二個數字是 $2$、$5$、$8$，則可以得到 $200$ 元。如果第一個和第二個的數字相同，則可以得到 $50$ 元。以上三種得獎方式，你只能選擇獎金最高的一種來領取。
現在給你一張刮刮樂上的兩個數字，請問你可以得到多少獎金。
輕鬆題，依照題意實作即可。
```python=
def main():
stop = False
while not stop:
a, b = map(int, input().split())
print(
max(
(100 if a & 1 else 0),
(200 if b in (2, 5, 8) else 0),
(50 if a == b else 0)
) if (stop := (0 <= a <= 9 and 0 <= b <= 9)) else "錯誤"
)
main()
```
### 彩券 II 2024/9/22
同上一題，只是將「取最高獎金」改成「獎金總和」。
```python=
def main():
stop = False
while not stop:
a, b = map(int, input().split())
print(
(
(100 if a & 1 else 0)
+ (200 if b in (2, 5, 8) else 0)
+ (50 if a == b else 0)
) if (stop := (0 <= a <= 9 and 0 <= b <= 9)) else "錯誤"
)
main()
```
### 最大值 2024/9/25
給你一連串的正整數，請你找出最大的數出現在第幾個位置，以及它是多少。
- 輸入說明：一開始有一個正整數 $N$，代表後面會出現幾個數字，接下來即是這 $N$ 個整數。
- 輸出說明：請輸出最大值出現在第幾個位置（位置從 $1$ 開始算），以及它是多少，中間請空一格。
`enumerate` 的第二個 parameter 為 `start` 值，即從哪個數字開始數，這題可以用來轉換成 1-based。
```python=
def main():
from operator import itemgetter
input() # 輸入N 用不到
print(*max(enumerate(map(int, input().split()), 1), key=itemgetter(1)))
main()
```
### 小學生死神的使者 2024/10/15
蚵北終於長大了，成為一家偵探社的老闆，不再是小學生死神，今天在立花公園發生了一起案件，想要從代號為 A、B、C、D、E、F 六個偵查員中挑選若干人去破案，挑選的規則必須符合下列各點：
1.A、B 兩人中至少去一人。
2.A、D 不能一起去。
3.A、E、F 三人中要派兩人去。
4.B、C 兩人不是都去就是都不去。
5.C、D 兩人中去一人。
6.若 D 不去，則 E 也不去。
那麼，你知道有哪幾位被挑選？
只有 $6$ 人，數字很小直接窮舉。
用 bit 來窮舉，簡潔又好看。
答案：ABCF
```python=
for bit in range(1 << 6): # 窮舉六人的所有組合
if bit & 0b11 == 0: continue # A、B兩人中至少去一人。
if bit & 0b1001 == 0b1001: continue # A、D不能一起去。
if (bit & 0b110001).bit_count() != 2: continue # A、E、F三人中要派兩人去。
if (bit >> 1) & 1 != (bit >> 2) & 1: continue # B、C兩人不是都去就是都不去。
if (bit & 0b1100).bit_count() != 1: continue # C、D兩人中去一人。
if bit & 0b11000 == 0b10000: continue # 若D不去，則E也不去。
print("".join(c for i, c in enumerate("ABCDEF") if (bit >> i) & 1)) # 答案
```
### 購物的優惠 2024/10/16
萬聖節要到了，阿明想要購買一些南瓜，已知一顆30元，他找到幾間店家，分別有以下的優惠：
購買 $3$ 個南瓜，可以免費獲得 $1$ 個南瓜。
購買 $2$ 個南瓜，第二個南瓜享受 $40\%$ 的折扣。
購買 $5$ 個南瓜，可以免費獲得 $2$ 個南瓜。
老師原本的題目沒講清楚，因此衍伸出了兩種題意：
1. 只能選擇一種方案
2. 可以任意搭配方案
首先可以將每個方案轉換成「每顆西瓜多少錢」的形式方便比較：
買 $1$ 顆，花 $30$ 元，得到 $1$ 個
買 $3$ 顆，花 $90$ 元，得到 $4$ 個
買 $2$ 顆，花 $48$ 元，得到 $2$ 個
買 $5$ 顆，花 $150$ 元，得到 $7$ 個
第一種題意，就是用除法計算所有方案的花費即可。
`divmod` 可以只做一次除法回傳商數及餘數。
$Time: O(1), Space: O(1)$
```python=
def main():
n = int(input())
# get, cost
plan = ((4, 90), (2, 48), (7, 150))
plan_name = ("一個一個買", "買三送一", "第二個40%-off", "買五送二")
ans = (30 * n, 0) # 先worst case 一個一個買
for i, (get, cost) in enumerate(plan, start=1): # 嘗試各種方案
q, r = divmod(n, get)
ans = min(ans, (cost * q + r * 30, i))
print(ans[0], plan_name[ans[1]])
main()
```
第二種題意，就用得上 DP，對於每一個 $N$ 選最佳轉移。
為了得知購買方式，需要記錄前置狀態。
$Time: O(n), Space: O(n)$
```python=
def main():
n = int(input())
# buy, get, cost
plan = ((1, 1, 30), (3, 4, 90), (2, 2, 48), (5, 7, 150))
# bottom-up
dp = [(0,)] * (n + 1)
for i in range(1, n + 1):
dp[i] = min((dp[i - get][0] + cost, buy, get)
for buy, get, cost in plan if i >= get)
# 倒推購買順序
res = []
i = n
while i:
res.append(dp[i][1])
i -= dp[i][2]
print(dp[n][0])
print(*reversed(res)) # reversed(倒推) = 順序
main()
```
而題目給定的方案其實可以貪心。
$Time: O(1), Space: O(1)$
```python=
def main():
n = int(input())
# buy, get, cost
# 從最優惠的方案開始選
plan = ((5, 7, 150), (3, 4, 90), (2, 2, 48), (1, 1, 30))
res = 0
for buy, get, cost in plan:
q, n = divmod(n, get)
res += cost * q
return res
main()
```
### 放風風雲 2024/10/23
南光中學座落於新營糖廠旁邊，是間作風開放的學校，每到中午時間便會放風讓學生到外面用餐。當然還是會有人逾時不歸，身為管理者的阿茗，每天總是要為哪些人沒有回來而傷透腦筋。
現在想請你寫一個程式，幫助阿茗找出哪些人沒有回來。
輸入說明：
一開始有兩個正整數 $N$、$M$，$N$ 代表收容人的人數（編號從 $1$ 到 $N$），$M$ 代表回來的人數，接下來有 $M$ 個正整數，分別代表這 $M$ 位已經回來的收容人編號（不用考慮編號超出範圍或其他錯誤）。
輸出說明：
請將沒有回來的收容人編號從小到大輸出，兩個編號中間請空一格。
**學校實際上從來沒有也永遠不會放風。**
陣列應用基本題。
$Time: O(n), Space: O(n)$
```python=
it = map(int, input().split())
n, m = next(it), next(it)
l = [True] * n
for i in it:
l[i - 1] = False
print(*(i for i, v in enumerate(l, start=1) if v))
```
### 數字探險趣 2024/10/30
在一個遙遠的數字王國裡，住著一位名叫小數的勇敢探險者。小數熱愛探索這個王國的每一個角落，尤其是那些充滿神秘數字的地方。這些數字有的高大威猛，有的卻小巧玲瓏，讓小數感到無比好奇。
某天，小數在森林裡發現了一個古老的寶箱，寶箱裡裝滿了各式各樣的正整數。這些數字像是被施了魔法，散發著耀眼的光芒。小數決定要找出這些數字中，哪些比他心中最崇拜的數字 $X$ 更小，哪些又比 $X$ 更大。
於是，小數開始了他的計數冒險。他希望能夠清楚地知道，有多少數字比 $X$ 小，還有多少數字比 $X$ 大。這樣，他就能更好地理解這些數字的特性，並在未來的探險中運用這些知識。
任務描述
小數需要你的幫助！請你幫他完成以下任務：
首先，告訴小數這個寶箱裡有多少個數字。
接著，輸入這些數字的清單。
然後，告訴小數一個特定的數字 $X$，他想知道比這個數字小和大的數字各有多少個。
輸入格式：
第一行包含一個正整數 $N$，表示數字的個數。
第二行包含 $N$ 個正整數，這些數字用空格分隔。
第三行包含一個正整數 $X$，表示要比較的數字。
輸出格式：
第一行輸出比 $X$ 小的數字的個數。
第二行輸出比 $X$ 大的數字的個數。
簡單地計數即可，也不用用到陣列。
$Time: O(n), Space: O(1)$
```python=
input()
it = map(int, input().split())
x = int(input())
lower = greater = 0
for i in it:
if i < x: lower += 1
elif i > x: greater += 1
print(lower, greater, sep="\n")
```
### 森林猴子的打字冒險 2024/10/30
在一個深山的森林裡，住著一隻名叫小猴的猴子。小猴是一隻非常好奇的猴子，總是喜歡探索新事物。有一天，小猴發現了一台古老的打字機，這台打字機散發著神秘的光芒，讓小猴忍不住想要試試看。
小猴開始在打字機上隨意地按鍵，隨著每一次敲擊，鍵盤上發出清脆的聲音。小猴的目標是打出王國裡最美麗的詩句，這首詩句是由著名的詩人創作的，名叫《山道猴子》。然而，這首詩句的字數眾多，小猴的打字速度卻不快，且經常按錯鍵。
小猴聽說過一個古老的傳說：如果他能夠打出這首詩句，哪怕是去掉某幾個字元，這也算是達成任務。於是，小猴決定不放棄，繼續努力地在打字機上敲擊著。
任務描述
小猴需要你的幫助！請你幫他檢查一下他打出的文字是否符合以下條件：
輸入格式：
第一行包含一個字符串，表示指定的文字。
第二行包含一個字符串，表示猴子輸入的文字。
輸出格式：
如果猴子打出的文字去掉某幾個字元後能夠形成指定的文字，則輸出 "符合條件"。
否則，輸出 "不符合條件"。
子序列檢查，使用 iterator 比較好寫。
$Time: O(n), Space: O(n)$
```python=
p, s = iter(input()), input()
j = next(p)
for i in s:
if i == j:
j = next(p, None)
if j is None:
print("符合條件")
break
else:
print("不符合條件")
```
### 求平方根 2024/11/5
二分逼近法求平方根。
Python 的浮點數精度大約是小數點下 $17$ 位，那個 `w` 是 debug 用的。
二分搜直到區間大小為 $0$，即達到浮點數精度極限。
有趣的是二分搜出來的答案不一定跟數學算出來的一樣，所以說只要扯到浮點數，一切都是玄學。
```python=
n = int(input())
# bisect
w = len(str(n)) + 18
le, ri = 0, n
while le != (mid := (le + ri) / 2) != ri:
if mid ** 2 <= n:
le = mid
else:
ri = mid
print(le)
# math
print(n ** 0.5)
```
### 計算最大子陣列和及其元素 2024/11/6
卡丹算法，只是要記錄區間端點位置。
$Time: O(n), Space: O(n)$
```python=
input() # n 不重要 丟掉
l = tuple(map(int, input().split()))
ans = -float("INF")
ai = aj = -1
i = dp = 0
for j, v in enumerate(l):
if dp < 0:
dp = 0
ai = j
dp += v
if ans < dp:
ans = dp
aj = j + 1
print(ans)
print(*l[ai:aj])
```
### 影像遮罩 2024/11/9
實做一個函式，對輸入的兩個矩陣做捲積。
```python=
Image = list[list[int]]
def image_matting(mask: Image, img: Image) -> Image:
m, n = len(mask), len(img)
half = m >> 1
res = [[0] * n for _ in range(n)]
for i in range(half, n - half):
for j in range(half, n - half):
res[i][j] = sum(img[i + di][j + dj] * mask_val
for di, mask_row in enumerate(mask, -1)
for dj, mask_val in enumerate(mask_row, -1))
return res
```
### 防駭銀行 2024/11/9
某銀行為不讓駭客輕易地進入他們的系統，固定將英文字母的 5 個母音 `a`, `e`, `i`, `o`, `u` 通通取代成 `abc`，數字通通取代成 `$`，
例如：
`wehave99dollarsinthebank`會變成
`wabchabcvabc$$dabcllabcrsabcnthabcbabcnk`。
依照題意實作即可。用 `str.join` 達到線性時間的字串組合。
```python=
s = input()
ans = []
for i in s:
if i.isdigit():
ans.append("$")
elif i in "aeiou":
ans.append("abc")
else:
ans.append(i)
print("".join(ans))
```
### 請問今年貴庚 2024/11/12
老張和小王在外面休息，突然看到 $3$ 位鄰居。
老張就對問小王說：猜猜他們幾歲?【老張知道他們的歲數】
老張就給小王提示：他們三個人的歲數乘起來會等於 $2450$，且他們三個的歲數加起來是小王的 $2$ 倍，他們的歲數和不超過 $80$。
小王說：應該還差一個條件。
老張說：喔喔...我忘了，我都比他們三個大。
請問 $3$ 個鄰居和小王以及老張的歲數為何？
題目資訊不足，只能求出部分答案。
列出 $2450$ 的因數，然後 DFS 窮舉即可。
答案：
鄰居: $[2, 25, 49]$, 小王: $38$, 老張: ≥ $49$
鄰居: $[2, 35, 35]$, 小王: $36$, 老張: ≥ $35$
鄰居: $[5, 10, 49]$, 小王: $32$, 老張: ≥ $49$
鄰居: $[5, 14, 35]$, 小王: $27$, 老張: ≥ $35$
鄰居: $[7, 7, 50]$, 小王: $32$, 老張: ≥ $50$
鄰居: $[7, 10, 35]$, 小王: $26$, 老張: ≥ $35$
鄰居: $[7, 14, 25]$, 小王: $23$, 老張: ≥ $25$
共 $7$ 解
```python=
x = 2450
n = 3
f = [1, 2, 5, 7, 10, 14, 25, 35, 49, 50, 70, 98, 175, 245, 350, 490, 1225, 2450]
cur = []
ans = []
def dfs(c, x):
if c == n:
cur.append(x)
if sum(cur) <= 80 and sum(cur) & 1 == 0:
res = [*sorted(cur), sum(cur) >> 1, max(cur)]
if res not in ans:
ans.append(res)
cur.pop()
return
for i in f:
q, r = divmod(x, i)
if r: continue
cur.append(i)
dfs(c + 1, q)
cur.pop()
dfs(1, x)
for *a, b, c in ans:
print(f"鄰居: {a}, 小王: {b}, 老張: ≥ {c}")
print(f"共 {len(ans)} 解")
```
### 甲乙丙丁愛運動 2024/11/12
甲乙丙丁四人喜歡的運動不同，而且每人都只做固定一種運動；
已知，籃球場只休星期一，
羽球場只休星期二，桌球場只休星期四，
游泳池則休星期二四六；
甲：『今天我要去運動，不然明天沒得去。』
乙：『今明兩天我都會去運動。』
丙：『今天我要去運動，前天我也有去。』
丁：『從這個星期一到今天，我每天都有去運動。』
請問，四人說話的這天是星期幾？四人各自做什麼運動呢？
列出四種運動的開館日，同時窮舉「四人與運動的關係」和「今天星期幾」即可。
答案：
星期 3
甲: swimming
乙: basketball
丙: badminton
丁: table tennis
```python=
from itertools import permutations
# 7654321
accessible = [
0b1111110, # basketball
0b1111101, # badminton
0b1110111, # table tennis
0b1010101 # swimming
]
name = [
"basketball",
"badminton",
"table tennis",
"swimming"
]
for a, b, c, d in permutations(enumerate(accessible)):
for i in range(2, 6): # 3 ~ 6 in 1-based
if (a[1] >> i) & 0b11 != 0b01: continue
if (b[1] >> i) & 0b11 != 0b11: continue
if (c[1] >> i - 2) & 0b101 != 0b101: continue
i += 1 # to 1-based
if (d[1] & ((1 << i) - 1)).bit_count() != i: continue
print(
f"星期 {i}\n"
f"甲: {name[a[0]]}\n"
f"乙: {name[b[0]]}\n"
f"丙: {name[c[0]]}\n"
f"丁: {name[d[0]]}\n"
)
```
### 求對數 2024/11/13
也是二分搜。
Python 的 pow 內建快速冪，十分快。
```python=
b, x = map(int, input().split())
# bisect
w = len(str(x)) + 18
le, ri = 0, x
while le != (mid := (le + ri) / 2) != ri:
if pow(b, mid) <= x:
le = mid
else:
ri = mid
print(le)
# math
from math import log
print(log(x, b))
```
### 座位配當表 2024/11/19
有 ABCD 四個種族的人，要坐在下面這八張椅子上：
其中：
- 每個種族至少有一個人，C 族只有一個人
- AB 兩族不相鄰而坐，CD 兩族也不相鄰而坐（上下左右都算相鄰）
- 每個 A 族的人都坐在兩個 D 族的人中間
- 至少有一位 D 族的人坐在兩個 B 族的人中間
- 至少有兩位 D 族人相鄰而坐
請問，各個座位上坐著的是哪一族人呢？
推理比較簡單，窮舉難寫的一題，主要是圖醜，邊界條件不好判。因此在建圖的時候加上一層 sentinel，減少很多麻煩。
C 族只有一個人，窮舉他的位置，與剩餘位置下 ABD 的所有組合，再對每個格子判斷是否符合。
答案：
有唯一解
```
. B . .
D D A D
. B C .
. . B .
```
```python=
from itertools import product, repeat
G = (
(-1, 0, -1, -1, -1),
(1, 2, 3, 4, -1),
(-1, 5, 6, -1, -1),
(-1, -1, 7, -1, -1),
(-1, -1, -1, -1)
)
d = ((0, -1), (-1, 0), (0, 1), (1, 0))
for state in product(*repeat(range(3), 7)):
if 0 not in state or 1 not in state or sum(1 for i in state if i == 2) < 2:
continue
for c in range(8):
valid = 0
get = lambda x: -1 if x == -1 else 3 if x == c else state[x - (x > c)]
for i in range(4):
for j in range(4):
idx = G[i][j]
if idx == -1: continue
cur = get(idx)
if cur & 1:
bad = cur ^ 1
if any(get(G[i + di][j + dj]) == bad for di, dj in d):
break
elif cur == 0:
if not (get(G[i][j - 1]) == get(G[i][j + 1]) == 2 or
get(G[i - 1][j]) == get(G[i + 1][j]) == 2):
break
elif cur == 2:
if (get(G[i][j - 1]) == get(G[i][j + 1]) == 1 or
get(G[i - 1][j]) == get(G[i + 1][j]) == 1):
valid |= 0b1
if get(G[i][j + 1]) == 2 or get(G[i + 1][j]) == 2:
valid |= 0b10
else:
assert False
else:
continue
break
else:
if valid != 0b11: continue
for i in range(4):
for j in range(4):
cur = get(G[i][j])
print("." if cur == -1 else "ABDC"[cur], end=" ")
print()
print()
```
### 區間質數數量 2024/12/3
有兩種解法，適合不同的情況：
使用 Miller–Rabin prime test 判斷區間內的每個數字是不是質數。
可以先特判特定因數，加速程式。
$Time: O(r \log_2 x)$，$r$ 為區間長度，$\log_2 x$ 代表區間內每個數 $x$ 的計算為 $\log_2 x$
```python=
def main():
s, t = map(int, input().split())
cnt = 0
for n in range(s, t + 1):
# 先特判 節省時間
if n <= 1: continue
elif n & 1 == 0:
if n == 2: cnt += 1
elif n <= 7: cnt += 1
elif n % 3 == 0 or n % 5 == 0 or n % 7 == 0: continue
else:
# Miller–Rabin prime test
d = n - 1
r = (d & -d).bit_length() - 1
d >>= r
for a in (
(2, 7, 61) if n <= 1 << 32 else # 篩 2³² 以內
(2, 325, 9375, 28178, 450775, 9780504, 1795265022) # 可到 2⁶⁴
):
if a % n == 0:
continue
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break # 可能是質數 繼續下一輪驗證
else:
# 不是質數
break
else:
# 通過所有驗證 是質數
cnt += 1
print(cnt)
main()
```
使用質數篩，從 $1$ 跑到右端點。適合大區間多筆詢問。
雖然歐拉線性篩的理論複雜度更好，但做了很多除法常數偏大，通常反而較慢。
$Time: O(n \log (\log n))$
```python=
def main():
from itertools import islice
from math import isqrt
n = 10 ** 6 + 1
sieve = [True] * n
sieve[0] = sieve[1] = False
prefix = 0 # 同時對篩做前綴和
for i, v in enumerate(islice(sieve, isqrt(n))):
if v is True:
prefix += 1
for j in range(i * i, n, i):
sieve[j] = False
sieve[i] = prefix
sieve.append(0) # sentinel for prefix
q = int(input()) # 幾個詢問?
for _ in range(q):
# 查詢 [s, t] 區間質數個數
s, t = map(int, input().split())
print(sieve[t] - sieve[s - 1])
main()
```
### 弔詭邏輯問題 2024/12/3
```
Q1：第一個答案為A的問題是哪一個問題？
(A)1 (B)2 (C)3 (D)4
Q2：唯一連續兩個有相同答案的問題是：
(A)5，6 (B)6，7 (C)7，8 (D)8，9
Q3：本問題的答案和哪一個問題的答案相同？
(A)4 (B)9 (C)8 (D)2
Q4：答案是A的問題的個數是：
(A)5 (B)4 (C)3 (D)2
Q5：本問題的答案和哪一個問題的答案相同？
(A)1 (B)2 (C)3 (D)4
Q6：答案A的個數和答案什麼的個數相同？
(A)皆與BCD不同 (B)B (C)C (D)D
Q7：按字母順序，本問題的答案和下一個問題的答案相差幾個字母？（A和B相差1）
(A)3 (B)2 (C)1 (D)0
Q8：答案為母音字母的問題有幾個？（母音字母：A）
(A)0 (B)1 (C)2 (D)3
Q9：答案為子音字母的個數為：（子音字母：BCD）
(A)合數 (B)質數 (C)小於 5 (D)平方數
Q10：本問題的答案是：
(A)A (B)B (C)C (D)D
```
為了可讀性，沒做甚麼優化，單純的窮舉。
答案有兩個：
```
1 2 3 4 5 6 7 8 9 10
A C B C A B D D B A
A C B C A C D D B A
```
```python=
from itertools import islice, product, pairwise
prime = (2, 3, 5, 7)
square = (0, 1, 4, 9)
print(*range(1, 11))
for l in product(range(4), repeat=10):
# Q1
if l[0] != next((i for i, v in enumerate(islice(l, 4)) if v == 0), None):
continue
# Q2
it = (i for i, (a, b) in enumerate(pairwise(l), start=-4) if a == b)
if l[1] != next(it, None) or next(it, None) is not None: continue
# Q3
if l[2] != l[(3, 8, 7, 1)[l[2]]]: continue
# Q4
cnt = [0] * 4
for v in l: cnt[v] += 1
if l[3] + 1 != cnt[0]: continue
# Q5
if l[4] != l[l[4]]: continue
# Q6
if not (
(l[5] == 0 and all(cnt[0] != cnt[i] for i in range(1, 4)))
or cnt[0] == cnt[l[5]]
): continue
# Q7
if abs(l[6] - l[7]) != 3 - l[6]: continue
# Q8
if l[7] != cnt[0]: continue
# Q9
bcd = sum(cnt) - cnt[0]
if not (
(l[8] == 0 and bcd not in prime)
or (l[8] == 1 and bcd in prime)
or (l[8] == 2 and bcd < 5)
or (l[8] == 3 and bcd in square)
): continue
print(*map("ABCD".__getitem__, l))
```
### 腹胖打GO 2024/12/4
最近有一種新興的行業稱為「美食外送員」（以下簡稱外送員），針對網路平台上顧客的訂單，外送員先到店家取餐，再送達下訂的顧客家中，即可得到一筆酬勞。
小叡加入外送員這行業已經有一段時間，由於接單的效率不高，導致收入不如預期。
這時他發現其實每天一早就可以知道整天有哪些訂單，只要細心規劃，就可以讓那一天得到更多的酬勞。
但是由於訂單的數量太多，小叡不知道該怎麼計算，你能幫他找出那天最高的酬勞有多少嗎？
輸入資料的第一行有一個正整數 $T$，代表下面有T組測試資料。
第二行有一個正整數 $N$，代表這一天有 $N$ 筆訂單。
接下來有 $N$ 行，每行裡面有三個正整數 $A$、$B$、$C$，代表這筆訂單是 $A$ 時間要到店家取餐，B$ 時間送達顧客家，即可得到 $C$ 的酬勞。
在此假設小叡對所有的訂單都有最優先的接單權，而且小叡送達顧客家中，下一個單位時間可瞬間移動至下一個店家門口，而接單過程中，是無法同時再接其他訂單，也就是從 $A$ 到 $B$ 時間為該訂單所用，$B+1$ 時間起才能再進行下一個訂單。
APCS p4 中等難度的 DP 題。
依照結束時間排列並分組，對於每一個結束時間，二分搜各起點的最佳解。
老師原本預期的似乎是 $O(n^2)$ 解。
$Time: O(n \log_2 n), Space: O(n)$
```python=
def main():
from sys import stdin
from bisect import bisect_left
from itertools import groupby
from operator import itemgetter
e = stdin.readline
for _ in range(int(e())):
n = int(e()) # 訂單數量
ends = [0] # 各訂單結束時間
vals = [0] # 各訂單最佳解
best = 0 # 當前最佳解
for end, g in groupby(
sorted((tuple(map(int, e().split())) for _ in range(n)),
key=itemgetter(1)), # 按照結束時間排序
key=itemgetter(1) # 按照結束時間分組 求每一結束時間的最佳解
):
update = False # 這個結束點是否更新答案
for start, _, value in g:
idx = bisect_left(ends, start) - 1 # rightmost less than
value += vals[idx] # 加上可轉移的最高酬勞(max結束時間 < 此單開始時間)
if value > best: # 更新最佳解
update = True
best = value
if update: # 如果有更新最佳解 就加入前置狀態中
ends.append(end)
vals.append(best)
print(best)
main()
```
### 統一發票兌獎系統 2024/12/10
每到單數月 $25$ 日，就是統一發票的開獎日，你是否每隔兩個月就會期待這一天呢？由於原本統一發票的中獎號碼有一組特獎、三組頭獎和零至三組的增開六獎，這裡我們將題目簡化，改成只有一組的頭獎中獎號碼，並將中獎規則修改如下：頭獎：和頭獎中獎號碼完全相同者，可得 $20$ 萬。二獎：末七碼和頭獎中獎號碼末七位相同者，可得 $4$ 萬元。三獎：末六碼和頭獎中獎號碼末六位相同者，可得 $1$ 萬元。四獎：末五碼和頭獎中獎號碼末五位相同者，可得 $4$ 千元。五獎：末四碼和頭獎中獎號碼末四位相同者，可得 $1$ 千元。六獎：末三碼和頭獎中獎號碼末三位相同者，可得 $2$ 百元。
現在給你頭獎中獎號碼以及發票上的號碼，請你判斷它的得獎金額。
輸入說明
輸入資料有兩組八位數的號碼，第一組是頭獎中獎號碼，第二組是發票上的號碼。
輸出說明
請你輸出這張發票可以得到多少獎金（沒中獎請輸出 $0$）。
號碼很短只有 $8$ 位，直接 slice 字串就好了。
如果要好的時間複雜度，可以從末尾判斷回來，輸出最後一個仍然相等的。
```python=
def check_prize(head_number: str, invoice_number: str) -> int:
prize_rules = [
(0, 200000), # 完全相同
(-7, 40000), # 末七碼相同
(-6, 10000), # 末六碼相同
(-5, 4000), # 末五碼相同
(-4, 1000), # 末四碼相同
(-3, 200), # 末三碼相同
]
for length, prize in prize_rules:
if head_number[length:] == invoice_number[length:]:
return prize
return 0
def main() -> None:
total_prize = 0
while line := input("請輸入頭獎號碼和發票號碼: ").rstrip():
head_number, invoice_number = line.split()
prize = check_prize(head_number, invoice_number)
total_prize += prize
print(f"這張發票的獎金: {prize}元")
print(f"此次兌獎共中獎: {total_prize}元")
main()
```
### 愛的魔力轉圈圈 2024/12/10
這部偶像劇有四個男角、四個女角，以下用男一~男四，女一~女四來代表。
劇情開始的時候，八人的感情狀況都是單戀，一個愛一個，剛好形成一個圓圈，沒有人能湊成一對
已知：『女二』愛的男生愛著『女一』『女四』愛的男生愛的女生愛著『男一』『女三』愛的男生愛的女生愛著『男三』『男二』愛的女生不愛『男四』『男四』和『男一』都不愛『女四』
請問，你能理清這八人的感情狀況嗎？
首先，給 $8$ 人上標記並簡化一下規則：
```
0. 02 _ 01
1. 04 _ _ 11
2. 03 _ _ 13
3. 12 _ X14
4. 14 X04
5. 11 X04
```
環狀問題，將編號 $0$ 的規則當作初始狀態：$[2, 0, 1, 0, 0, 0, 0, 0]$。
每層 DFS 窮舉一個位置，並根據規則填上腳色編號。
```python=
def rec(d):
if all(cur):
for i in range(0, 8, 2):
if (
(cur[i - 3] == 2 and cur[i - 1] == 4)
or (cur[i - 1] == 4 and cur[i] == 4)
or (cur[i - 1] == 1 and cur[i] == 4)
):
return
print(*(f"{'女男'[i & 1]}{v}" for i, v in enumerate(cur)))
return
for i in range(0, 8, 2):
if d == 1 and not cur[i - 4] and not cur[i - 1]:
cur[i - 4], cur[i - 1] = 4, 1
rec(2)
cur[i - 4], cur[i - 1] = 0, 0
elif d == 2 and not cur[i - 4] and not cur[i - 1]:
cur[i - 4], cur[i - 1] = 3, 3
rec(3)
cur[i - 4], cur[i - 1] = 0, 0
elif d == 3 and not cur[i - 3] and cur[i - 1] != 4:
cur[i - 3] = 2
rec(4)
cur[i - 3] = 0
elif d == 4 and not cur[i - 1] and cur[i] != 4:
cur[i - 1] = 4
rec(5)
cur[i - 1] = 0
elif d == 5 and not cur[i - 1] and cur[i] != 4:
cur[i - 1] = 1
rec(6)
cur[i - 1] = 0
cur = [2, 0, 1, 0, 0, 0, 0, 0]
rec(1)
```
### 志願分發 2024/12/11
多元選修、學校選社團、指考或聯招通通需要填志願，考試志願分發的步驟如下：
1. 先將每個人按照考試分數由高而低排序。
2. 由分數高的人，先依照其志願 $1$、志願 $2$、志願 $3$...順序選擇學校。每選到一個學校，則該校的缺額應該減一。
模擬題，依照題意實作即可。
題目的數字都很小，而且格子數量固定，感覺比較受限。若是題目限制更寬泛一些應該會更有趣。
答案：
```
1 94 1 2 3 1 1
2 93 2 1 3 2 1
3 92 1 2 3 1 1
4 91 1 2 3 2 2
5 90 2 0 0 2 1
6 89 1 2 3 3 3
7 88 1 0 0 0 0
8 87 3 1 0 3 1
9 86 2 1 0 0 0
10 85 2 1 0 0 0
1 2 0 2 1 3 0 92
2 3 0 3 2 4 5 90
3 3 1 2 6 8 0 87
```
```python=
# 根據題目給的資訊打表
students = [
[94, 1, 2, 3, 0, 0],
[93, 2, 1, 3, 0, 0],
[92, 1, 2, 3, 0, 0],
[91, 1, 2, 3, 0, 0],
[90, 2, 0, 0, 0, 0],
[89, 1, 2, 3, 0, 0],
[88, 1, 0, 0, 0, 0],
[87, 3, 1, 0, 0, 0],
[86, 2, 1, 0, 0, 0],
[85, 2, 1, 0, 0, 0]
]
schools = [
[2, 2, 0, 0, 0, 0, None],
[3, 3, 0, 0, 0, 0, None],
[3, 3, 0, 0, 0, 0, None]
]
for student_id, student in enumerate(students, start=1):
score = student[0]
for rank, preference in enumerate(student[1:4], start=1):
if not preference: break
school = schools[preference - 1] # 0-based
if school[1]:
school[1] -= 1
school[2] += 1
school[2 + school[2]] = student_id
school[6] = (score if school[6] is None
else min(score, school[6]))
student[4] = preference
student[5] = rank
break
print(f"{student_id:2}", *student)
print()
for school_id, school in enumerate(schools, start=1):
print(f"{school_id:2}", *school)
```
### 編碼破解 2024/12/17
在第二次世界大戰中，德軍的通訊編碼被美國破解，以致於機密被美國竊聽而慘敗。假設現在有一種簡易的文字編碼規則如下：將訊息每個字母往後推兩位再傳出去，例如 A→C、B→D，而後面的 Y→A、Z→B，所有的訊息都是大寫字母。現在給你編過碼的文字，請你解讀回原本的訊息。
經典的凱薩密碼，以下程式則是輸出所有位移可能，並且支援大小寫字母，英文字母以外則會原樣輸出。
```python=
s = input()
print("\n".join("".join(
(chr((ord(i) - 65 + shift) % 26 + 65) if i.isupper() else
chr((ord(i) - 97 + shift) % 26 + 97) if i.islower() else
i) for i in s
) for shift in range(26)))
```
### 鐵達尼號的求生號碼 2024/12/17
鐵達尼號撞到冰山後要沉沒了，傑克與蘿絲成功找上逃生小艇，同樣找上共有 $30$ 人，但是小艇最大載客量只有 $15$ 人，任何人都不想放棄生存的機會，於是，大家圍成一圈並给予編號，約定圍成一圈、然後依序數到 $9$ 的乘客要下船，請問最後可以留在小艇的號碼有哪些。
經典的約瑟夫問題，使用 BIT 維護剩下的人形成的前綴和，並在 BIT 上二分搜找下一個下船的人。
答案：1 2 3 4 10 11 13 14 15 17 20 21 25 28 29
$Time: O(k \log_2 n), Space: O(n)$
```python=
# 總人數, 數到幾下船, 下船幾個
n, m, k = 30, 9, 15
# build BIT
bit = [i & -i for i in range(n + 1)]
# n's highest bit
hb = 1 << n.bit_length() - 1
target = 0
for r in range(n, n - k, -1):
# update bisect target
target = (target + m - 1) % r
# bisect_right for target on BIT
b = hb
i = v = 0
while b > 0:
if (_i := i + b) <= n and (_v := v + bit[_i]) <= target:
i, v = _i, _v
b >>= 1
# update BIT
i += 1 # 0-based to 1-based
print(f"remove {i}")
while i <= n:
bit[i] -= 1
i += i & -i
# BIt to array
for i in range(n, 0, -1):
if (j := i + (i & -i)) <= n:
bit[j] -= bit[i]
print("survived:", *(i for i, v in enumerate(bit) if v))
```
### 編碼問題 2024/12/17
給定一個英文字串，請計算使用霍夫曼編碼對這串字符串進行編碼所需的存儲空間（以位元為單位）。
Huffman 編碼是一種常用的數據壓縮算法，它通過對字符出現的頻率進行編碼，將出現頻率高的字符用較短的位元串（Bit Strings）表示，而出現頻率低的字符用較長的位元串（Bit Strings）表示，從而實現對數據的壓縮。
霍夫曼編碼的精隨在於「依照頻率給予編碼」，即 `build_tree` 部分。
使用一個 `priority queue` ，每一輪取最小的兩個節點合併。可以用一次 Sort 還有兩個 `queue` 來達成常數更小的建樹，但前者的可讀性更高，也較容易實作。
DFS 都是用迭代而不是遞迴寫的，只能說非常優雅。
這個東西我也搞了半個晚上。
```python=
from collections import Counter
from heapq import heapify, heappop, heappush
def build_tree(s: str) -> tuple: # O(nlogn) priority queue
freq = Counter(s)
n = len(freq)
h = [(v, k) for k, v in freq.items()]
heapify(h)
# 給每一項加上獨特編碼 以免rank相同時 heapq跑去比較node 而TypeError
h = [(v, i, k) for i, (v, k) in enumerate(h)]
# tree = node: tuple[le: node, ri: node] | str
i = n
while len(h) > 1:
u, _, le = heappop(h)
v, _, ri = heappop(h)
pa = (le, ri)
heappush(h, (u + v, i, pa))
i += 1
return h[0][2]
def tree2dict(root: tuple) -> dict[str, int]:
key = 0
dfs = [(root, 1)] # 每個編碼加上前綴1 防止int的前綴0都被削去
dic = {}
while dfs:
cur, bit = dfs.pop()
key = (key << 1) | bit
if cur is None: # visited node
key >>= 2
elif isinstance(cur, str): # leaf
dic[cur] = key
key >>= 1
else:
le, ri = cur
dfs.append((None, 0)) # sentinel
dfs.append((le, 0))
dfs.append((ri, 1))
return dic
def compress(s: str, dic: dict) -> int:
res = 0
for bit in map(dic.get, s):
res <<= bit.bit_length()
res |= bit
return res
def decompress(bit: int, root: tuple) -> str:
res = []
cur = dummy = (None, root)
for i in map(int, bin(bit).lstrip("0b")):
cur = cur[i]
if isinstance(cur, str):
res.append(cur)
cur = dummy
return "".join(res)
s = input()
print(f"inputed string: {s}")
tree: tuple = build_tree(s)
dic: dict = tree2dict(tree)
compressed: str = compress(s, dic)
print(f"compressed int: {compressed}")
print(f"compressed bit: {compressed:b}")
print(f"bit length: {compressed.bit_length()}")
print(f"decompressed str: {decompress(compressed, tree)}")
```
### 三角形的組合 2024/12/24
已知一個三角形的任意兩邊和必定大於第三邊，小恩的爸爸給了他一大堆長短不一的木棒，小恩想知道這些木棒到底可以組合出幾個不同的三角形，長度相同但是不同木棒所組成的三角形視為不同的三角形，例如 $4$ 根木棒長度為 $3$、$3$、$3$、$3$，則可以組合出 $4$ 個不同的三角形。
經典題，窮舉三者之一，剩下兩者雙指標伺候。
$Time: O(n^2), Space: O(n)$
```python=
n = int(input())
l = sorted(map(int, input().split()))
ans = 0
for ri in range(2, n):
i, j = 0, ri - 1
while i < j:
if l[i] + l[j] > l[ri]:
ans += j - i
j -= 1
else:
i += 1
print(ans)
```
### 真相只有一個 2024/12/28
怪盜積德寄來了一封預告信：
『今晚，我會選擇港口的 $1 \sim 60$ 號倉庫中的其中一個倉庫，然後得到裡面的寶藏。
我鎖定的是 $0$、$1$、$2$、$4$、$7$、$15$、$31$，這些數隨意相加也加不到的數字，但是，加的時候一個數字只能出現一次。』
警方仔細算了一陣子，終於找到那唯一符合的倉庫，請問到底要在哪一號倉庫警備才對呢？
不帶權的 0-1 背包問題，可以用一個 bit 紀錄那些數字可以被組合出來，再用位元運算找 $0$ 的位置。
答案：$30$
```python=
bit = 1
for i in map(int, "0、1、2、4、7、15、31".split("、")):
bit |= bit << i
bit = ~bit # 翻轉 找0位置
print((bit & -bit).bit_length() - 1) # lowbit
```
### 生成字串 2025/1/4
請問依照圖片規則可以出現幾種不同字串、字母數量限定為 $8$ 以下。
要注意 `W` 的那兩條，只有往左的有 `W`，往右的為空字串。
BFS 一直在圖上遍歷，直到 queue 內的所有字串長度都超過 $8$。
答案：
總共: 26
2: TE
3: TWE
4: TRUE TWWE
5: TRUWE TWWWE TWRUE
6: TWWWWE TWWRUE TWRUWE TRUWWE
7: TWRUWWE TWWWRUE TRUWWWE TWWRUWE TRUWRUE TWWWWWE
8: TRUWWWWE TWRUWWWE TWWWWRUE TRUWRUWE TWWRUWWE TWWWRUWE TWWWWWWE TRUWWRUE TWRUWRUE
```python=
from itertools import groupby
# 建圖
G = [[("T", 1)],
[("R", 2), ("", 3)],
[("U", 3)],
[("W", 1), ("E", 4)]]
ans = set()
cur = [("", 0)]
while cur:
nxt = []
for string, node in cur:
for nxt_char, nxt_node in G[node]:
nxt_string = string + nxt_char
if nxt_node == 4:
ans.add(nxt_string)
elif len(nxt_string) < 8:
nxt.append((nxt_string, nxt_node))
cur = nxt
print("總共:", len(ans))
for l, group in groupby(sorted(ans, key=len), key=len):
print(f"{l}:", *group)
```
### 移動迷宮 2025/1/4
請問最短時間需要幾秒鐘？
簡單一點，使用 Dijkstra 找最短路。（也可以維護五個 queue，但麻煩）
這題的建圖真的十分噁心，我打了幾十分鐘。
因為建圖的格式關係，我走的兩步是原題中的一步，所以將迷宮間轉換的時間 $5$ 翻倍成 $10$，最後再將時間除以 $2$。
我將圖壓平成一個一維陣列，方便實作，因為原圖的邊框很明確，所以不需要額外判斷 edge case。
答案：$18$
```python=
import sys
from io import StringIO
# 建圖
testcase = """#############
# # #
# ### # ### #
# A# # # #
### # ### # #
# # # #
# ######### #
# # #
##### # ### #
# # B# #
# ######### #
# #
#############
#############
# # #
# # # # #
# # # #
# ### # # ###
# # # #
##### ### #
# # #
# ######### #
# # #
# # # # ### #
# # # # #
#############
"""
sys.stdin = StringIO(testcase)
def main():
from sys import stdin
from itertools import batched
from heapq import heappop, heappush
inf = float("INF")
def new_pos(step, pos, symbol):
if not 0 <= pos < size: return
val = l[pos]
if val is None or step >= val: return
l[pos] = step
frm[pos] = symbol
heappush(dij, (step, pos))
l = [(None if i == "#" else inf if i == " " else i)
for line in stdin for i in line.rstrip()]
size = len(l)
frm = [" "] * size
for row in batched(l, 13):
print(*map({None: "#", inf: " ", "A": "A", "B": "B"}.__getitem__, row))
start = next(i for i, v in enumerate(l) if v == "A")
end = next(i for i, v in enumerate(l) if v == "B")
l[start] = l[end] = inf
step = 0
dij = [(step, start)]
while dij:
step, pos = heappop(dij)
if pos == end: break
if step > l[pos]: continue
new_pos(step + 1, pos - 1, ">")
new_pos(step + 1, pos + 1, "<")
new_pos(step + 1, pos - 13, "v")
new_pos(step + 1, pos + 13, "^")
new_pos(step + 10, pos - 169, ".")
new_pos(step + 10, pos + 169, "x")
for row in batched(frm, 13):
print(*row)
print(step >> 1)
main()
```
## 心得
原本以為會像一直以來的資訊課一樣，只是 `cache(祖傳題庫)` 來應付一字不差的選擇題，或是把早就 Leaked 的程式碼以漢明距離為零的精準度 C-V 到段考的手寫答案卷上就會 `return 100`，hardcoded 無腦 AC，彷彿人生已經寫死在 config 檔裡。
但仁郁老師卻肯 allocate 自己的時間、榨乾自己的靈感 buffer，精心設計各種有趣的原創題，連段考都改成斷網上機，不管是霍夫曼編碼、義賊廖添丁，或者各式各樣窮舉(?)題都十分有意思，成功 override 我原本只想 C-V 應付的惰性，燃爆自主鑽研、探索學習的熱情，並使我完成作業、甚至實作出遠超作業要求的內容後收穫良多，感謝仁郁老師用心地出題 :D。
這些題目也無庸置疑地讓我的實作能力更臻純青，日後也將懷抱著這股對程式設計的熱情，窮舉更多推理題，直到 `stack overflow`！
## 附件
### [包含以上所有程式碼的文件](https://colab.research.google.com/drive/1Zua33r4O5c5U8umzuteKWIQGGAltdhdu?hl=en)
### [本文的連結](https://hackmd.io/@ericshen19555/Sk2IhIjOyl)
Sign in with Wallet
Connect another wallet