ZeroJudge 解題筆記：d045. 11222 - Only I did it!

作者：王一哲
日期：2026年3月30日


ZeroJudge 題目連結：d045. 11222 - Only I did it!

解題想法

我是用集合處理這題。先將三人解的題號分別存入集合 $a, b, c$，只有第一個人解出來的題目就是 $a$ 對 $b, c$ 的聯集取差集，只有第二個人解出來的題目就是 $b$ 對 $c, a$ 的聯集取差集，只有第三個人解出來的題目就是 $c$ 對 $a, b$ 的聯集取差集。分別計算三個差集的長度，輸出最長的差集對應的朋友編號、差集長度與題號。

Python 程式碼

使用時間約為 9 ms，記憶體約為 3.5 MB，通過測試。

T = int(input())
for t in range(1, T+1):
    print(f"Case #{t:d}:")
    a = set(tuple(map(int, input().split()))[1:])
    b = set(tuple(map(int, input().split()))[1:])
    c = set(tuple(map(int, input().split()))[1:])
    a_bc = a.difference(b.union(c))
    b_ca = b.difference(c.union(a))
    c_ab = c.difference(a.union(b))
    m, n, p = len(a_bc), len(b_ca), len(c_ab)
    imax = max(m, n, p)
    if m == imax: print(1, m, *sorted(a_bc))
    if n == imax: print(2, n, *sorted(b_ca))
    if p == imax: print(3, p, *sorted(c_ab))

ZeroJudge 解題筆記：d041. 11219 - How old are you?

作者：王一哲
日期：2026年3月29日


ZeroJudge 題目連結：d041. 11219 - How old are you?

解題想法

用自訂函式計算年齡，如果今天的日、月、年分別為 $dt, mt, yt$，生日的日、月、年分別為 $db, mb, yb$，先假設年齡 $age = yt - yb$，接下來再依照 $(mt, dt), (mb, db)$ 修正 $age$ 的值，如果 $mt < mb$ 或是 $mt = mb, dt < db$，則 $age$ 減 1。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

def cal_age(today, birthday):
    dt, mt, yt = map(int, today.split('/'))
    db, mb, yb = map(int, birthday.split('/'))
    age = yt - yb
    #if (mt, dt) < (mb, db): age -= 1  # 第5、6行效果相同
    if mt < mb or (mt == mb and dt < db): age -= 1
    if age < 0: return "Invalid birth date"
    if age > 130: return "Check birth date"
    return str(age)

T = int(input())
for t in range(1, T+1):
    _ = input()
    ans = cal_age(input(), input())
    print(f"Case #{t:d}: {ans:s}")

ZeroJudge 解題筆記：c203. 13185 - DPA Numbers I

作者：王一哲
日期：2026年3月28日


ZeroJudge 題目連結：c203. 13185 - DPA Numbers I

解題想法

這題的測資很小，硬算就好。寫一個自訂函式 test 找 n 的所有因數和 $isum$，$isum$ 至少為 1，接下來從 $i = 2$ 開始往上測試到 $i = \sqrt{n}$ 為止，如果 $i$ 可以整除 $n$，則 $isum$ 加上 $i + (n/i)$；如果 $i^2 = n$，則 $isum$ 要再減去 $i$。最後比較 $isum$ 與 $n$ 的關係，輸出對應的答案。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

def test(n):
    isum = 1
    for i in range(2, int(n**0.5) + 1):
        if n%i == 0:
            isum += i + n//i
        if i*i == n:
            isum -= i
    if isum == n: return "perfect"
    if isum < n: return "deficient"
    return "abundant"

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        result.append(f"{test(int(data[ptr]))}\n")
        ptr += 1
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：c187. 10986 - Sending email

作者：王一哲
日期：2026年3月27日


ZeroJudge 題目連結：c187. 10986 - Sending email

解題想法

