ZeroJudge 解題筆記：c113. 00378 - Intersecting Lines

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


ZeroJudge 題目連結：c113. 00378 - Intersecting Lines

解題想法

直線的方程式可以寫成 $$ ax + by + c = 0 $$ 如果線上的兩個點的座標為 $(x_1, y_1)$、$(x_2, y_2)$，代入上式可得 $$ ax_1 + by_1 + c = 0 ~~~~~ ax_2 + by_2 + c = 0 $$ 兩式相減可得 $$ ax_1 - ax_2 + by_1 - by_2 = 0 ~\Rightarrow~ a(x_1 - x_2) = b(y_2 - y_1) $$ $$ a = y_2 - y_1 ~~~~~ b = x_1 - x_2 ~~~~~ c = -ax_1 - by_1 = x_1(y_1 - y_2) + y_1(x_2 - x_1) $$ 題目給定另一條直線上的座標為 $(x_3, y_3)$、$(x_4, y_4)$，則方程式 $a'x + b'y + c' = 0$ 的係數為 $$ a' = y_4 - y_3 ~~~~~ b' = x_3 - x_4 ~~~~~ c' = -a'x_3 - b'y_3 = x_3(y_3 - y_4) + y_3(x_4 - x_3) $$ 如果兩條直線平行，則 $$ \frac{a}{b} = \frac{a'}{b'} ~\Rightarrow~ ab' = a'b $$ 如果兩條直線重合，除了上式之外還要再加上另外兩個條件 $$ \frac{a}{c} = \frac{a'}{c'} ~\Rightarrow~ ac' = a'c ~~~~~ \frac{b}{c} = \frac{b'}{c'} ~\Rightarrow~ bc' = b'c $$ 如果兩條直線只有一個交點，則 $$ ab'x + bb'y + cb' - (a'bx + b'by + c'b) = 0 ~\Rightarrow~ x = \frac{c'b - cb'}{ab' - a'b} $$ $$ aa'x + ba'y + ca' - (a'ax + b'ay + c'a) = 0 ~\Rightarrow~ y = \frac{c'a - ca'}{ba' - b'a} $$

Python 程式碼

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

def line_equation(x1, y1, x2, y2):
    a = y2 - y1
    b = x1 - x2
    c = x1*(y1 - y2) + y1*(x2 - x1)
    return a, b, c

print("INTERSECTING LINES OUTPUT")
n = int(input())
for _ in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
    a, b, c = line_equation(x1, y1, x2, y2)
    ap, bp, cp = line_equation(x3, y3, x4, y4)
    if a*bp == ap*b:
        if a*cp == ap*c and b*cp == c*bp: print("LINE")
        else: print("NONE")
    else:
        x = (cp*b - c*bp) / (a*bp - ap*b)
        y = (cp*a - c*ap) / (b*ap - bp*a)
        print(f"POINT {x:.2f} {y:.2f}")
print("END OF OUTPUT")

ZeroJudge 解題筆記：c110. 00311 - Packets

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


ZeroJudge 題目連結：c110. 00311 - Packets

解題想法

如果面積 $6 \times 6$ 的商品數量為 $n_6$，需要的箱子數量就是 $n_6$，而且沒有剩下的空間。 如果面積 $5 \times 5$ 的商品數量為 $n_5$，需要的箱子數量為 $n_5$，每一個箱子會剩下面積為 $11$ 的空間，總空間為 $11 n_5$，可以放入面積 $1 \times 1$ 的商品。 如果面積 $4 \times 4$ 的商品數量為 $n_4$，需要的箱子數量為 $n_4$，每一個箱子會剩下面積為 $20$ 的空間，總空間為 $20 n_4$，可以放入面積 $2 \times 2$ 的商品最多 $5$ 個，如果還有剩下的空間，可以再放入面積 $1 \times 1$ 的商品。下圖的 O 代表可用空間，X 代表已被面積 $4 \times 4$ 商品佔用的空間。

OOOOOO
OOOOOO
XXXXOO
XXXXOO
XXXXOO
XXXXOO

如果面積 $3 \times 3$ 的商品數量為 $n_3$，一個箱子最多可以放入 $4$ 個面積 $3 \times 3$ 的商品，需要的箱子數量 $$ p_3 = \left \lceil \frac{n_3}{4} \right \rceil $$ 如果 $n_3$ 是 $4$ 的倍數，不會有剩下的空間；如果 $mod(n_3, 4) = 1$ 剩下面積為 $27$ 的空間，可以放入面積 $2 \times 2$ 的商品最多 $5$ 個；如果 $mod(n_3, 4) = 2$ 剩下面積為 $18$ 的空間，可以放入面積 $2 \times 2$ 的商品最多 $3$ 個；如果 $mod(n_3, 4) = 3$ 剩下面積為 $9$ 的空間，可以放入面積 $2 \times 2$ 的商品最多 $1$ 個。如果還有剩下的空間，可以再放入面積 $1 \times 1$ 的商品。下圖的 O 代表可用空間，X 代表已被面積 $3 \times 3$ 商品佔用的空間。

