---
# System prepended metadata

title: 高二上資訊科課程成果
tags: [已完成]

---

# 高二上資訊科課程成果

> 作者：沈宗叡（暴力又被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。請問要怎樣才能過關。

![image](https://hackmd.io/_uploads/ByLVLPiO1l.png)

題目沒講是要先乘除後加減，還是單純由左而右運算，因此我兩種都寫了。

邏輯上就是一般的 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$ 個自然數填入下面的圓圈中，使得每個數的所有相鄰數之和如右圖所示（相鄰為有實線直接相連）

![image](https://hackmd.io/_uploads/S1aGFvsdkx.png)

這種圖論題最麻煩的就是建圖，只能手生，超級地獄。後面還會有更噁的，非常值得期待。

使用 `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)
```

答案：
![image](https://hackmd.io/_uploads/By0f5wouyg.png)

### 消防設備 2024/9/21

基地有 $9$ 座倉庫，為了防火，需在這些倉庫中放兩套消防設備。只要一座倉庫放了消防設備，凡是與它有路連著的倉庫都可以就近使用。這兩套消防設備應該放在哪裡，才能使 $9$ 座倉庫都用得上？

![image](https://hackmd.io/_uploads/ryWVjvsO1g.png)

這題是圖論裡經典的 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

廖添丁從貪官甲家偷了錢以後，挨家挨戶送，最後到乙家。路線不走第二遍，而且一家不漏。他是按照什麼樣的路線走過去的呢？

![image](https://hackmd.io/_uploads/SJaUJuou1l.png)

這題我會！窮舉所有邊的走訪順序就好了！

答案：
總共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$...順序選擇學校。每選到一個學校，則該校的缺額應該減一。

![image](https://hackmd.io/_uploads/ryj9KosO1g.png)

模擬題，依照題意實作即可。
題目的數字都很小，而且格子數量固定，感覺比較受限。若是題目限制更寬泛一些應該會更有趣。

答案：
```
 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$ 以下。

![image](https://hackmd.io/_uploads/SkKe-3idyx.png)

要注意 `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

![image](https://hackmd.io/_uploads/HJV4Mnj_Jx.png)

請問最短時間需要幾秒鐘？

簡單一點，使用 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)

![image](https://hackmd.io/_uploads/SkYAC2s_1e.png)

### [本文的連結](https://hackmd.io/@ericshen19555/Sk2IhIjOyl)

![image](https://hackmd.io/_uploads/HkDqL6jOJe.png)