這題要求從起點 $S$ 到終點 $T$ 的最短距離，可以用戴克斯特拉演算法 (Dijkstra's algorithm) 解題。

Python 程式碼

使用時間約為 0.2 s，記憶體約為 20.7 MB，通過測試。

import sys, heapq

result = []  # 要輸出的結果
T = int(sys.stdin.readline())  # T 組測資
for t in range(1, T+1):  # 執行 T 次
    n, m, start, end = map(int, input().split())  # n 個節點，m 條邊，起點、終點
    if start == end:  # 特例，起點等於終點
        result.append(f"Case #{t:d}: 0\n")  # 答案 0
        for _ in range(m): _ = sys.stdin.readline()  # 依然要讀取以下 m 行測資
    else:  # 一般的狀況
        graph = dict()  # 節點連接關係
        for _ in range(m):  # 讀取 m 行測資
            u, v, w = map(int, sys.stdin.readline().split())  # 節點 u, v 相連，邊長 w
            if u not in graph: graph[u] = [(v, w)]
            else: graph[u].append((v, w))
            if v not in graph: graph[v] = [(u, w)]
            else: graph[v].append((u, w))
        cost = [float('inf')]*n  # 走到每個節點的最低成本
        pq = [(0, start)]  # 最小優先佇列，放入 (0, 起點)
        while pq and pq[0][1] != end:  # 如果 pq 還有資料而且最上面的資料不是終點
            curr, u = heapq.heappop(pq)  # 取出 pq 最上面的資料
            if u not in graph: continue  # 如果 u 沒有子節點，找下一個點
            for v, w in graph[u]:  # 依序讀取 u 的子節點及權重
                new_w = curr + w  # 新的成本
                if new_w < cost[v]:  # 如果比原來走到 v 的最低成本還低
                    cost[v] = new_w  # 更新 cost[v]
                    heapq.heappush(pq, (new_w, v))  # (new_w, v) 加入 pq
          # 如果 cost[end] 不等於預設值，可以走到終點
        ans = str(cost[end]) if cost[end] != float('inf') else "unreachable"
        result.append(f"Case #{t:d}: {ans:s}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c139. 00291 - The House Of Santa Claus

作者：王一哲
日期：2026年3月26日


ZeroJudge 題目連結：c139. 00291 - The House Of Santa Claus

解題想法

先用一個陣列儲存每個節點可以連接的節點編號，再寫一個自訂函式，用遞迴及回溯跑所有可能的畫法。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

def solve():
    import sys
    ans = []
    graph = [[], [2, 3, 5], [1, 3, 5],
             [1, 2, 4, 5], [3, 5], [1, 2, 3, 4]]
    def backtrack(u, path, visited):
        if len(path) == 9:
            ans.append(path)
            return
        for v in graph[u]:
            if (u, v) in visited or (v, u) in visited: continue
            visited.add((u, v))
            visited.add((v, u))
            backtrack(v, path + [v], visited)
            visited.remove((u, v))
            visited.remove((v, u))
    backtrack(1, [1], set())
    result = ["".join(map(str, a)) + "\n" for a in ans]
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：c134. 00668 - Parliament

作者：王一哲
日期：2026年3月25日


ZeroJudge 題目連結：c134. 00668 - Parliament

解題想法

這題要將某個正整數 n，分拆成任意個不重複的正整數，使分拆後的正整數乘積最大。因為拆成 1 不會使乘積變大，至少從 2 開始分拆，盡量拆成越多個數字越好。如果 $n \leq 4$ 分拆後的正整數乘積不會大於 $n$，因此題目的測資 $\geq 5$ 。分拆時從 $i=2$ 開始測試，每次分拆後將 $n-i$，直到 $n < i$ 為止，如果最後 $n > 0$ ，再將分拆出來最大的 $n$ 個數都加 1。 注意：此題的答案只要輸出分拆後的正整數，不需要輸出個數。題目敘述與測資的要求不合。

Python 程式碼

使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    T = int(data[0])
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if result:  # 不是第一組測資，先換行
            result.append("\n")
        if n <= 4:  # 特例，小於等於 4，不能分拆
            result.append(f"{n:d}\n")
        else:
            i = 2  # 從 2 開始測試
            ans = []  # 分拆的數字
            while n >= i:  # 如果 n 還能分拆
                ans.append(i)  # i 加入 anss
                n -= i  # n 減去 i
                i += 1  # i 加 1
            for j in range(len(ans)-1, len(ans)-n-1, -1):  # 最後 n 個數加 1
                ans[j] += 1
            res = " ".join(map(str, ans))
            result.append(f"{res}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：c133. 00639 - Don't Get Rooked

作者：王一哲
日期：2026年3月24日


ZeroJudge 題目連結：c133. 00639 - Don't Get Rooked

解題想法

這題很像八皇后，用集合 rooks 儲存已經放置城堡的位置，寫一個自訂函式 is_safe 檢查代入的位置 (row, col) 是否安全；再寫另一個自訂函式 backtrack 代入 (0, 0)，用遞迴與回溯找答案。

Python 程式碼

使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

import sys

def solve(n):
    grid = [list(sys.stdin.readline().strip()) for _ in range(n)]
    rooks = set()  # 已放置城堡的位置
    ans = 0  # 答案
    """ grid[row][col] 處是否可以放置城堡 """
    def is_safe(row, col):
        for r in range(row-1, -1, -1):  # 向上檢查
            if grid[r][col] == 'X': break
            if (r, col) in rooks: return False
        for r in range(row+1, n, 1):  # 向下檢查
            if grid[r][col] == 'X': break
            if (r, col) in rooks: return False
        for c in range(col-1, -1, -1):  # 向左檢查
            if grid[row][c] == 'X': break
            if (row, c) in rooks: return False
        for c in range(col+1, n, 1):  # 向右檢查
            if grid[row][c] == 'X': break
            if (row, c) in rooks: return False
        return True  # 通過 4 個方向的檢查，回傳 True
    """ 回溯，代入 row, col """
    def backtrack(row, col):
        nonlocal ans  # 這樣才能修改函數外的變數值
        if col == n:  # 如果欄已經出界
            col = 0   # 歸零
            row += 1  # 找下一列
        if row == n:  # 如果列已經出界
            ans = max(ans, len(rooks))  # 更新答案
            return    # 遞迴出口
        # 測試 (row, col) 是否可以放置城堡
        if grid[row][col] == '.' and is_safe(row, col):
            rooks.add((row, col))  # 放置城堡
            backtrack(row, col+1)  # 遞迴，測試下一欄是否能放置城堡
            rooks.remove((row, col))  # 回溯
        backtrack(row, col+1)  # 遞迴，不在 (row, col) 處放置城堡
    """ End of backtrack """
    backtrack(0, 0)  # 從 (0, 0) 開始測試
    return ans

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    result.append(f"{solve(n):d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c131. 00615 - Is It A Tree?

作者：王一哲
日期：2026年3月23日


ZeroJudge 題目連結：c131. 00615 - Is It A Tree?

解題想法

用自訂函式 test 代入節點資料，檢測是否為樹。檢測項目為

• 讀取邊的端點 $u, v$，因為 $u$ 可以連到 $v$，$u$ 為父節點，$v$ 為子節點。如果 $v$ 已經有父節點，因為一個節點不可能有兩個父節點，不是樹，回傳 False。
• 檢查是否只有一個根節點，因為不可能有兩個根節點。
• 用 BFS 從根節點開始走訪，如果能夠走到所有節點，是樹，回傳 True。

Python 程式碼

使用時間約為 8 ms，記憶體約為 3.3 MB，通過測試。

import sys
from collections import deque

def test(data):  # 檢測用的函式，輸入節點資料
    if data == [0, 0]: return True  # 特例，資料只有 0, 0，回傳 True
    parent, children = dict(), dict()  # {v: u} v 的父節點是 u，u 的子節點集合
    nodes = set()  # 所有節點的集合
    for i in range(0, len(data), 2):  # 一次讀取兩筆測資
        u, v = data[i], data[i+1]  # 節點 u 連到 v
        nodes.add(u); nodes.add(v)  # u, v 加入 nodes
        if v in parent: return False  # 如果 v 已經有父節點，回傳 True
        parent[v] = u  # v 的父節點是 u
        if u not in children: children[u] = {v}  # 如果 u 還沒有子節點，建立集合，加入 v
        else: children[u].add(v)  # 反之，直接加入 v
    ### 檢查是否只有一個根節點 ###
    root = -1  # 根節點
    for node in nodes:  # 依序讀取所有節點
        if node not in parent:  # 如果 node 沒有父節點
            if root == -1: root = node  # 如果 root 等於 -1，node 是根節點
            elif root != -1: return False  # 反之，不可能有兩個根節點，回傳 False
    ### BFS 檢查所有節點是否相連 ###
    que = deque([root])  # 待走訪佇列，先加入根節點
    visited = {node: False for node in nodes}  # 各節點走訪狀態
    visited[root] = True  # 已走訪根㿝3點
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 開頭取出資料
        if u not in children: continue  # 如果 u 沒有子節點，找下一個點
        for v in children[u]:  # 依序讀取 u 的子節點 v
            if visited[v]: return False  # 如果 v 已走訪，環狀結構，回傳 False
            visited[v] = True  # 已走訪 v
            que.append(v)  # v 加入 que
    ### End of BFS，如果所有節點已走訪回傳 True ###
    return all(visited.values())

"""" 讀取資料並解題 """
lines = sys.stdin.readlines()  # 讀取所有測資
idx = 0  # 從 lines 讀取資料的索引值
ca = 0  # 第幾組測資
result = []  # 要輸出的字串
while idx < len(lines):  # 如果 idx 還沒有出界繼續執行
    line = lines[idx]  # 讀取一行
    idx += 1
    line = line.strip()  # 跳過空行
    if not line: continue
    if line == "-1 -1": break  # 中止迴圈的條件
    ca += 1
    if line == "0 0":  # 特例，這組測資只有 0 0
        data = [0, 0]
    else:  # 其它狀況
        data = list(map(int, line.split()))  # 轉成整數串列
        if data[-1] == 0 and data[-2] == 0:  # 如果最後兩項都是 0
            data = data[:-2]  # 去掉最後兩項，結束這組測資
        else:  # 還有測資
            while True:  # 繼續讀取，直到結尾是 0 0 為止
                tmp = list(map(int, lines[idx].split()))
                idx += 1
                if tmp[-1] == 0 and tmp[-2] == 0:
                    data += tmp[:-2]
                    break
                else: data += tmp
    state = " " if test(data) else " not "  # 依照測試結果決定輸出的內容
    result.append(f"Case {ca:d} is{state:s}a tree.\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c130. 00574 - Sum It Up

作者：王一哲
日期：2026年3月22日


ZeroJudge 題目連結：c130. 00574 - Sum It Up

解題想法

這題考自訂函式的遞迴與回溯，同時用 set 儲存已經測試的過組合。

Python 程式碼

使用時間約為 10 ms，記憶體約為 3.4 MB，通過測試。

import sys

def solve(line):  # 解題用的函式
    nums = list(map(int, line.split()))  # 讀取一行測資
    t, n = nums[0], nums[1]  # 前兩項是目標、可用數字數量
    nums = nums[2:]  # 後面是可用的數字
    tested = set()  # 已測試過的組合，要用 tuple
    result = [f"Sums of {t:d}:\n"]  # 答案開頭
    """ 回溯，代入已選數字、加總、起點索引值 """
    def backtrack(choice, total, start):
        if tuple(choice) in tested: return  # 已測試過，遞迴出口
        tested.add(tuple(choice))  # choice 轉成 tuple 加入 tested
        if total > t: return  # 加總大於目標，遞迴出口
        if total == t:  # 加總等於目標，新增一組解，遞迴出口
            result.append("+".join(map(str, choice)) + "\n")
            return
        for i in range(start, n):  # 依序測試 nums[start] ~ nums[n-1]
            backtrack(choice + [nums[i]], total + nums[i], i+1)  # 選擇 nums[i]
            backtrack(choice, total, i+1)  # 不選擇 nums[i]
    """ End of backtrack """
    backtrack([], 0, 0)  # 呼叫 backtrack，代入空串列、加總 0、起點 0
    if len(result) == 1: result.append("NONE\n")  # 如果 result 長度為 1，加入 NONE
    sys.stdout.write("".join(result))  # 輸出答案

if __name__ == "__main__":
    for line in sys.stdin:
        line = line.strip()
        if not line: continue
        if line == "0 0": break
        solve(line)

ZeroJudge 解題筆記：c129. 00572 - Oil Deposits

作者：王一哲
日期：2026年3月21日


ZeroJudge 題目連結：c129. 00572 - Oil Deposits

解題想法

這類連通區塊的題目用 BFS 就對了。但是這題的連通方式跟踩地雷一樣，有 8 個方向要檢查。

Python 程式碼

使用時間約為 13 ms，記憶體約為 3.4 MB，通過測試。

import sys
from collections import deque

for line in sys.stdin:
    if not line.strip(): continue
    m, n = map(int, line.split())  # 地圖尺寸 m*n
    if m == 0 and n == 0: break  # 中止迴圈
    grid = [list(sys.stdin.readline().strip()) + ['*'] for _ in range(m)]  # 地圖最右邊加 * 當作哨兵
    grid.append(['*']*(n+1))  # 地圖最下方加 * 當作哨兵
    cnt = 0  # 連通區域數量
    """ BFS """
    for i in range(m):  # 依序掃過地圖每一格，不包含哨兵
        for j in range(n):
            if grid[i][j] == '*': continue  # 不含石油，找下一格
            que = deque([(i, j)])  # 待走訪的佇列
            cnt += 1  # 數量加 1
            grid[i][j] = '*'  # 此格已走訪，設定為 *
            while que:  # 如果 que 有資料繼續執行
                r, c = que.popleft()  # 取出 que 最前面的資料
                # 注意，這題的連通方式跟踩地雷一樣，有 8 個方向要檢查
                for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
                    nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                    if grid[nr][nc] == '*': continue  # 不含石油，找下一格
                    grid[nr][nc] = '*'  # 此格已走訪，設定為 *
                    que.append((nr, nc))  # (nr, nc) 加到 que
    """ End of BFS """
    sys.stdout.write(f"{cnt:d}\n")