ZeroJudge 解題筆記：c098. 00106 - Fermat vs. Pythagoras

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


ZeroJudge 題目連結：c098. 00106 - Fermat vs. Pythagoras

解題想法

這題困難之處在於找數學關係，不能用暴力法跑兩層迴圈，一定會超時。 畢氏三元組 (Pythagorean triples) 的定義為滿足 $x^2 + y^2 = z^2$ 的正整數為 $(x, y, z)$。原始畢氏三元組 (Primitive Pythagorean triples) 還要再加上 $x, y, z$ 互質的條件，也就是 $gcd(x, y, z) = 1$。需要用到的性質為 $$ x = m^2 - n^2, ~~~ y = 2mn, ~~~ z = m^2 + n^2 $$ 其中

• $m > n> 0$，且 $m, n$ 為整數。
• $m, n$ 互質，即 $gcd(m, n) = 1$
• $m - n$ 為奇數，即 $m, n$ 為一個奇數、一個偶數。

推導過程

直角三角形邊長 $x^2 + y^2 = z^2$，其中 $z$ 是斜邊。因為 $(x, y, z)$ 互質，不可能有 2 個以上的偶數，所以

• $x, z$ 是奇數
• $y$ 是偶數

假設 $y \equiv 2k$，其中 $k$ 為正整數，則 $$ x^2 + (2k)^2 = z^2 ~\Rightarrow~ x^2 + 4k^2 = z^2 ~\Rightarrow~ z^2 - x^2 = 4k^2 ~\Rightarrow~ (z+x)(z-x) = 4k^2 $$ 假設 $a = z-x, ~b = z+x$，因為 $z, x$ 是奇數，所以 $a, b$ 是偶數。假設 $a = 2p, ~b = 2q$，則 $$ 2p \cdot 2q = (2k)^2 ~\Rightarrow~ pq = k^2 $$ 因為 $x, z$ 互質，所以 $p, q$ 互質，為了符合 $pq = k^2$，$p, q$ 必須是平方數。 假設 $p = n^2,~ q = m^2$，由於 $$ a = z-x = 2p = 2n^2, ~~~ b = z+x = 2q = 2m^2 $$ 由 $a+b$ 可以解 $z$ $$ a+b = 2z ~\Rightarrow~ 2(m^2 + n^2) = 2z ~\Rightarrow~ z = m^2 + n^2 $$ $$ x = z - a = m^2 + n^2 - 2n^2 = m^2 - n^2 $$ $$ y = \sqrt{z^2 - x^2} = \sqrt{(m^2 + n^2)^2 - (m^2 - n^2)^2} = \sqrt{4m^2 n^2} = 2mn $$

Python 程式碼

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

import sys, math

def solve(maxn):
    status = [False]*(maxn+1)  # 0 ~ maxn 是否為畢氏三元組
    coprime = [0]*(maxn+1)  # 0 ~ maxn 互質三元組數量前綴和
    """
     計算 0 ~ maxn 之間的原始畢氏三元組與所有畢氏三元組數量
     依序檢查 m = 2 ~ sqrt(maxn), n = 1 ~ m-1
     如果 m-n 是奇數，m, n 互質，則 x = m^2 - n^2, y = 2mn, z = m^2 + n^2
     為原始畢氏三元組，再將 (x, y, z) 乘以整數倍，找其它的畢氏三元組
    """
    for m in range(2, int(maxn**0.5) + 1):
        for n in range(1, m):
            if (m-n)%2 == 1 and math.gcd(m, n) == 1:
                x, y, z = m*m - n*n, 2*m*n, m*m + n*n
                if z > maxn: continue  # z 超過上限，找下一組
                coprime[z] += 1  # z 對應的原始畢氏三元組數量加 1
                k = 1  # 原始畢氏三元組的 k 倍，如果 k > 1 為不互質的三元組
                while k*z <= maxn:  # 如果 k*z 還沒有超過上限繼續執行
                    status[k*x], status[k*y], status[k*z] = True, True, True
                    k += 1
    # coprime 改成前綴和
    for i in range(1, maxn+1):
        coprime[i] += coprime[i-1]
    # 0 ~ maxn 之間非畢氏三元組的數量前綴和
    non_member = [0]*(maxn+1)
    cnt = 0
    for i in range(1, maxn+1):
        if not status[i]: cnt += 1
        non_member[i] = cnt
    sys.stdout.write(f"{coprime[maxn]:d} {non_member[maxn]:d}\n")

