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")  # 求電功率

ZeroJudge 解題筆記：c126. 00536 - Tree Recovery

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


ZeroJudge 題目連結：c126. 00536 - Tree Recovery

解題想法

這題需要知道二元樹的結構及走訪的順序。前序走訪的順序為父節點、左子節點、右子節點，中序走訪的順序為左子節點、父節點、右子節點，後序走訪的順序為左子節點、右子節點、父節點。因此，從測資中讀到的前序走訪資料開頭就是根節點，測資中的中序走訪資料左側為根節點的左子樹，右側為根節點的右子樹。依照這樣的原則設計從前序走訪、中序走訪資料建立後序走訪資料的函式。

Python 程式碼

用字串儲存二元樹走訪的資料，用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

def build_tree(preorder, inorder):
    if not preorder or not inorder: return ""  # 如果沒有資料，回傳空字串
    root = preorder[0]  # 前序走訪開頭為根節點
    root_idx = inorder.find(root)  # 找到中序走訪資料中根節點的索引值
    left_inorder = inorder[:root_idx]  # 中序走訪資料中左子樹資料
    right_inorder = inorder[root_idx+1:]  # 中序走訪資料中右子樹資料
    left_preorder = preorder[1:1+len(left_inorder)]  # 前序走訪資料中左子樹資料
    right_preorder = preorder[1+len(left_inorder):]  # 前序走訪資料中右子樹資料
    left_postorder = build_tree(left_preorder, left_inorder)  # 遞迴，找左子樹後序走訪資料
    right_postorder = build_tree(right_preorder, right_inorder)  # 遞迴，找右子樹後序走訪資料
    return left_postorder + right_postorder + root  # 組合成答案

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    result.append(f"{build_tree(*line.split())}\n")
sys.stdout.write("".join(result))

用串列儲存二元樹走訪的資料，用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