OOOOOO     OOOOOO     XXXOOO
OOOOOO     OOOOOO     XXXOOO
OOOOOO     OOOOOO     XXXOOO
XXXOOO     XXXXXX     XXXXXX
XXXOOO     XXXXXX     XXXXXX
XXXOOO     XXXXXX     XXXXXX

如果面積 $2 \times 2$ 的商品數量為 $n_2$，一個箱子最多可以放入 $9$ 個面積 $2 \times 2$ 的商品，需要的箱子數量 $$ p_2 = \left \lceil \frac{n_2}{9} \right \rceil $$ 如果 $n_2$ 是 $9$ 的倍數，不會有剩下的空間；如果 $mod(n_2, 9) = r_2$ 剩下面積為 $36 - 4 r_2$ 的空間，可以放入面積 $1 \times 1$ 的商品。 如果面積 $1 \times 1$ 的商品數量為 $n_1$，一個箱子最多可以放入 $36$ 個面積 $1 \times 1$ 的商品，需要的箱子數量 $$ p_1 = \left \lceil \frac{n_1}{36} \right \rceil $$ 最後答案為 $ans = p_1 + p_2 + p_3 + n_4 + n_5 + n_6$

Python 程式碼

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

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n1, n2, n3, n4, n5, n6 = map(int, line.split())
    if n1 == 0 and n2 == 0 and n3 == 0 and n4 == 0 and n5 == 0 and n6 == 0: break
    """ 放入 5*5 的商品 """
    s5 = 11*n5  # 放 5*5 商品箱子剩下的空間
    if s5 >= n1:  # 可以放入所有 1*1 商品
        s5 -= n1; n1 = 0
    else:  # 無法放入所有 1*1 商品
        n1 -= s5; s5 = 0
    """ 放入 4*4 的商品 """
    s4 = 20*n4  # 放 4*4 商品箱子剩下的空間
    if s4 >= n2*4:  # 可以放入所有 2*2 商品
        s4 -= n2*4; n2 = 0
    else:  # 無法放入所有 2*2 商品
        n2 -= s4//4; s4 = 0
    if s4 > 0 and n1 > 0:  # s4 還有空間而且還有 1*1 商品要放
        if s4 >= n1:  # 可以放入所有 1*1 商品
            s4 -= n1; n1 = 0
        else:  # 無法放入所有 1*1 商品
            n1 -= s4; s4 = 0
    """ 放入 3*3 的商品 """
    r3 = n3%4  # 沒放滿的箱子中 3*3 商品數量
    p3 = n3//4 + (r3 > 0)  # 3*3 商品使用的箱子數量
    s3 = 0  # 沒放滿的箱子剩下的面積
    if r3 == 1:  # 放 1 個 3*3 商品
        s3 = 27  # 面積剩下 27
        if n2 <= 5:  # 可以放入所有 2*2 商品
            s3 -= n2*4; n2 = 0
        else:  # 無法放入所有 2*2 商品
            s3 -= 20; n2 -= 5
    elif r3 == 2:  # 放 2 個 3*3 商品
        s3 = 18  # 面積剩下 18
        if n2 <= 3:  # 可以放入所有 2*2 商品
            s3 -= n2*4; n2 = 0
        else:  # 無法放入所有 2*2 商品
            s3 -= 12; n2 -= 3
    elif r3 == 3:  # 放 3 個 3*3 商品
        s3 = 9  # 面積剩下 9
        if n2 == 1:  # 可以放入所有 2*2 商品
            s3 -= 4; n2 = 0
        elif n2 > 1:  # 無法放入所有 2*2 商品
            s3 -= 4; n2 -= 1
    if s3 > 0 and n1 > 0:  # s3 還有空間而且還有 1*1 商品要放
        if s3 >= n1:  # 可以放入所有 1*1 商品
            s3 -= n1; n1 = 0
        else:  # 無法放入所有 1*1 商品
            n1 -= s3; s3 = 0
    """ 放入 2*2 的商品 """
    r2 = n2%9  # 沒放滿的箱子中 3*3 商品數量
    p2 = n2//9 + (r2 > 0)  # 2*2 商品使用的箱子數量
    s2 = 0 if r2 == 0 else 36 - r2*4  # 沒放滿的箱子剩下的面積
    if s2 > 0 and n1 > 0:  # s2 還有空間而且還有 1*1 商品要放
        if s2 >= n1:  # 可以放入所有 1*1 商品
            s2 -= n1; n1 = 0
        else:  # 無法放入所有 1*1 商品
            n1 -= s2; s2 = 0
    """ 放入 1*1 的商品 """
    p1 = n1//36 + (n1%36 > 0)
    """ 印出答案 """
    print(p1 + p2 + p3 + n4 + n5 + n6)