for line in sys.stdin:
    solve(int(line))

ZeroJudge 解題筆記：c096. 00700 - Date Bugs

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


ZeroJudge 題目連結：c096. 00700 - Date Bugs

解題想法

我只有想到最暴力的作法，用集合 ans 儲存所有第一部電腦所有可能的年份，再依序計算其它電腦可能的年份存入集合 cand，取 ans 與 cand 的交集更新 ans。如果最後 ans 有資料，答案是 ans 之中的最小值；反之則輸出 **Unknown bugs detected.**。這個寫法不快，但是容易操作。

Python 程式碼

暴力解，使用時間約為 23 ms，記憶體約為 6 MB，通過測試。

import sys

ca = 0
maxy = 10000  # 答案上限為 9999
for line in sys.stdin:
    if line.rstrip() == "0": break;
    ca += 1
    if ca > 1: print()  # 如果不是第一筆測資，先印出空行
    n = int(line)  # 電腦數量
    ans = set()  # 第 1 部電腦可能對應的年份
    yi, ai, bi = map(int, sys.stdin.readline().split())  # 顯示年份 yi，於 bi 年出問題，出問題之後回到 ai
    di = bi - ai  # 從 bi 回到 ai 的差值
    for i in range(0, maxy-yi, di): ans.add(yi+i) # 計算可能的年份差
    for _ in range(n-1):  # 讀取 n-1 行資料
        cand = set()  # 第 2 ~ n 部電腦可能對應的年份
        y, a, b = map(int, sys.stdin.readline().split())  # 顯示年份 y，於 b 年出問題，出問題之後回到 a
        d = b - a  # 從 b 回到 a 的差值
        for i in range(0, maxy-y, d): cand.add(y+i)  # 計算可能的年份差
        ans.intersection_update(cand)  # 更新 ans
    print(f"Case #{ca:d}:")
    if ans:  # 如果有交集，印出 ans 之中的最小值
        print(f"The actual year is {min(ans):d}.")
    else:  # 反之，印出 Unknown bugs detected.
        print("Unknown bugs detected.")

ZeroJudge 解題筆記：c094. 00661 - Blowing Fuses

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


ZeroJudge 題目連結：c094. 00661 - Blowing Fuses

解題想法

用陣列記錄每個電器是否開啟，依序讀取操作的電器編號，更新電器使用狀態及總電流。用一個布林值記錄是否已經燒掉，如果總電流過大標記為 True。

Python 程式碼

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

import sys

ca = 0  # 第幾次測試
for line in sys.stdin:
    n, m, c = map(int, line.split())  # n 個電器，m 次操作，最大電流 c
    if n == 0 and m == 0 and c == 0: break  # 中止迴圈的條件
    ca += 1  # ca 加 1
    if ca > 1: print()  # 如果不是第 1 次測試，先印出空白列
    current = [0] + [int(sys.stdin.readline()) for _ in range(n)]  # 讀取 n 個電器的電流，開頭加 0
    blown = False  # 是否已燒掉
    curr, imax = 0, 0  # 目前的電流，電流最大值
    turn_on = [False]*(n+1)  # 電器狀態，預設為關閉
    for _ in range(m):  # 讀取 m 次操作
        idx = int(sys.stdin.readline())  # 電器編號
        if blown: continue  # 如果已燒掉，繼續讀完剩下的操作
        turn_on[idx] = not turn_on[idx]  # 更新電器的狀態
        if turn_on[idx]: curr += current[idx]  # 如果開啟，加上這個電器的電流
        else: curr -= current[idx]  # 如果關閉，減去這個電器的電流
        if curr > c: blown = True  # 如果 curr 大於 c，已燒掉
        else: imax = max(imax, curr)  # 反之，更新最大電流
    print(f"Sequence {ca:d}")  # 印出答案
    if blown:
        print("Fuse was blown.")
    else:
        print("Fuse was not blown.")
        print(f"Maximal power consumption was {imax:d} amperes.")

ZeroJudge 解題筆記：c093. 00608 - Counterfeit Dollar

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


ZeroJudge 題目連結：c093. 00608 - Counterfeit Dollar

解題想法

這題的困難之處在於分析測量結果，詳情請參考下方程式碼之中的註解。我是用集合儲存硬幣資料，由於 Python 的集合可以直接取聯集 (union)、差集 (difference)，寫起來比較簡單。

Python 程式碼

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

