ZeroJudge 解題筆記：d087. 00107 - The Cat in the Hat

作者：王一哲
日期：2026年4月5日


ZeroJudge 題目連結：d087. 00107 - The Cat in the Hat

解題想法

寫一個自訂函式 check，輸入起始高度 h、倍率 n，計算總數、高度為 1 的數量、總高度。用 for 迴圈依序測試倍率 1 ~ H-1，用 check 檢查代入的倍率高度為1的貓的數目是否符合測資。

Python 程式碼

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

import sys

def check(h, n):  # 輸入起始高度、倍率
    total, curr, hsum = 1, 1, h  # 總數，目前的數量，總高度
    h //= 1+n  # 新的高度
    while h >= 1:  # 如果 h 大於等於 1 繼續執行
        curr *= n  # 更新數量為 n 倍
        total += curr  # 更新總數
        hsum += curr*h  # 更新總高度
        h //= 1+n  # 更新高度
    return total, curr, hsum  # 回傳總數、高度為 1 的數量、總高度
    
result = []
lines = sys.stdin.readlines()
for line in lines:
    H, M = map(int, line.split())  # 起始高度、高度為 1 的數量
    if H == 0 and M == 0: break  # 如果 H 與 M 皆等於 0，中止迴圈
    total, imin, hsum = H, 1, H  # 試算結果，總數、高度為 1 的數量、總高度
    for i in range(1, H):  # 測試倍率 1 ~ H-1
        total, imin, hsum = check(H, i)  # 回傳測試結果
        if imin == M: break  # 如果 imin 等於 M，找到答案，中止迴圈
    result.append(f"{total-imin:d} {hsum:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d057. 11494 - Queen

作者：王一哲
日期：2026年4月4日


ZeroJudge 題目連結：d057. 11494 - Queen

解題想法

可能的步數有 3 種：

1. 不需要移動，回傳 0。
2. 在同一列、同一欄、斜直線上，回傳 1。
3. 其它狀況，走 2 步一定會走到，回傳 2。

Python 程式碼

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

import sys

def find_step(x1, y1, x2, y2):  # 輸入起點、終點找步數
    if x1 == x2 and y1 == y2: return 0  # 不需要移動，回傳 0
    if x1 == x2 or y1 == y2: return 1  # 在同一欄或列，回傳 1
    if x2 - x1 == y2 - y1:  # 右上、左下斜直線
        dx = x2 - x1  # x 方向位移
        dy = y2 - y1  # y 方向位移
        if 1 <= x1 + dy <= 8 and 1 <= y1 + dx <= 8:  # 沒出界
            return 1  # 回傳 1
    if x2 - x1 == y1 - y2:  # 左上、右下斜直線
        dx = x2 - x1  # x 方向位移
        dy = y2 - y1  # y 方向位移
        if 1 <= x1 - dy <= 8 and 1 <= y1 - dx <= 8:  # 沒出界
            return 1  # 回傳 1
    # 其它狀況，最多只要水平、垂直各走一步，回傳 2
    return 2

result = []
lines = sys.stdin.readlines()
for line in lines:
    if line.strip() == "0 0 0 0": break
    step = find_step(*map(int, line.split()))
    result.append(f"{step:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d056. 10013 - Super long sums

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


ZeroJudge 題目連結：d056. 10013 - Super long sums

解題想法

這題如果用 Python 解題，最好用串列 a、b 儲存超長整數，再用另一個串列 ans 儲存計算結，串列資料格式為字串。運算時由 a、b 最後面住前讀取資料，將計算結果用字串格式存入 ans，輸出答案時將 ans 反序輸出。如果用 C++ 解題，可以用字串或 vector 儲存超長整數，用字串格式好像速度快一點。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        for _ in range(n):
            m = int(data[ptr])
            ptr += 1
            a, b = [], []
            for _ in range(m):
                c, d = map(int, data[ptr:ptr+2])
                ptr += 2
                a.append(c)
                b.append(d)
            ans = []
            carry = 0
            for i, j in zip(a[::-1], b[::-1]):
                k = int(i) + int(j) + carry
                if k >= 10:
                    carry = 1
                    ans.append(f"{k%10}")
                else:
                    carry = 0
                    ans.append(f"{k}")
            if carry == 1: ans.append("1")
            res = "".join(ans[::-1])
            if not result: result.append(f"{res}\n")
            else: result.append(f"\n{res}\n")
        sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d055. 11437 - Triangle Fun

作者：王一哲
日期：2026年4月2日


ZeroJudge 題目連結：d055. 11437 - Triangle Fun

解題想法

數學題。分點公式是高中數學課程內容，假設要在兩個點 $A$、$B$ 找到另一個點 $C$，使 $\overline{AB} : \overline{CB} = m : n$，則 $$ C = \frac{n}{m+n} A + \frac{m}{m+n} B $$ 題目的提示中有由寫三角形三個頂點求面積的公式 $$ area = \frac{1}{2} \times \left | A_x B_y - A_y B_x + B_x C_y - C_x B_y + C_x A_y - C_y A_x \right | $$ 還要自己推導，由兩條不平行的直線端點求交點座標的公式。假設 $(x_1, y_1), (x_2, y_2)$ 是直線 $y = ax + b$ 的端點座標，$(x_3, y_3), (x_4, y_4)$ 是直線 $y = a'x + b'$ 的端點座標。將 $(x_1, y_1), (x_2, y_2)$ 代入 $y = ax + b$ 可得 $$ y_1 = ax_1 + b ~~~~~ y_2 = ax_2 + b $$ 利用加減消去法可得 $$ a = \frac{y_1 - y_2}{x_1 - x_2} ~~~~~ b = \frac{x_2 y_1 - x_1 y_2}{x_2 - x_1} $$ 同理可得 $$ a' = \frac{y_3 - y_4}{x_3 - x_4} ~~~~~ b' = \frac{x_4 y_3 - x_3 y_4}{x_4 - x_3} $$ 再求 $y = ax + b$ 與 $y = a'x + b'$ 的交點 $(x, y)$，利用加減消去法可得 $$ x = \frac{b' - b}{a - a'} ~~~~~ y = \frac{a'b - ab'}{a' - a} $$

Python 程式碼

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

def find_point(ax, ay, bx, by):
    """
    代入直線的兩個端點 A、B
    求與 A、B 距離比為 1:2 的座標
    """
    cx = (2*ax + bx) / 3
    cy = (2*ay + by) / 3
    return cx, cy

def intersection(x1, y1, x2, y2, x3, y3, x4, y4):
    """
    x1, y1, x2, y2 是一條直線 y = ax + b 的兩個端點
    x3, y3, x4, y5 是另一條直線 y = a'x + b' 的兩個端點
    兩條直線不平行，求直線的交點
    """
    a = (y1 - y2) / (x1 - x2)
    b = (x2*y1 - x1*y2) / (x2 - x1)
    ap = (y3 - y4) / (x3 - x4)
    bp = (x4*y3 - x3*y4) / (x4 - x3)
    x = (bp - b) / (a - ap)
    y = (ap*b - a*bp) / (ap - a)
    return x, y

def find_area(ax, ay, bx, by, cx, cy):
    """
    代入三角形 ABC 的三的頂點座標求面積
    """
    return abs(ax*by - ay*bx + bx*cy - by*cx + cx*ay - cy*ax)/2

t = int(input())
for _ in range(t):
    Ax, Ay, Bx, By, Cx, Cy = map(float, input().split())
    Dx, Dy = find_point(Bx, By, Cx, Cy)
    Ex, Ey = find_point(Cx, Cy, Ax, Ay)
    Fx, Fy = find_point(Ax, Ay, Bx, By)
    Px, Py = intersection(Bx, By, Ex, Ey, Ax, Ay, Dx, Dy)
    Qx, Qy = intersection(Bx, By, Ex, Ey, Cx, Cy, Fx, Fy)
    Rx, Ry = intersection(Ax, Ay, Dx, Dy, Cx, Cy, Fx, Fy)
    area = find_area(Px, Py, Qx, Qy, Rx, Ry)
    print(f"{round(area):d}")

ZeroJudge 解題筆記：d054. 11310 - DELIVERY DEBACLE

作者：王一哲
日期：2026年4月1日


ZeroJudge 題目連結：d054. 11310 - DELIVERY DEBACLE

解題想法

這題考動態規畫，最難的地方是找遞迴關係式。$dp[n]$ 代表長度為 $n$ 時的排列方式數量，先列出前幾項：

1. $dp[0] = 1$，沒有任何的蛋糕，只有 1 種方式。
2. $dp[1] = 1$，只能放 2 個方形蛋糕，只有 1 種方式。
3. $dp[2] = 4 ＋ 1 ＝ 5$，用 1 個 L 形蛋糕及 1 個方形蛋糕佔據其中 4 格，再用 2 個方形蛋糕佔據剩下的 2 格，因為 L 形蛋糕的組合可以旋轉，有 4 種方式；也可以用 6 個方形蛋糕填滿 6 格，1 種方式；加起來共有 5 種方式。

$n = 3$ 開始會出現另一種排列方式，用 2 個 L 形蛋糕佔據其中 6 格，有以下 2 種方式

OOX     OXX
OXX     OOX

因此 $dp[3]$ 的組成有：

1. $dp[2] = 5$，用 2 個方形蛋糕佔據最後 2 格。
2. $4 \times dp[1] = 4 \times 1 = 4$，用 1 個 L 形蛋糕及 1 個方形蛋糕佔據最後 4 格，因為這個組合可以旋轉，要乘以 4。
3. $2 \times dp[0] = 2 \times 1 = 2$，用 2 個 L 形蛋糕佔據最後 6 格，這個組合有 2 種，要乘以 2。

$dp[3] = dp[2] + 4 \times dp[1] + 2 \times dp[0] = 5 + 4 \times 1 + 2 \times 1 = 11$ $dp[4]$ 的組成有：

1. $dp[3] = 11$，用 2 個方形蛋糕佔據最後 2 格。
2. $4 \times dp[2] = 4 \times 5 = 4$，用 1 個 L 形蛋糕及 1 個方形蛋糕佔據最後 4 格，因為這個組合可以旋轉，要乘以 4。
3. $2 \times dp[1] = 2 \times 1 = 2$，用 2 個 L 形蛋糕佔據最後 6 格，這個組合有 2 種，要乘以 2。
4. $dp[4] = dp[3] + 4 \times dp[2] + 2 \times dp[1] = 11 + 4 \times 5 + 2 \times 1 = 35$

遞迴關係式為 $$ dp[n] = dp[n-1] + 4 \times dp[n-2] + 2 \times dp[n-3] $$

Python 程式碼

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

def solve():
    import sys

    # 建表，n = 0 ~ 40
    dp = [1]*41
    dp[2] = 5
    for i in range(3, 41):
        dp[i] = dp[i-1] + 4*dp[i-2] + 2*dp[i-3]
    # 讀取資料並查表找答案
    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{dp[n]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d048. 11309 - Counting Chaos

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


ZeroJudge 題目連結：d048. 11309 - Counting Chaos

解題想法

寫一個自訂函式 check，檢查輸入的時間 h:m 是否為迴文。再寫另一個自訂函式 solve，輸入讀取的到字串 s，用 : 分割為 h:m，再換算成分鐘，由於答案範圍很小，用線性搜尋從目前的時間 curr 開始找答案即可。

Python 程式碼

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

def check(h, m):  # 檢查 h:m 是否為迴文
    time = f"{h:02d}{m:02d}"  # 補 0 組成字串
    time = time.lstrip('0')  # 刪除前置 0
    return time == time[::-1]  # 是否為迴文

def solve(s):  # 輸入字串求解
    h, m = map(int, s.split(':'))  # 用 : 分割字串轉成整數
    curr = h*60 + m  # 現在的時刻，以分鐘為單位
    for _ in range(1, 1440):  # 線性搜尋找答案
        curr += 1  # 時間加 1 分鐘
        curr_h = curr//60%24  # 時
        curr_m = curr%60  # 分
        if check(curr_h, curr_m):  # 如果是迴文，回傳答案
            return f"{curr_h:02d}:{curr_m:02d}"
    return "00:00"  # 預設的回傳值，理論上用不到

n = int(input())
for _ in range(n):
    print(solve(input()))

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