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

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