T = int(input())  # T 組測資
for _ in range(T):
    """ 前置作業 """
    data = []  # 測試資料，內容為 [left, right, satatus]
    coins = set()  # 所有參與測試的硬幣
    status = dict()  # 硬幣狀態，內容為 name: [light possible, heavy possible]
    for _ in range(3):  # 讀取 3 次測試結果
        left, right, state = input().split()  # 左側硬幣，右側硬幣，右側狀態
        data.append([left, right, state])  # 資料加到 data
        for coin in left: coins.add(coin)  # 更新 coins
        for coin in right: coins.add(coin)
    for coin in coins:  # 更新 status，預設值為 [True, True]
        status[coin] = [True, True]
    """ 處理測試資料 """
    for left, right, state in data:  # 依序讀取測試資料
        if state == "even":  # 如果兩側平衡，左、右的硬幣都是真的
            for coin in left: status[coin] = [False, False]  # 更新 status，兩種狀態都是 False
            for coin in right: status[coin] = [False, False]
        elif state == "up":  # 如果右側較高，代表左側較重、右側較輕，假的硬幣一定在這些硬幣之中
            leri = set(left).union(set(right))  # 兩側硬幣的聯集
            for coin in coins.difference(leri):  # 沒有參與這次測試的硬幣都是真的
                status[coin] = [False, False]
            for coin in left: status[coin][0] = False  # 左側硬幣不可能比真的硬幣輕
            for coin in right: status[coin][1] = False  # 右側硬幣不可能比真的硬幣重
        else:  # 如果右側較低，代表左側較輕、右側較重，假的硬幣一定在這些硬幣之中
            leri = set(left).union(set(right))  # 兩側硬幣的聯集
            for coin in coins.difference(leri):  # 沒有參與這次測試的硬幣都是真的
                status[coin] = [False, False]
            for coin in left: status[coin][1] = False  # 左側硬幣不可能比真的硬幣重
            for coin in right: status[coin][0] = False  # 右側硬幣不可能比真的硬幣輕
    """ 結束測試，找答案 """
    fake, result = "", ""  # 假的硬幣名稱、狀態
    for coin, (light, heavy) in status.items():  # 依序讀取 status 的資料
        if light and not heavy:  # 如果這個硬幣可能比較輕、不可能比較重
            fake = coin  # 找到假的硬幣
            result = "light"  # 較輕
            break  # 中止迴圈
        if not light and heavy:  # 如果這個硬幣不可能比較輕、可能比較重
            fake = coin  # 找到假的硬幣
            result = "heavy"  # 較重
            break  # 中止迴圈
    print(f"{fake:s} is the counterfeit coin and it is {result:s}.")

ZeroJudge 解題筆記：c092. 00587 - There's treasure everywhere!

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


ZeroJudge 題目連結：c092. 00587 - There's treasure everywhere!

解題想法

我先用字典儲存各種方向縮寫對應的 1 個單位位移量，接下來再依照讀取到的測資計算東西向、南北向位移。我花最多時間的地方反而是在讀取測資，因為用數量不一定的逗號、句號分隔資料，反而比用空格分隔資料還要麻煩。用 C++ 解題時，如果用 float 會吃 WA，要用 double 才能 AC。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    if line.rstrip() == "END": break
    ca += 1  # case 加 1
    if ca > 1: print()
    x, y = 0.0, 0.0  # 目前的位置
    dia = 1.0/(2**0.5)  # 對角線長度，2分之根號2
    dirs = {"N": (0.0, 1.0), "E": (1.0, 0.0), "S": (0.0, -1.0), "W": (-1.0, 0.0),
            "NE": (dia, dia), "NW": (-dia, dia), "SE": (dia, -dia), "SW": (-dia, -dia)}
    steps = line[:-2].split(",")  # 刪除最後的 .\n，再用 , 分割，存成串列
    for step in steps:  # 依序讀取每一步的距離、方向
        a = 0; d = ""  # 移動距離、方向
        for i, c in enumerate(step):  # 依序讀取 step 的字元，讀到英文字母為止
            if c.isalpha():
                a = int(step[:i])
                d = step[i:]
                break
        x, y = x + a*dirs[d][0], y + a*dirs[d][1]  # 更新位置
    print(f"Map #{ca:d}")
    print(f"The treasure is located at ({x:.3f},{y:.3f}).")
    print(f"The distance to the treasure is {(x*x + y*y)**0.5:.3f}.")

