ZeroJudge 解題筆記：d269. 11579 - Triangle Trouble

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


ZeroJudge 題目連結：d269. 11579 - Triangle Trouble

解題想法

讀取一行測資，將 $n$ 個邊長由大到小排序，再依序讀取連續 3 個邊長 $a, b, c$，如果最長的邊 $a$ 大於等於較短的兩個邊 $b, c$ 加總，無法組成三角形；反之，用海龍公式計算三角形面積。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    T = int(data[0])  # T 組測資
    ptr = 1
    while ptr < len(data):  # 執行 T 次
        n = int(data[ptr])  # 首項是邊的數量
        ptr += 1
        edges = sorted(map(float, data[ptr:ptr+n]), reverse=True)  # 邊長，由大到小排序
        ptr += n
        imax = 0.0  # 最大面積
        for i in range(n-2):  # 依序讀取邊長，每次 3 項
            a, b, c = edges[i:i+3]  # 邊長
            if a >= b + c:  # 最長的邊大於等於另外兩個邊相加
                continue  # 無法組成三角形，找下一組
            s = (a + b + c) * 0.5  # 用海龍公式求三角形面積
            area = (s * (s-a) * (s-b) * (s-c))**0.5
            if area > imax: imax = area  # 更新最大值
        result.append(f"{imax:.2f}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d261. 11000 - Bee

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


ZeroJudge 題目連結：d261. 11000 - Bee

解題想法

只有第一隻母蜂不會死，剩下的公蜂、母蜂每年結束都會死去。第 $i$ 年的母蜂數量等於 $1$ 加上第 $i-1$ 年的公蜂數量，第 $i$ 年的公蜂數量等於第 $i-1$ 年的公蜂加母蜂數量。

Python 程式碼

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

def solve():
    import sys

    maxn = 50
    f = [0]*(maxn + 1)
    m = [0]*(maxn + 1)
    f[0] = 1
    for i in range(1, maxn + 1):
        f[i] = 1 + m[i-1]
        m[i] = f[i-1] + m[i-1]

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

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d260. 11455 - Behold my quadrangle

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


ZeroJudge 題目連結：d260. 11455 - Behold my quadrangle

解題想法

先將 4 個邊排序後分別存入 $a, b, c, d$，如果 $a, b, c, d$ 皆相等，輸出 square；如果 $a$ 等於 $b$ 且 $c$ 等於 $d$，輸出 rectangle；如果 $a + b + c > d$，輸出 quadrangle；其它狀況輸出 banana。

Python 程式碼

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

T = int(input())
for _ in range(T):
    a, b, c, d = sorted(map(int, input().split()))
    if a == b == c == d:
        print("square")
    elif a == b and c == d:
        print("rectangle")
    elif a + b + c > d:
        print("quadrangle")
    else:
        print("banana")

如果是多筆測資可以改成這樣，使用時間約為 15 ms，記憶體約為 8.2 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        T = int(data[ptr])
        ptr += 1
        for _ in range(T):
            a, b, c, d = sorted(map(int, data[ptr:ptr+4]))
            ptr += 4
            if a == b == c == d:
                result.append("square\n")
            elif a == b and c == d:
                result.append("rectangle\n")
            elif a + b + c > d:
                result.append("quadrangle\n")
            else:
                result.append("banana\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d258. 11313 - Gourmet Games

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


ZeroJudge 題目連結：d258. 11313 - Gourmet Games

解題想法

用一個 while 迴圈，當 $n \geq m$ 時繼續執行，每次執行時將集數 $cnt$ 加上 n//m，$n$ 改為 n = n//m + n%m。由於最後只能有一個優勝者，$n$ 最後必須等於 1，如果 $n$ 等於 1 輸出 $cnt$，反之輸出 cannot do this。

Python 程式碼

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

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    cnt = 0
    while n >= m:
        cnt += n//m
        n = n//m + n%m
    print(cnt if n == 1 else "cannot do this")

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split() 
    t = int(data[0])
    ptr = 1
    for _ in range(t):  # 只能跑 t 次，否則會吃 OLE
        n = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        cnt = 0
        while n >= m:
            cnt += n//m
            n = n//m + n%m
        if n == 1: result.append(f"{cnt:d}\n")
        else: result.append("cannot do this\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d256. 11388 - GCD LCM

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


ZeroJudge 題目連結：d256. 11388 - GCD LCM

解題想法

假設兩個數字 $a, b$ 的最大公因數 $G = GCD(a, b)$，最小公倍數 $L = LCM(a, b)$，而且題目要求「如果有多組解，輸出 $a$ 最小的一組」，答案就是 $a = G$，$b = L$，因為 $a$ 之中不能有 $G$ 以外大於 $1$ 的因數。如果 $L$ 不能被 $G$ 整除，則輸出 $-1$。

Python 程式碼

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

T = int(input())
for _ in range(T):
    G, L = map(int, input().split())
    if L%G != 0: print("-1")
    else: print(G, L)

C++ 程式碼

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

#include <cstdio>

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        int G, L; scanf("%d %d", &G, &L);
        if (L%G != 0) puts("-1");
        else printf("%d %d\n", G, L);
    }
    return 0;
}

ZeroJudge 解題筆記：d253. 00674 - Coin Change

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


ZeroJudge 題目連結：d253. 00674 - Coin Change

解題想法

每種面額的硬幣使用數量不限，是無限背包問題，用動態規畫解題，假設 $dp[i]$ 是總金額 i 的組合數，初始值是 $dp[0] = 1$。先建表，計算總金額 0 到 7489 的組合數，再讀取測資、查表、輸出答案。

Python 程式碼

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

def solve():
    import sys

    coins = (1, 5, 10, 25, 50)  # 硬幣面額
    maxn = 7489
    dp = [0]*(maxn + 1)  # 總金額 i 有幾種組合
    dp[0] = 1  # 初始值，金額 0 只有 1 種組合
    for coin in coins:  # 無限背包問題
        for i in range(coin, maxn + 1):
            dp[i] += dp[i - coin]
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    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 解題筆記：d242. 00481 - What Goes Up

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


ZeroJudge 題目連結：d242. 00481 - What Goes Up

解題想法

這題要找最長遞增子序列 (longest increasing subsequence, LIS) 的內容，網路上有不少的教學。我是記錄目前 lis 對應的字元索引值，最後再將這些索引值對應的字元組成字串，反序後輸出。

Python 程式碼

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

def get_lis(nums):
    if not nums: return []
    n = len(nums)
    prev = [-1]*n
    tails = []
    for i, num in enumerate(nums):
        low, high = 0, len(tails)-1
        while low <= high:
            mid = (high - low) // 2 + low
            if num > nums[tails[mid]]: low = mid + 1
            else: high = mid - 1
        if low == len(tails): tails.append(i)
        else: tails[low] = i
        if low > 0: prev[i] = tails[low-1]
    lis = []
    curr = tails[-1]
    while curr != -1:
        lis.append(nums[curr])
        curr = prev[curr]
    return lis[::-1]

def solve():
    import sys
    
    result = []
    arr = list(map(int, sys.stdin.read().split()))
    lis = get_lis(arr)
    result.append(f"{len(lis):d}\n-\n")
    for v in lis: result.append(f"{v:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d224. 11296 - Counting Solutions to an Integral Equation

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


ZeroJudge 題目連結：d224. 11296 - Counting Solutions to an Integral Equation

解題想法

這題可以用公式解或是動態規畫。 $$ x + 2y + 2z = n ~\Rightarrow~ x = n - 2(y + z) = n - 2k $$ 因為題目要求 $x, y, z$ 為 0 或正整數，因此 $$ y + z = k ~\Rightarrow~ 0 \leq k \leq \left \lfloor \frac{n}{2} \right \rfloor = m $$ 符合條件的 $(y, z)$ 為 $(0, k), (1, k-1), \dots, (k, 0)$，共有 $k + 1$ 組，因此所有的解數量為 $$ \sum_{k=0}^{m} (k+1) = 0 + 1 + 2 + \dots + (m+1) = \frac{(m+1)(m+2)}{2} $$ 如果用 $dp[i]$ 代表 $x + 2y + 2z = i$ 時的解數量，起始條件為 $dp[0] = 1$。$x = 0, 1, 2, \dots, n$，當 $x$ 加 1 時，解的數量會更新為 $$ dp[i] = dp[i] + dp[i-1] $$ $y, z = 0, 1, 2, \dots, \left \lfloor \frac{n}{2} \right \rfloor$，則 $y$ 或 $z$ 加 1 時，解的數量會更新為 $$ dp[i] = dp[i] + dp[i-2] $$

Python 程式碼

公式解，使用時間約為 40 ms，記憶體約為 11.4 MB，通過測試。

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

動態規畫，使用時間約為 0.4 s，記憶體約為 63.6 MB，通過測試。

def solve():
    import sys

    maxn = 1000000
    dp = [0]*(maxn+1)
    dp[0] = 1  # i = 0，1 組解
    for i in range(1, maxn+1):  # 加入 x
        dp[i] += dp[i-1]
    for i in range(2, maxn+1):  # 加入 y
        dp[i] += dp[i-2]
    for i in range(2, maxn+1):  # 加入 z
        dp[i] += dp[i-2]

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    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 解題筆記：d018. 字串讀取練習

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


ZeroJudge 題目連結：d018. 字串讀取練習

解題想法

這題的輸出格式對 Python 使用者而言很麻煩，答案如果是小數，輸出的位數不固定，而且要捨去後面的0；如果是整數則連小數點都不能輸出。後來是將相減的結果先轉成字串，再用 rstrip('0') 去除後方的 0，再接著用 rstrip('.') 去除後方的小數點，如果答案是小數，此時字串最後面是數字，小數點不會被刪除。

Python 程式碼

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

def format_float(num):
    return f"{num:.6f}".rstrip('0').rstrip('.')

while True:
    try:
        data = input().split()
        even, odd = 0, 0
        for d in data:
            k, v = d.split(':')
            k = int(k)
            v = float(v)
            if k%2 == 0: even += v
            else: odd += v
        ans = format_float(odd - even)
        print(ans)
    except EOFError:
        break

ZeroJudge 解題筆記：c929. 蝸牛老師的點名單-續

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


ZeroJudge 題目連結：c929. 蝸牛老師的點名單-續

解題想法

這題如果用 Python 解題很快，只要先讀取分割用的字串，再將第二行字串用 split 代入第一行字串分割就好了。如果用 C++ 解題，則要用 getline 讀取整行字串，再依序檢查第二行字串的每個字元，找出分割用字串的索引值，再用 substr 取出子字串。

Python 程式碼

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

s = input()
for t in input().split(s):
    print(t)

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

s = input()  # 分割用的字串
t = input()  # 要被分割的字串
n = len(s)  # 字串長度
pre = 0  # 前一個分割點
idx = t.find(s)  # 從 t 之中找 s 的索引值
while idx != -1:  # -1 代表沒找到
    print(t[pre:idx])  # 印出分割後的子字串
    pre = idx + n  # 更新 pre
    idx = t.find(s, pre)  # 從 s[pre:] 找 t
if pre > 0: print(t[pre:])  # 最後一段
else: print(t)  # 沒有分割