ZeroJudge 解題筆記：c106. 00271 - Simply Syntax

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


ZeroJudge 題目連結：c106. 00271 - Simply Syntax

解題想法

原文的題目連結，其中條件的部分為

The only characters in the language are the characters 'p' through 'z' and 'N', 'C', 'D', 'E', and 'I'. 句子之中只有英文小寫字母 p 到 z、大寫字母 N, C, D, E, I。
1. Every character from 'p' through 'z' is a correct sentence. 英文小寫字母 p 到 z 是合法的。
2. If s is a correct sentence, then so is Ns. 如果某個單字 s 是合法的，則 Ns 也是合法的，注意，這裡面的 s 不是專門指小寫字母 s。
3. If s and t are correct sentences, then so are Cst, Dst, Est and Ist. 如果某兩個單字 st 是合法的，則 Cst、Dst、Est 及 Ist 也是合法的，注意，這裡面的 st 不是專門指小寫字母 st。
4. Rules 0. to 3. are the only rules to determine the syntactical correctness of a sentence. 只有規則 0 到 3，沒有其它的規則。

Python 程式碼

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

import sys

def check(s):
    st = []  # 有效字元的堆疊
    for c in s[::-1]:  # 由後向前讀取
        if c in "pqrstuvwxyz":  # c 是 pqrstuvwxyz
            st.append(c)  # c 放入 st
        elif c == 'N':  # 如果 c 是 N
            if not st:  # 如果 st 是空的
                return False  # 回傳 False
            a = st.pop()  # 取出 st 最後一項
            st.append(c+a)  # c+a 加入 st
        elif c in "CDEI":  # 如果 c 是 CDEI
            if len(st) < 2:  # 如果 st 不到兩項資料
                return False  # 回傳 False
            a = st.pop()  # 取出 st 最後兩項
            b = st.pop()
            st.append(c+a+b)  # c+a+b 加入 st
        else:  # 其它狀況，c 不合法
            return False  # 回傳 False
    return len(st) == 1  # 如果 st 只有一筆資料，整個字串合法