ZeroJudge 解題筆記：c091. 00576 - Hiaku Review

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


ZeroJudge 題目連結：c091. 00576 - Hiaku Review

解題想法

Python 可以用 split("/") 以斜線分割句字，而 C++ 則是依序讀取字元，讀到 / 時結算前一個句字。依序計算每個句子中的音節數量，但是連續的母音只能算 1 個音節，記錄前方的字元否為母音，如果這個字元不是母音，則音節數量加 1。

Python 程式碼

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

import sys

for line in sys.stdin:
    if line.rstrip() == "e/o/i": break
    sens = line.rstrip().split("/")
    standard = (0, 5, 7, 5)  # 三個句子的標準音節數量
    haiku = True  # 是否符合規則
    for i, sen in enumerate(sens, start=1):
        cnt = 0  # 音節數量
        state = False  # 前方的字元是否為母音 aeiouy
        for c in sen:  # 依序讀取 sen 的字元 c
            if c in "aeiouy": state = True  # 如果 c 是 aeiouy
            else:  # 如果 c 不是 aeiouy
                if state: cnt += 1  # 如果前方的字元是母音，音節數量加 1
                state = False  # 重設狀態
        if state: cnt += 1  # 如果最後是連續母音，cnt 加 1
        if cnt != standard[i]:  # 如果音節數量不合
            print(i)  # 印出 i
            haiku = False  # 不符合規則
            break  # 中止迴圈
    if haiku: print("Y")  # 如果符合規則，印出 Y

ZeroJudge 解題筆記：c089. 00389 - Basically Speaking

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


ZeroJudge 題目連結：c089. 00389 - Basically Speaking

解題想法

由於 Python 的 int 內建了用指定進位制將字串轉換成 10 進位整數的功能，這部分可以使用預設工具；但是輸出格式之中沒有對應 7 進位制的工具，需要自己寫。而 C++ 則是兩個部分都要自己寫。

Python 程式碼

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

import sys

def ntos(n, base):  # 輸入整數 n、基底 base，輸出轉換後的字串
    # 數字 0 ~ 15 對應的字元
    table = {0: '0', 1: '1', 2: '2', 3: '3',
             4: '4', 5: '5', 6: '6', 7: '7',
             8: '8', 9: '9', 10: 'A', 11: 'B',
             12: 'C', 13: 'D', 14: 'E', 15: 'F'}
    s = ""  # 儲存結果用的字串
    while n > 0:  # 如果 n 大於 0 繼續執行
        s = table[n%base] + s  # 取 n%base 對應的字元加到 s 前面
        n //= base  # n 變為 1/base 倍
    return s  # 回傳 s

for line in sys.stdin:
    arr = line.split()  # 分割後會轉為串列存到 arr
    # 先將字串用指定的基底 arr[1] 轉成 10 進位整數，再用 ntos 轉成 arr[2] 進位字串
    s = ntos(int(arr[0], int(arr[1])), int(arr[2]))
    m = len(s)  # s 的長度
    if m > 7: print("  ERROR")  # 長度大於 7，印出  ERROR
    else: print(" "*(7-m) + s)  # 反之前面補空格到長度為 7 再輸出

ZeroJudge 解題筆記：c088. 00516 - Prime Land

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


ZeroJudge 題目連結：c088. 00516 - Prime Land

解題想法

讀取一行測資，再每次讀取測資中的兩個數字，分別為底數及次方，將這個數字 $n$ 還原成 10 進位；接下來對 $n-1$ 做質因數分解，依照題目要求的格式輸出答案。

Python 程式碼

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

import sys

for line in sys.stdin:
    if line.rstrip() == "0": break
    arr = list(map(int, line.split()))  # 讀取一行資料
    n, m = 1, len(arr)  # n 儲存測資對應的整數，測資長度 m
    for i in range(0, m, 2):  # 一次讀取測資中的兩個數字
        n *= arr[i]**arr[i+1]  # 計算 n
    n -= 1  # 題目要算 n-1 的質因數分解結果
    curr = n  # 儲存 n-1，之後的計算會改變量值
    ans = []  # 答案
    for i in range(2, int(n**0.5)+1):  # 測試 2 ~ sqrt(n) 的質因數
        p = 0  # i 的次方
        while curr%i == 0:  # 如果 curr 能被 i 整除
            p += 1  # 次方加 1
            curr //= i  # curr 變為 1/i 倍
        if p > 0: ans += [p, i]  # 如果 p 大於 0，ans 加上 [p, i]
    if curr > 1: ans += [1, curr]  # 如果 curr 大於 1，ans 要加上 [1, curr]
    if not ans: print(n, 1)  # 如果 ans 是空的，n 是因數，輸出 n 1
    else: print(*ans[::-1])  # 題目要求因數由大到小輸出