def build_tree(preorder, inorder):
    if not preorder or not inorder: return []  # 如果沒有資料，回傳空串列
    root = preorder[0]  # 前序走訪開頭為根節點
    root_idx = inorder.find(root)  # 找到中序走訪資料中根節點的索引值
    left_inorder = inorder[:root_idx]  # 中序走訪資料中左子樹資料
    right_inorder = inorder[root_idx+1:]  # 中序走訪資料中右子樹資料
    left_preorder = preorder[1:1+len(left_inorder)]  # 前序走訪資料中左子樹資料
    right_preorder = preorder[1+len(left_inorder):]  # 前序走訪資料中右子樹資料
    left_postorder = build_tree(left_preorder, left_inorder)  # 遞迴，找左子樹後序走訪資料
    right_postorder = build_tree(right_preorder, right_inorder)  # 遞迴，找右子樹後序走訪資料
    return left_postorder + right_postorder + [root]  # 組合成答案

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    ans = "".join(build_tree(*line.split()))
    result.append(f"{ans}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c125. 00534 - Frogger

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


ZeroJudge 題目連結：c125. 00534 - Frogger

解題想法

先讀取所有石頭的位置，計算任意兩個石頭之間的距離，存入二維陣列 $dist$ 之中，其中 $dist[i][j]$ 代表石頭 $i, j$ 之間的距離。 開一個陣列 $ans$，儲存到達第 $i$ 個石頭的路徑上單次跳躍距離最大值之中的最小值。接下來用一個最小優先佇列 $pq$，資料為 $(距離, 石頭索引值)$，代表到第 $i$ 顆石頭的路徑上最大的單次跳躍距離，距離最小的資料放上面。如果 $pq$ 還有資料，而且 $pq$ 最上面的石頭索引值不等於 $1$（終點），while 迴圈繼續執行。每次取出 $pq$ 最上方的資料，目前的距離 $curr$、石頭索引值 $u$，掃過石頭 $v ~(0 \leq v \leq n-1)$，取 $curr$ 與 $dist[u][v]$ 較大者為新的距離 $new_{dis}$，如果 $new_{dis} < ans[v]$，更新 $ans[v]$，並將 ${new_{dis}, v}$ 加入 $pq$。

Python 程式碼

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

import sys, heapq

def cal_dis(a, b):  # 計算距離用的函式
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)  # n 顆石頭
    if n == 0: break  # 中止迴圈的條件
    ca += 1
    if ca > 1: result.append("\n")  # 從第 2 筆測資開始要先空一行
    stones = [tuple(map(float, sys.stdin.readline().split())) for _ in range(n)]  # 石頭位置
    dist = [[0.0]*n for _ in range(n)]  # 石頭之間的距離
    for i in range(n):
        for j in range(n):
            if i == j: continue
            d = cal_dis(stones[i], stones[j])
            dist[i][j] = d
            dist[j][i] = d
    ans = [float('inf')]*n  # 到達第 i 個石頭的路徑上單次跳躍距離最大值之中的最小值
    pq = [(0.0, 0)]  #  (距離, 石頭索引值)，代表到第 $i$ 顆石頭的路徑上最大的單次跳躍距離
    while pq and pq[0][1] != 1:  # pq 還有資料，而且 pq 最上面的石頭索引值不等於 1
        curr, u = heapq.heappop(pq)  # 取出 pq 最上方的資料，目前的距離 curr、石頭索引值 u
        for v in range(n):  # 掃過石頭 v = 0 ~ n-1
            if v == u: continue  # 同一顆石頭，跳過
            new_dis = max(curr, dist[u][v])  # 新的距離
            if new_dis < ans[v]:  # 新的最小值
                ans[v] = new_dis  # 更新 ans[v]
                heapq.heappush(pq, (new_dis, v))  # (new_dis, v) 加入 pq
    result.append(f"Scenario #{ca:d}\nFrog Distance = {ans[1]:.3f}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c124. 00532 - Dungeon Master

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


ZeroJudge 題目連結：c124. 00532 - Dungeon Master

解題想法

這題可以用一個三維陣列儲存地圖及步數，0 代表起點、障礙物、邊界，-1 代表還沒有走過的格子，另外在地圖的邊緣加一圈 0 當作哨兵，避免在用 BFS 找最短路徑時出界。 由於測資中有一些多餘的空行，用 Python 解題時可以用 sys.stdin.read().split() 一次讀取所有測資、拆開、存入串列，這樣可以很方便地避開空行。

Python 程式碼

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

import sys
from collections import deque

result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    L, R, C = map(int, data[ptr:ptr+3])  # 迷宮的高、深、寬，對應 z、y、x 座標
    ptr += 3
    if L == 0 and R == 0 and C == 0: break  # 中止迴圈的條件
    sx, sy, sz, ex, ey, ez = 0, 0, 0, 0, 0, 0  # 起點、終點座標
    maze = [[[0]*(C+1) for _ in range(R+1)] for _ in range(L+1)]  # 迷宮，0 是起點、邊界、石頭
    """ 讀取地圖資料，-1 代表還沒有走過 """
    for z in range(L):  # 依序讀取 L 層地圖
        for y in range(R):  # 讀取 R 列地圖
            line = data[ptr]
            ptr += 1
            for x, ch in enumerate(line):  # 依序讀取此列的字元
                if ch == 'S':  # 起點，步數為 0
                    sz, sy, sx = z, y, x
                    maze[z][y][x] = 0
                elif ch == 'E':  # 終點，-1 代表還沒有走過
                    ez, ey, ex = z, y, x
                    maze[z][y][x] = -1
                elif ch == '.':  # 走道，-1 代表還沒有走過
                    maze[z][y][x] = -1
    """ BFS 找最短路徑 """
    que = deque([(sz, sy, sx)])  # que 放入起點
    find_ans = False  # 是否有解
    while que and not find_ans:  # 如果 que 還有資料而且還沒有找到答案，繼續執行
        z, y, x = que.popleft()  # 取出 que 最前面的資料
        for dz, dy, dx in ((1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)):  # 6 方位檢查
            nz, ny, nx = z+dz, y+dy, x+dx  # 要檢查 (nz, ny, nx)
            if maze[nz][ny][nx] != -1: continue  # 如果此格不是 -1，找下一格
            maze[nz][ny][nx] = maze[z][y][x] + 1  # 設定此格步數
            if nz == ez and ny == ey and nx == ex:  # 走到終點，找到答案，中止迴圈
                find_ans = True
                break
            que.append((nz, ny, nx))  # (nz, ny, nx) 加入 que
    """ End of BFS """
    if find_ans:
        result.append(f"Escaped in {maze[ez][ey][ex]:d} minute(s).\n")
    else:
        result.append("Trapped!\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c122. 00443 - Humble Numbers

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


ZeroJudge 題目連結：c122. 00443 - Humble Numbers

解題想法

用陣列 nums 儲存 humble number，再用另外 4 個變數 i2, i3, i5, i7 記錄 nums 之中前一個 2、3、5、7 倍數對應的索引值，每次更新時計算這 4 個索引值分別乘以 2、3、5、7 的值，取其中的最小值加入 nums 之中並更新對應的索引值，當 nums 的長度等於 5842 就可以停止運算。接下來讀取測資，從 nums 之中找答案。

Python 程式碼

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

import sys

# 計算前 5842 個Humble Number
nums = [0, 1]  # 配合編號，開頭多一個 0
i2, i3, i5, i7 = 1, 1, 1, 1  # 2, 3, 5, 7 倍數基底的索引值
while len(nums) <= 5842:  # 當 nums 長度小於、等於 5842 時繼續執行
    nxt2 = nums[i2] * 2  # 下一個 2 的倍數
    nxt3 = nums[i3] * 3  # 下一個 3 的倍數
    nxt5 = nums[i5] * 5  # 下一個 5 的倍數
    nxt7 = nums[i7] * 7  # 下一個 7 的倍數
    nxt_num = min(nxt2, nxt3, nxt5, nxt7)  # 取以上 4 個數之中的最小值加入 nums
    nums.append(nxt_num)
    if nxt_num == nxt2: i2 += 1  # 如果是 2 的倍數更新 i2
    if nxt_num == nxt3: i3 += 1  # 如果是 3 的倍數更新 i3
    if nxt_num == nxt5: i5 += 1  # 如果是 5 的倍數更新 i5
    if nxt_num == nxt7: i7 += 1  # 如果是 7 的倍數更新 i7

def last(x):  # 數字後面接的英文
     two = x%100  # 最後兩位數
     one = x%10  # 最後一位數
     if two == 11 or two == 12 or two == 13: return "th"  # 最後兩位數是 11、12、13，回傳 th
     if one == 1: return "st"  # 最後一位數是 1，回傳 st
     if one == 2: return "nd"  # 最後一位數是 2，回傳 nd
     if one == 3: return "rd"  # 最後一位數是 3，回傳 rd
     return "th"  # 其它，回傳 th

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    result.append(f"The {n:d}{last(n):s} humble number is {nums[n]:d}.\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c121. 00495 - Fibonacci Freeze

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


ZeroJudge 題目連結：c121. 00495 - Fibonacci Freeze

解題想法

由於題目要求計算到費氏數列第 5000 項，需要用到大數加法，如果用 Python 解題可以直接算，如果用 C++ 則要自己寫大數加法的函式。

Python 程式碼

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

import sys

fib = [0]*5001
fib[1] = 1
for i in range(2, 5001):
    fib[i] = fib[i-1] + fib[i-2]

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    print(f"The Fibonacci number for {n:d} is {fib[n]:d}")

ZeroJudge 解題筆記：c117. 00439 - Knight Moves

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


ZeroJudge 題目連結：c117. 00439 - Knight Moves

解題想法

為了便於計算，會將棋盤的座標改成 0-indexed。用一個二維串列記錄從起點走到每一格的步數，預設值 -1 代表未走訪，起點步數為 0，用 BFS 找步數。

Python 程式碼

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

import sys
from collections import deque

result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    start, end = data[ptr:ptr+2]  # 起點，終點
    ptr += 2
    if start == end:  # 特例，不需要移動
        result.append(f"To get from {start:s} to {end:s} takes 0 knight moves.\n")
        continue
    grid = [[-1]*8 for _ in range(8)]  # 棋盤上走到每格的步數，-1 代表還沒有走過
    c1 = ord(start[0]) - ord('a')  # 起點座標 (r1, c1)，改成 0-index
    r1 = int(start[1]) - 1
    c2 = ord(end[0]) - ord('a')  # 終點座標 (r2, c2)，改成 0-index
    r2 = int(end[1]) - 1
    grid[r1][c1] = 0  # 起點步數 0
    que = deque([(r1, c1)])  # 待走訪佇列
    find_ans = False  # 是否找到答案
    while que and not find_ans:  # BFS，如果 que 還有資料而且還沒有找到答案，繼續執行
        r, c = que.popleft()  # 目前所在的位置 (r, c)
        for dr, dc in ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)):  # 八方位檢查
            nr, nc = r+dr, c+dc  # 正在檢查 (nr, nc)
            if 0 <= nr < 8 and 0 <= nc < 8 and grid[nr][nc] == -1:  # 未出界也未走訪
                grid[nr][nc] = grid[r][c] + 1  # 更新 (nr, nc) 的步數
                if nr == r2 and nc == c2:  # 走到終點
                    find_ans = True  # 已經找到答案
                    break  # 中止迴圈
                que.append((nr, nc))  # 將 (nr, nc) 加入 que
    result.append(f"To get from {start:s} to {end:s} takes {grid[r2][c2]:d} knight moves.\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c116. 00438 - The Circumference of the Circle

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


ZeroJudge 題目連結：c116. 00438 - The Circumference of the Circle

解題想法

這題考數學。假設三角形 $ABC$，三個角的對邊長度分別為 $a, b, c$，三角形面積為 $$ area = \frac{1}{2}ab \sin C $$ 假設外接圓半徑為 $R$，由正弦定理可得 $$ \frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = 2R ~\Rightarrow~ \sin C = \frac{c}{2R} $$ 再代回面積公式 $$ area = \frac{1}{2} ab \cdot \frac{c}{2R} = \frac{abc}{4R} ~\Rightarrow~ R = \frac{abc}{4 area} $$ 其中三角形面積可以用海龍公式求解 $$ area = \sqrt{s(s-a)(s-b)(s-c)} ~~~~~ s = \frac{a+b+c}{2} $$ 最後在計算圓周長 $2 \pi R$ 時，$\pi$ 要用題目給的 $3.141592653589793$。

Python 程式碼

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

import sys, math

for line in sys.stdin:
    x1, y1, x2, y2, x3, y3 = map(float, line.split())
    a = ((x1 - x2)**2 + (y1 - y2)**2)**0.5
    b = ((x2 - x3)**2 + (y2 - y3)**2)**0.5
    c = ((x3 - x1)**2 + (y3 - y1)**2)**0.5
    s = (a+b+c) / 2
    area = (s*(s-a)*(s-b)*(s-c))**0.5
    R = a*b*c/(4*area)
    print(f"{2*3.141592653589793*R:.2f}")

ZeroJudge 解題筆記：c115. 00437 - The Tower of Babylon

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


ZeroJudge 題目連結：c115. 00437 - The Tower of Babylon

解題想法

因為方塊可以旋轉，在讀取方塊邊長時，先將邊長排序，假設邊長依序為 $x, y, z$，將三種邊長排列方式都存入串列 blocks 之中。接下來將 blocks 依照長、寬由大到小排序，用 dp 計算最大高度。

Python 程式碼

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

import sys

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)  # 積木數量
    if n == 0: break  # 中止迴圈條件
    ca += 1
    blocks = []  # 可能的積木尺寸
    for _ in range(n):  # 讀取 n 行資料
        x, y, z = sorted(map(int, sys.stdin.readline().split()))  # x >= y >= z
        blocks.append((z, y, x))  # 取長、寬較大者放前面
        blocks.append((z, x, y))
        blocks.append((y, x, z))
    blocks.sort(key = lambda b : (b[0], b[1]), reverse=True)  # 依照長、寬由大到小排序
    m = len(blocks)  # 可用的積木數量
    dp = [0]*m  # 以第 i 塊為最上方的積木，累計的最大高度
    for i in range(m):  # 依序掃過第 0 ~ m-1 塊積木
        xi, yi, zi = blocks[i]  # 第 i 塊的 x、y、z 大小
        dp[i] = zi  # 如果只放第 i 塊，高度為 zi
        for j in range(i):  # 依序掃過第 0 ~ i-1 塊積木
            xj, yj = blocks[j][0], blocks[j][1]
            if xj > xi and yj > yi:  # 第 i 塊可以放在第 j 塊上面
                dp[i] = max(dp[i], dp[j] + zi)  # 取第 i 塊目前的高度、第 j 塊的高度加上 zi 較大者
    result.append(f"Case {ca:d}: maximum height = {max(dp):d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c114. 00409 - Excuses, Excuses!

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


ZeroJudge 題目連結：c114. 00409 - Excuses, Excuses!

解題想法

我是用集合儲存關鍵字，用串列儲存答案。讀取一行藉口之後，計算這行之中的關鍵字數量，如果數量是新的最大值，將儲存答案的串列清空、只存入這一行；如果數量等於目前的最大值，這一行加入儲存答案的串列之中。

Python 程式碼

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

import sys

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    ca += 1
    if ca > 1: result.append("\n")
    result.append(f"Excuse Set #{ca:d}\n")
    n, m = map(int, line.split())  # n 個關鍵字，m 行藉口
    keyword = {sys.stdin.readline().strip() for _ in range(n)}  # 關鍵字集合
    worst = []  # 最爛的藉口
    imax = 0  # 最爛的藉口關鍵字數量
    for _ in range(m):  # 讀取 m 行
        excuse = sys.stdin.readline().rstrip()  # 藉口
        cnt = 0  # 這個藉口的關鍵字數量
        word = []  # 暫存字母用的串列
        for c in excuse:  # 依序讀取字元 c
            if c.isalpha():  # 如果 c 是字母
                word.append(c.lower())  # 轉成小寫加入 word
            else:  # 反之，將 word 組成字串，如果是關鍵字，cnt 加 1
                if "".join(word) in keyword: cnt += 1
                word.clear()  # 漬空 word
        if "".join(word) in keyword: cnt += 1  # 最後要再結算一次
        word.clear()  # 漬空 word
        if cnt > imax:  # 如果 cnt 大於 imax
            imax = cnt  # 更新 imax
            worst = [excuse]  # 找到新的最爛藉口
        elif cnt == imax:  # 如果 cnt 等於 imax
            worst.append(excuse)  # 最爛藉口加一
    for s in worst: result.append(f"{s}\n")
sys.stdout.write("".join(result))