result = []
for line in sys.stdin:
    if not line.rstrip(): continue
    result.append("YES\n" if check(line.rstrip()) else "NO\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c104. 00167 - The Sultan's Successors

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


ZeroJudge 題目連結：c104. 00167 - The Sultan's Successors

解題想法

八皇后的變型，主要考遞迴跟回溯。

Python 程式碼

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

import sys

def solve(grid):  # 主要的解題函式
    rows = [-1]*8  # 目前皇后放置的列
    cols, dia1, dia2 = set(), set(), set()  # 已用的欄、左上右下對角線、右上左下對角線
    imax = 0  # 最高分，預設為 0
    ### 回溯，代入列、目前的分數 ###
    def backtrack(row, curr):
        nonlocal imax  # 這樣才能改變外層 imax 的值
        if row == 8:  # 遞迴出口，已放置 8 個皇后
            imax = max(imax, curr)  # 更新 imax
        # 試著在此列每一欄放置皇后
        for col in range(8):
            # 檢查欄、左上右下、右上左下是否已被佔用
            if col not in cols and (row-col) not in dia1 and (row+col) not in dia2:
                # 可以放置皇后
                rows[row] = col
                cols.add(col)
                dia1.add(row-col)
                dia2.add(row+col)
                # 遞迴到下一列，代入加上 (row, col) 的分數
                backtrack(row+1, curr+grid[row][col])
                # 回溯，移除皇后，恢復佔用的狀態
                rows[row] = -1
                cols.remove(col)
                dia1.remove(row-col)
                dia2.remove(row+col)
    ### End of backtrack ###
    backtrack(0, 0)  # 從第 0 列、分數 0 開始回溯
    return imax  # 回傳最高分

idx = 0
lines = sys.stdin.readlines()
t = int(lines[idx])
idx += 1
for _ in range(t):
    grid = [list(map(int, line.split())) for line in lines[idx:idx+8]]
    idx += 8
    imax = solve(grid)
    sys.stdout.write(f"{imax:5d}\n")

ZeroJudge 解題筆記：c103. 00131 - The Psychic Poker Player

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


ZeroJudge 題目連結：c103. 00131 - The Psychic Poker Player

解題想法

這題我只寫了 Python 版本。我先為每一種牌型寫一個自訂函式，再用另一個自訂函式 check 檢查手牌的牌型，由高分檢查到低分。最後再寫一個自訂函式 check 測試各種換牌張數的最高分。討論區裡有一種用數學計算的寫法，但我沒有認真推導數學關係式，就沒有寫了。

Python 程式碼

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

import sys, itertools

def flush(hand):  # 手牌是否為同花
    return all(card[1] == hand[0][1] for card in hand[1:])

def straight(hand):  # 手牌是否為順子
    nums = {'A': 14, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7,
            '8': 8, '9':9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13}  # 牌面數字
    flag1, flag2 = True, True  # 是否為 A, 2, 3, 4, 5，是否為其它號碼的順子
    if hand[-1][0] == 'A':  # 特例，最大的是 A，要檢查是否為 A, 2, 3, 4, 5
        pre = 1  # A 當作 1
        for card in hand[:-1]:
            curr = nums[card[0]]
            if curr != pre+1:
                flag1 = False
                break
            pre = curr
    else: flag1 = False  # 最大的不是 A，不可能是 A, 2, 3, 4, 5
    # 其它號碼的順子
    pre = nums[hand[0][0]]
    for card in hand[1:]:
        curr = nums[card[0]]
        if curr != pre+1:
            flag2 = False
            break
        pre = curr
    return flag1 or flag2

def straight_flush(hand):  # 手牌是否為同花順
    return flush(hand) and straight(hand)

def four_of_a_kind(hand):  # 手牌是否為鐵支
    cnt = dict()  # 計數器
    for card in hand:  # 依序讀取手牌數值
        n = card[0]
        if n not in cnt: cnt[n] = 1
        else: cnt[n] += 1
    return max(cnt.values()) == 4  # 如果某一種數值有 4 張，是鐵支

def full_house(hand):  # 手牌是否為葫蘆
    cnt = dict()  # 計數器
    for card in hand:  # 依序讀取手牌數值
        n = card[0]
        if n not in cnt: cnt[n] = 1
        else: cnt[n] += 1
    tmp = sorted(cnt.values())  # 牌面數量排序
    return len(tmp) == 2 and tmp[0] == 2 and tmp[1] == 3

def three_of_a_kind(hand):  # 手牌是否為三條
    cnt = dict()  # 計數器
    for card in hand:  # 依序讀取手牌數值
        n = card[0]
        if n not in cnt: cnt[n] = 1
        else: cnt[n] += 1
    tmp = sorted(cnt.values())  # 牌面數量排序
    return len(tmp) == 3 and tmp[0] == 1 and tmp[1] == 1 and tmp[2] == 3

def two_pairs(hand):  # 手牌是否為兩對
    cnt = dict()  # 計數器
    for card in hand:  # 依序讀取手牌數值
        n = card[0]
        if n not in cnt: cnt[n] = 1
        else: cnt[n] += 1
    tmp = sorted(cnt.values())  # 牌面數量排序
    return len(tmp) == 3 and tmp[0] == 1 and tmp[1] == 2 and tmp[2] == 2

def one_pair(hand):  # 手牌是否為一對
    cnt = dict()  # 計數器
    for card in hand:  # 依序讀取手牌數值
        n = card[0]
        if n not in cnt: cnt[n] = 1
        else: cnt[n] += 1
    tmp = sorted(cnt.values())  # 牌面數量排序
    return len(tmp) == 4 and tmp[0] == 1 and tmp[1] == 1 and tmp[2] == 1 and tmp[3] == 2

def check(hand):
    if straight_flush(hand): return 8
    if four_of_a_kind(hand): return 7
    if full_house(hand): return 6
    if flush(hand): return 5
    if straight(hand): return 4
    if three_of_a_kind(hand): return 3
    if two_pairs(hand): return 2
    if one_pair(hand): return 1
    return 0

def change(hand, deck):  # 輸入手牌、牌庫，依序檢查
    result = [[0, i] for i in range(6)]  # 從牌庫換 0 ~ 5 張牌可組成的最大組合，[組合, 換牌數量]
    result[0][0] = check(hand)
    # 換一張牌，測試換第一張 ~ 第五張的效果
    best = 0
    for i in range(5):
        tmp = hand[:i] + hand[i+1:] + [deck[0]]
        tmp.sort(key = lambda x : (nums[x[0]], shdc[x[1]]))
        best = max(best, check(tmp))
    result[1][0] = best
    # 換二張牌，測試換其中兩張牌的效果
    best = 0
    for i, j in itertools.combinations(range(5), 2):
        tmp = hand.copy()
        tmp.remove(hand[i])
        tmp.remove(hand[j])
        tmp += deck[:2]
        tmp.sort(key = lambda x : (nums[x[0]], shdc[x[1]]))
        best = max(best, check(tmp))
    result[2][0] = best
    # 換三張牌，測試換其中三張牌的效果
    best = 0
    for i, j, k in itertools.combinations(range(5), 3):
        tmp = hand.copy()
        tmp.remove(hand[i])
        tmp.remove(hand[j])
        tmp.remove(hand[k])
        tmp += deck[:3]
        tmp.sort(key = lambda x : (nums[x[0]], shdc[x[1]]))
        best = max(best, check(tmp))
    result[3][0] = best
    # 換四張牌，測試只留其中一張牌的效果
    best = 0
    for i in range(5):
        tmp = [hand[i]] + deck[:4]
        tmp.sort(key = lambda x : (nums[x[0]], shdc[x[1]]))
        best = max(best, check(tmp))
    result[4][0] = best
    # 全換
    result[5][0] = check(deck)
    result.sort(reverse=True)
    return result[0]

for line in sys.stdin:
    hand = line.split()[:5]
    deck = line.split()[5:]
    nums = {'A': 14, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7,
            '8': 8, '9':9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13}  # 牌面數字
    shdc = {'S': 0, 'H': 1, 'D': 2, 'C': 3}  # 花色
    comb = ("highest-card", "one-pair", "two-pairs", "three-of-a-kind", "straight",
            "flush", "full-house", "four-of-a-kind", "straight-flush")
    sorted_hand = sorted(hand, key = lambda x : (nums[x[0]], shdc[x[1]]))  # 數字、花色由小到大排序
    best_comb, change_cards = change(sorted_hand, deck)
    print("Hand: ", end="")
    print(*hand, end=" ")
    print("Deck: ", end="")
    print(*deck, end=" ")
    print(f"Best hand: {comb[best_comb]:s}")

ZeroJudge 解題筆記：c102. 00128 - Software CRC

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


ZeroJudge 題目連結：c102. 00128 - Software CRC

解題想法

這題會用到字元的 ASCII 編碼，因為編碼為 0 到 255 的整數，可以用 1 個位元組 (byte)、8 個位元 (bit)、2 位數的 16 進位整數表示。題目的意思應該是將讀到的字串，逐一按照字元的 ASCII 編碼排成很長一列的 16 進位整數，最後再加上兩個 16 進位整數的 CRC 碼，讓這個很長的 16 進位整數可以被指定的 10 進位整數 34943 整除。題目要求的就是每一行測資對應的 CRC 碼。解題過程如下：

1. 假設字串對應的整數儲存於變數 m，從字串 s 最前面依序讀取字元 c，將 m 向左平移 8 位元之後加上 c 的 ASCII 編碼。為了避免 m 溢位，可以在每一次計算後對 g 取餘數。
2. 將 m 向左平移 16 位元，增加給 CRC 碼的空間，再對 g 取餘數 r。
3. 如果 r 等於 0，CRC 碼就是 0；反之，CRC 碼為 g-r。
4. 將 CRC 碼向右平移 8 位元再與 0XFF 取 &，可以得到第一個 byte 的值；將 CRC 碼與 0XFF 取 &，可以得到第二個 byte 的值。

Python 程式碼

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

import sys

def solve(s):
    g, m = 34943, 0  # 取餘數用的除數，字串編碼對應的整數
    for c in s:  # 依序讀取 s 的字元 c
        m = ((m << 8) + ord(c)) % g  # m 向左平移 8 位元後加上 c 的 ASCII 碼，再取餘數
    m <<= 16  # m 向左平移 16 位元，增加給 CRC 碼的空間
    r = m%g  # m 對 g 取餘數
    crc = 0  # CRC  碼預設為 0
    if r > 0: crc = g-r  # 如果 r 大於 0，CRC  碼改成 g-r
    byte1 = (crc >> 8) & 0xFF  # CRC  碼向右平移 8 位元，與 0xFF 取 &
    byte2 = crc & 0xFF  # CRC  碼與 0xFF 取 &
    print(f"{byte1:02X} {byte2:02X}")  # 將兩個位元組用 16 進位輸出

for line in sys.stdin:
    line = line.rstrip()
    if line == "#": break
    solve(line)

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}.")