ZeroJudge 解題筆記：c087. 00412 - Pi

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


ZeroJudge 題目連結：c087. 00412 - Pi

解題想法

如果測資提供 $n$ 個數字，所有的數對共有 $$ tot = C_n^2 = \frac{n(n-1)}{2} $$ 如果其中有 $cnt$ 組互質，則 $$ \frac{6}{\pi^2} = \frac{cnt}{tot} ~\Rightarrow~ \pi = \sqrt{\frac{6 \times tot}{cnt}} $$

Python 程式碼

用 itertools.combinations 産生數對組合，使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys, itertools, math

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    nums = [int(sys.stdin.readline()) for _ in range(n)]
    cnt, tot = 0, n*(n-1)//2
    for a, b in itertools.combinations(nums, 2):
        if math.gcd(a, b) == 1: cnt += 1
    if cnt == 0:
        print("No estimate for this data set.")
    else:
        print(f"{(6*tot/cnt)**0.5:.6f}")

用遞迴枚舉所有的數對組合，使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys, math

def comb(nums, arr, cnt):
    if len(arr) == 2:
        if math.gcd(*arr) == 1: return cnt+1
        return cnt
    for i in range(len(nums)):
        arr.append(nums[i])
        cnt = comb(nums[i+1:], arr, cnt)
        arr.pop()
    return cnt

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    nums = [int(sys.stdin.readline()) for _ in range(n)]
    tot = n*(n-1)//2
    cnt = comb(nums, [], 0)
    if cnt == 0:
        print("No estimate for this data set.")
    else:
        print(f"{(6*tot/cnt)**0.5:.6f}")

ZeroJudge 解題筆記：c086. 00402 - M*A*S*H

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


ZeroJudge 題目連結：c086. 00402 - M*A*S*H

解題想法

很像約瑟夫環的題目，但是測資不大，直接模擬淘汰的過程即可。

Python 程式碼

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

import sys

ca = 0  # 第幾筆測資
for line in sys.stdin:
    ca += 1  # 加1
    if ca > 1: print()  # 如果不是第1筆測資，換行
    arr = list(map(int, line.split()))  # 讀取一行資料
    n, x = arr[0], arr[1]  # n 個人參加，x 個人可以放假
    persons = [i for i in range(1, n+1)]  # 産生 1 ~ n 的編號
    for k in arr[2:]:  # 依序讀取 20 張牌的數字
        if n == x: break  # 如果剩下 x 個人，中止迴圈
        idx = k-1  # 淘汰者的索引值，初始值為 k-1
        while n > x and idx < n:  # 如果人數大於 x 而且 idx 還沒有出界
            persons.pop(idx)  # 淘汰索引值為 idx 的人
            n -= 1  # 人數減 1
            idx += k-1  # 下一個索引值加 k-1，因為淘汰一個人，不是加 k
    print(f"Selection #{ca:d}")  # 印出答案
    print(*persons)

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

import sys

result = []
data = sys.stdin.read().split()
ptr = 0
ca = 0  # 第幾筆測資
while ptr < len(data):
    ca += 1  # 加1
    if ca > 1: result.append("\n")  # 如果不是第1筆測資，換行
    n = int(data[ptr])  # n 個人參加
    x = int(data[ptr+1])  # x 個人可以放假
    ptr += 2
    persons = list(range(1, n+1))  # 産生 1 ~ n 的編號
    cards = list(map(int, data[ptr:ptr+20]))
    ptr += 20
    for k in cards:  # 依序讀取 20 張牌的數字
        if n == x: break  # 如果剩下 x 個人，中止迴圈
        idx = k-1  # 淘汰者的索引值，初始值為 k-1
        while n > x and idx < n:  # 如果人數大於 x 而且 idx 還沒有出界
            persons.pop(idx)  # 淘汰索引值為 idx 的人
            n -= 1  # 人數減 1
            idx += k-1  # 下一個索引值加 k-1，因為淘汰一個人，不是加 k
    result.append(f"Selection #{ca:d}\n")  # 印出答案
    res = " ".join(map(str, persons))
    result.append(f"{res}\n")
sys.stdout.write("".join(result))