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")

ZeroJudge 解題筆記：c128. 00544 - Heavy Cargo

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


ZeroJudge 題目連結：c128. 00544 - Heavy Cargo

解題想法

這題跟 c125. 00534 - Frogger。 依序讀取兩座城市的名稱及道路的承受重量上限，城市之間連接的關係存入字典 graph，key 為城市的名稱，value 為連接的城市名稱，格式為 list；道路資料存入字典 edge，key 為兩座城市 $u, v$ 組成的 tupel，value 為重量，因為是無向圖，$(u, v), (v, u)$ 都要存資料。 開一個陣列 $ans$，儲存到達第 $i$ 座城市的路徑可以承受的最大重量的最小值。接下來用一個最大優先佇列 $pq$，資料為 $(重量, 城市名稱)$，代表到第 $i$ 座城市的路徑上某一條路可以承受的最大重量，重量大的資料放上面。因為 Python 的 heapq 是最小優先佇列，為了把最大值放在上面，重量要加負號。如果 $pq$ 還有資料，而且 $pq$ 最上面的城市不等於終點，while 迴圈繼續執行。每次取出 $pq$ 最上方的資料，目前的重量 $curr$、城市的名稱 $u$，掃過與 $u$ 相連的城市 $v$，取 $curr$ 與 $edge[u, v]$ 較小者為新的重量 $new_w$，如果 $new_w < ans[v]$，更新 $ans[v]$，並將 ${new_w, v}$ 加入 $pq$。

Python 程式碼

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

import sys, heapq

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    n, r = map(int, line.split())  # n 個城市，r 條道路
    if n == 0 and r == 0: break  # 中止迴圈的條件
    ca += 1  # 測資編號加 1
    graph, edge = dict(), dict()  # 城市連接的關係，道路可以承受的重量
    for _ in range(r):  # 讀取 r 條道路
        u, v, w = sys.stdin.readline().split()  # 城市 u、v 之間的道路可以承受重量 w
        w = int(w)  # w 轉成 int
        if u not in graph: graph[u] = [v]  # 如果 u 不在 graph 之中，設定為 [v]
        else: graph[u].append(v)  # 反之，加上 v
        if v not in graph: graph[v] = [u]  # 如果 v 不在 graph 之中，設定為 [u]
        else: graph[v].append(u)  # 反之，加上 u
        edge[u, v] = w  # u、v 之間的道路可以承受重量 w
        edge[v, u] = w
    ans = {k: 0 for k in graph.keys()}  # 走到每個城市的路上可以承受的重量最大值
    start, end = sys.stdin.readline().split()  # 起點、終點
    pq = [(-float('inf'), start)]  # (-重量, 城市)，加負號讓重量大的放上面
    while pq and pq[0][1] != end:  # 如果 pq 有資料而且最上面的城市不是終點
        w, u = heapq.heappop(pq)  # 取出 pq 最上面的重量、城市
        w = -w  # w 轉成正值
        for v in graph[u]:  # 依序取出 u 連接的城市 v
            new_w = min(w, edge[u, v])  # 取 w 與 u、v 之間可以承受重量較小者
            if new_w > ans[v]:  # 如果 new_w 是新的最大值
                ans[v] = new_w  # 更新 ans[v]
                heapq.heappush(pq, (-new_w, v))  # (-new_w, v) 加入 pq
    if ca > 1: result.append("\n")  # 如果不是第 1 筆測資，先換行
    result.append(f"Scenario #{ca:d}\n{ans[end]:d} tons\n")  # 答案加入 result
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c127. 00537 - Artificial Intelligence

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


ZeroJudge 題目連結：c127. 00537 - Artificial Intelligence

解題想法

我用字典儲存前綴詞及單位對應的倍率，從讀取到的字串之中搜尋 I=、U=、P= 這 3 個字串，如果有找到這 3 個字串，再從字串索引值加 2 的位置開始向後讀取字元，找出對應的數字。最後配合前綴詞及單位調整數值的大小，輸出答案。

Python 程式碼

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

prefix = {'m': 0.001, 'k': 1000, 'M': 1000000, 'A': 1, 'V': 1, 'W': 1}  # 前綴詞及單位對應的倍率
T = int(input())  # T 組測資
for t in range(1, T+1):  # t = 1 ~ T
    if t > 1: print()  # 如果不是第 1 組測資，先換行
    print(f"Problem #{t:d}")
    line = input()  # 讀取一行字串
    idx_I = line.find("I=")  # 從字串中找 I= 的索引值
    idx_U = line.find("U=")  # 從字串中找 U= 的索引值
    idx_P = line.find("P=")  # 從字串中找 P= 的索引值
    I, U, P = 0, 0, 0  # 電流、電壓、電功率量值
    if idx_I != -1:  # 字串中有 I=
        tmp = ""  # 暫存量值用的字串
        for c in line[idx_I+2:]:  # 從 idx_I+2 開始讀取字元
            if c.isnumeric() or c == '.': tmp += c   # 如果 c 是數字或小數點，c 加到 tmp
            else:  # 如果 c 是其它字元
                I = float(tmp)  # tmp 轉成浮點數存入 I
                I *= prefix[c]  # 乘以前綴詞對應的倍率
                break  # 中止迴圈
    if idx_U != -1:  # 字串中有 U=
        tmp = ""  # 暫存量值用的字串
        for c in line[idx_U+2:]:  # 從 idx_U+2 開始讀取字元
            if c.isnumeric() or c == '.': tmp += c   # 如果 c 是數字或小數點，c 加到 tmp
            else:  # 如果 c 是其它字元
                U = float(tmp)  # tmp 轉成浮點數存入 U
                U *= prefix[c]  # 乘以前綴詞對應的倍率
                break  # 中止迴圈
    if idx_P != -1:  # 字串中有 P=
        tmp = ""  # 暫存量值用的字串
        for c in line[idx_P+2:]:  # 從 idx_P+2 開始讀取字元
            if c.isnumeric() or c == '.': tmp += c   # 如果 c 是數字或小數點，c 加到 tmp
            else:  # 如果 c 是其它字元
                P = float(tmp)  # tmp 轉成浮點數存入 P
                P *= prefix[c]  # 乘以前綴詞對應的倍率
                break  # 中止迴圈
    ### 印出答案 ###
    if idx_I == -1: print(f"I={P/U:.2f}A")  # 求電流
    elif idx_U == -1: print(f"U={P/I:.2f}V")  # 求電壓
    elif idx_P == -1: print(f"P={I*U:.2f}W")  # 求電功率