ZeroJudge 解題筆記：i706. B.永遠ㄉ神（yyds）

作者：王一哲
日期：2025年11月22日


ZeroJudge 題目連結：i706. B.永遠ㄉ神（yyds）

解題想法

用堆疊 st 記錄前方的人身高及索引值，堆疊中先放入 (-float('inf'), 0) 避免遇到空堆疊的狀況。每次讀取第 i 個人的身高 h，用 while 迴圈從 st 最上方開始檢查，移除所有身高大於 h 的資料，當 while 迴圈結束之後，st 最上方的資料的索引值就是要輸出的答案，再將 (h, i) 加入 st。

Python 程式碼

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

import sys

n = int(sys.stdin.readline())
st = [(-float('inf'), 0)]
ans = []
for i, h in enumerate(map(int, sys.stdin.readline().split()), start=1):
    while st[-1][0] >= h: st.pop()
    ans.append(str(st[-1][1]))
    st.append((h, i))
sys.stdout.write(" ".join(ans) + "\n")

ZeroJudge 解題筆記：a584. 2. 親等關係

作者：王一哲
日期：2025年11月21日


ZeroJudge 題目連結：a584. 2. 親等關係

解題想法

題目看起來像是樹，但其實用字典及串列儲存無向圖，再用 BFS 找兩個人之間的距離就過關了。如果用 Python 解題可以用 collections.defaultdict 存圖，這樣可以不需要檢查 key 值是否已在字典之中。我用 Python 寫這題很順利，反而是用 C++ 解題是吃了好幾次 WA，後來發現測資在第 1 行的人數 n 之後換行的格式可能比較特別，我一開始只有 cin.ignore() 跳過一個 \n，但是這樣會吃 WA，改成用 getline 讀取一整行才過關。

Python 程式碼

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

from collections import defaultdict, deque

""" 讀取測資並存圖 """
n = int(input())  # n 個人
graph = defaultdict(list)  # 無向圖，用字串當作 key，list 裡面存字串
for _ in range(n):  # 讀取 n 行
    names = input().split()  # 名字，用空格分割
    parent = names[0]  # 父節點名稱
    children = names[1:]  # 子節點名稱，可能有多個子節點
    for child in children:  # 依序讀取每個子節點名稱
        graph[parent].append(child)  # 儲存節點之間連接的方式
        graph[child].append(parent)
""" 讀取最後一行並用 BFS 找答案 """
a, b = input().split()  # 要找距離的兩個人名
que = deque([(a, 0)])  # 待走訪佇列，資料為 (節點, 距離)，先存入 (a, 0)
ans = 0  # 答案
visited = {a}  # 用 set 儲存已走訪節點名稱
while que:  # 如果 que 有資料繼續執行
    u, d = que.popleft()  # 從 que 開頭取出節點 u、距離 d
    if u == b:  # 如果 u 等於 b，找到終點
        ans = d  # 答案為 d
        break  # 中止迴圈
    for v in graph[u]:  # 依序讀取與 u 相連的節點 v
       if v in visited: continue  # 如果 v 已走訪過，找下一個節點
       visited.add(v)  # v 加入 visited
       que.append((v, d+1))  # (v, d+1) 加入 que
# 結束 BFS，印出答案
print(ans)

ZeroJudge 解題筆記：i645. 排列組合-組合

作者：王一哲
日期：2025年11月20日


ZeroJudge 題目連結：i645. 排列組合-組合

解題想法

這題原來應該是要考用函式遞迴及回溯，但是在 Python 可以用 itertools.combinations 産生所有的組合。

Python 程式碼

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

import sys

def comb(n, m, start, s):
    if len(s) == m:
        print(s)
        return 
    for i in range(start, n):
        c = chr(i + ord('a'))
        comb(n, m, i+1, s+c)

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    comb(n, m, 0, "")

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

import sys
from itertools import combinations

result = []
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    chars = [chr(i + ord('a')) for i in range(n)]
    for comb in combinations(chars, m):
        s = "".join(comb)
        result.append(f"{s}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：i644. 列舉八皇后問題所有解

作者：王一哲
日期：2025年11月19日


ZeroJudge 題目連結：i644. 列舉八皇后問題所有解

解題想法

經典的題目，用函式遞迴及回溯比較好寫。

Python 程式碼

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

def solve_n_queens(n):  # 自訂函式，解 n 皇后問題
    # 回溯，代入目前的列，已用的欄、左上右下斜線、右上左下斜線
    def backtrack(row, cols, diag1, diag2):
        if row == n:  # 遞迴出口，填入第 n 列，找到一組解
            # 將 borad 儲存的欄與列組成 tuple，依照欄排序，存入 ans
            # 由 ans 取出列的順序，轉成字串，存入 solutions
            ans = sorted([(c, i) for i, c in enumerate(board, start=1)])
            solutions.append("".join([str(i) for _, i in ans]))
        for col in range(n):  # 依序測試第 0 ~ n-1 欄
            d1 = row - col  # 左上右下斜線
            d2 = row + col  # 右上左下斜線
            # 如果 col, d1, d2 不在已用的集合之中，可以用這個位置
            if col not in cols and d1 not in diag1 and d2 not in diag2:
                board[row] = col  # row 列使用的欄為 col
                # 遞迴，找下一列，代入原來的集合分別與 col, d1, d2 的聯集
                backtrack(row+1, cols | {col}, diag1 | {d1}, diag2 | {d2})
    # end of backtrack
    solutions = []  # 所有的解
    board = [-1]*n  # 第 row 列的皇后放在第 col 欄
    backtrack(0, set(), set(), set())  # 呼叫 backtrack 求解
    return solutions  # 回傳所有的解
# end of solve_n_queens
all_solutions = solve_n_queens(8)
all_solutions.sort()  # 依照字典排序
for i, sol in enumerate(all_solutions, start=1):
    print(f"{i:d}: {sol:s}")

ZeroJudge 解題筆記：i510. 尋找子字串

作者：王一哲
日期：2025年11月18日


ZeroJudge 題目連結：i510. 尋找子字串

解題想法

這題用字串的 find 功能很好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    s, t = sys.stdin.readline().split()
    idx = s.find(t)
    if idx == -1: print("No")
    else: print(f"Yes\npos: {idx:d}")

ZeroJudge 解題筆記：i213. stack 練習

作者：王一哲
日期：2025年11月17日


ZeroJudge 題目連結：i213. stack 練習

解題想法

這題是堆疊 (stack) 的基本操作，在 Python 可以用 list 代替，在 C++ 可以用 stack 或 vector。

Python 程式碼

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

n = int(input())
st = []
for _ in range(n):
    line = input().split()
    if len(line) == 1:
        if line[0] == '2':
            if st: print(st[-1])
            else: print(-1)
        elif line[0] == '3':
            if st: st.pop()
    else:
        st.append(int(line[1]))

ZeroJudge 解題筆記：i177. 小畫家 (Painter)

作者：王一哲
日期：2025年11月16日


ZeroJudge 題目連結：i177. 小畫家 (Painter)

解題想法

這題用 BFS ，我習慣在旁邊加一圈哨兵，這樣可以不需要檢查是否出界。

Python 程式碼

加哨兵，不需要檢查是否出界，使用時間約為 0.4 s，記憶體約為 14.8 MB，通過測試。

from collections import deque

h, w, si, sj, z = map(int, input().split())
grid = [list(map(int, input().split())) + [-1] for _ in range(h)]
grid.append([-1]*(w+1))
color = grid[si-1][sj-1]
if color != z:
    que = deque([(si-1,sj-1)])
    grid[si-1][sj-1] = z
    while que:
        r, c = que.popleft()
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nr, nc = r+dr, c+dc
            if grid[nr][nc] == color:
                grid[nr][nc] = z
                que.append((nr, nc))
for row in grid[:h]: print(*row[:w])

ZeroJudge 解題筆記：i121. 英文字母大小寫的抉擇

作者：王一哲
日期：2025年11月15日


ZeroJudge 題目連結：i121. 英文字母大小寫的抉擇

解題想法

這題應該是專門出給 Python 的題目，因為 Python 的字串內建 capitalize(), upper(), title(), lower() 這四種格式，如果要用 C++ 寫這題會很麻煩。

Python 程式碼

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

line = input()
style = int(input())
if style == 1:
    print(line.capitalize())
elif style == 2:
    print(line.upper())
elif style == 3:
    print(line.title())
else:
    print(line.lower())

ZeroJudge 解題筆記：i025. 真因數和 (小 n)

作者：王一哲
日期：2025年11月14日


ZeroJudge 題目連結：i025. 真因數和 (小 n)

解題想法

因為測資不太，用試除法測試 $i = 2$ 到 $i = floor(\sqrt{n})$ 之間的整數是否為因數，如果 $i$ 是因數，則答案要加上 $i$ 及 $n/i$，最後再檢查 $n$ 是否為平方數，如果是平方數則答案要再減去 $\sqrt{n}$。

Python 程式碼

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

n = int(input())
if n == 1: print(0)  # 特例
else:
    root = int(n**0.5)
    isum = 1  # 所有真因數的合，找到真因數直接加起來就好
    for i in range(2, root+1):
        if n%i == 0:
            isum += i + (n//i)
    if root*root == n: isum -= root  # 完全平方數會多加一個 root，要扣掉
    print(isum)

ZeroJudge 解題筆記：h495. 農家樂(Agricola)

作者：王一哲
日期：2025年11月13日


ZeroJudge 題目連結：h495. 農家樂(Agricola)

解題想法

由於各項目的分數與數量沒有特定的數學關係，我只想到對每個項目分別建一個串列，記錄各數量對應的分數。

Python 程式碼

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

field = (-1, -1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
enclosure = (-1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
wheat = (-1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
vegetable = (-1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
sheep = (-1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
pig = (-1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
catle = (-1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)
t = int(input())
for _ in range(t):
    arr = tuple(map(int, input().split()));
    score = field[arr[0]] + enclosure[arr[1]] + wheat[arr[2]] + vegetable[arr[3]] + \
            sheep[arr[4]] + pig[arr[5]] + catle[arr[6]] - arr[7] + arr[8] + arr[9] + \
            2*arr[10] + 3*arr[11] + arr[12]
    print(score)

ZeroJudge 解題筆記：h089. 疊披薩

作者：王一哲
日期：2025年11月12日


ZeroJudge 題目連結：h089. 疊披薩

解題想法

這題就是河內塔。

Python 程式碼

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

def hanoi(n, src, aux, dst):
    if n == 1:
        print(f"from {src:s} to {dst:s}")
        return
    hanoi(n-1, src, dst, aux)
    print(f"from {src:s} to {dst:s}")
    hanoi(n-1, aux, src, dst)

hanoi(int(input()), "A", "B", "C")

ZeroJudge 解題筆記：h206. 強者就是要戰，但......什麼才是強者呢？

作者：王一哲
日期：2025年11月11日


ZeroJudge 題目連結：h206. 強者就是要戰，但......什麼才是強者呢？

解題想法

這題考分治法。

Python 程式碼

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

def solve(nums, big):  # 自定函式，代入串列，是否取較大的值
    n = len(nums)  # 串列長度
    if n == 1: return nums[0]  # 遞迴出口，只剩一項，回傳此項
    left = nums[:n//2]  # 左半部
    right = nums[n//2:]  # 右半部
    mleft = solve(left, not big)  # 遞迴，代入左半部，big 的狀態要反過來
    mright = solve(right, not big)  # 遞迴，代入右半部，big 的狀態要反過來
    if big: return max(mleft, mright)  # 如果 big 為 True，取左、右兩半較大的值
    else: return min(mleft, mright)  # 反之，取左、右兩半較小的值

n = int(input())
arr = list(map(int, input().split()))
print(solve(arr, True))

ZeroJudge 解題筆記：h075. 成績排名

作者：王一哲
日期：2025年11月10日


ZeroJudge 題目連結：h075. 成績排名

解題想法

這題輸出的加權平均可能是小數或整數，因為分母是10，如果是小數則印出到小數點後一位。由於題目要求的比序依序為加權平均、資訊、數學、英文成績由高到低，如果前面4項成績相同，再依照座號由小到大排序，如果使用 Python，可以將每個人的加權平均、資訊、數學、英文、座號的負值等5項組成 tuple 存到串列當中，用 sort 排序串列時會自動依照 tuple 之中的數值由小到大排序。如果使用 C++，可以用vector 儲存每個人資料，也可以自訂結構體，不過這樣就需要自己寫排序用的比較式。

Python 程式碼

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

n = int(input())
students = []  # (tot, cs, math, english, -num)
for _ in range(n):
    num, cs, math, english = list(map(int, input().split()))
    tot = cs*5 + math*3 + english*2
    students.append((tot, cs, math, english, -num))
students.sort(reverse=True)
for student in students:
    tot, num = student[0], -student[4]
    if tot%10 == 0: print(f"{num:d} {tot//10:d}")
    else: print(f"{num:d} {tot/10:.1f}")

ZeroJudge 解題筆記：g640. 璽羽的壽司

作者：王一哲
日期：2025年11月9日


ZeroJudge 題目連結：g640. 璽羽的壽司

解題想法

因為壽司沒有限量，可以重複賣出同樣價格的壽司，所以只要先將所有的壽司價格由小到大排序，再用二分搜尋法從所有壽司價格找等於顧客標準或是大於標準且最接近的值。

Python 程式碼

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

from bisect import bisect_left

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
tot = 0
for b in map(int, input().split()):
    idx = bisect_left(arr, b)
    if idx == n: continue
    tot += arr[idx]
print(tot)

ZeroJudge 解題筆記：g499. 109北二1.感測器的比較

作者：王一哲
日期：2025年11月8日


ZeroJudge 題目連結：g499. 109北二1.感測器的比較

解題想法

這題理論上可以用 while 迴圈計算 a 的個位數為 0 且 b 的個位數為 1 的數量，每次計算後將 a, b 除以 2，直到 a, b 其中一個等於 0 為止，但是這樣的速度很慢，用 C++ 可以過關，但是用 Python 在第 16 筆測資會超時。 改用位元運算，因為題目要求 a 的位數為 0、b 的位數為 1，先取 a XOR b，這樣位數不同的部分計算結果為 1，再與 b 取 AND，只有 a 的位數為 0、b 的位數為 1 的部分計算結果為 1。如果是 Python 可以用 bin 將計算結果轉成二進位制的字串，計算其中有幾個 1 即可。

Python 程式碼

第10筆測資開始超時。

data = list(map(int, input().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    while a > 0 or b > 0:  # 當 a 大於 0 或 b 大於 0 繼續執行 
        if a%2 == 0 and b%2 == 1: cnt += 1  # 如果 a 的個位數為 0 且 b 的個位數為 1，cnt 加 1
        a >>= 1; b >>= 1  # a, b 除以 2
print(cnt)  # 印出答案

改用 sys.stdin.readline 及 sys.stdout.write 加速，第16筆測資開始超時。

import sys

data = list(map(int, sys.stdin.readline().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    while a > 0 or b > 0:  # 當 a 大於 0 或 b 大於 0 繼續執行 
        if a&1 == 0 and b&1 == 1: cnt += 1  # 如果 a 的個位數為 0 且 b 的個位數為 1，cnt 加 1
        a >>= 1; b >>= 1  # a, b 除以 2
sys.stdout.write(f"{cnt:d}\n")  # 印出答案

改用位元運算，使用時間約為 2.8 s，記憶體約為 255.7 MB，通過測試。

import sys

data = list(map(int, sys.stdin.readline().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    cnt += sum(c == '1' for c in bin(b & (a^b))[2:])
sys.stdout.write(f"{cnt:d}\n")  # 印出答案

ZeroJudge 解題筆記：g489. 社團點點名

作者：王一哲
日期：2025年11月7日


ZeroJudge 題目連結：g489. 社團點點名

解題想法

題目說明有問題，測資中有不在社團名單裡的出席者，所以答案有可能是負的。用集合 members 儲存社團成員學號，再用另一個集合 present 儲存非社團成員但有出席的人，最後將兩者的數量相減即可。

Python 程式碼

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

m, n = map(int, input().split())  # 社團人數 m，有到的人數 n
members = set([input() for _ in range(m)])  # 社團成員學號
present = set()  # 非社團成員但有出席的人
for _ in range(n):  # 讀取 n 行資料
    s = input()  # 學號
    if s in members: members.remove(s)  # s 是社團成員，從 members 移除 s
    else: present.add(s)  # s 不是社團成員，s 加入 present
print(len(members) - len(present))

ZeroJudge 解題筆記：g488. COVID-101

作者：王一哲
日期：2025年11月6日


ZeroJudge 題目連結：g488. COVID-101

解題想法

題目給的遞迴式為 $$ n(x) = n(x-1) + x^2 - x + 1 $$ 列出前幾項找規律 $$ \begin{align*} n(1) &= 1\\ n(2) &= n(1) + 2^2 - 2 + 1\\ n(3) &= n(2) + 3^2 - 3 + 1\\ n(4) &= n(3) + 4^2 - 4 + 1\\ n(5) &= n(4) + 5^2 - 5 + 1\\ n(x) &= n(x-1) + x^2 - x + 1 \end{align*} $$ 將以上的式子相加，可以看出 $n(1)$ 到 $n(x-1)$ 會兩兩對消，因此 $$ \begin{align*} n(x) &= (2^2 + 3^2 + 4^2 + \dots + x^2) - (2 + 3 + 4 + \dots + x) + x\\ &= \sum_{i = 1}^x i^2 - 1 - \sum_{i=2}^x i + x\\ &= \frac{x(x+1)(2x+1)}{6} - \frac{(x+2)(x-1)}{2} + x - 1 \end{align*} $$

Python 程式碼

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

x = int(input())
print(x*(x+1)*(2*x+1)//6 - (x+2)*(x-1)//2 + x - 1)

遞迴解，使用時間約為 42 ms，記憶體約為 3.3 MB，通過測試。

def func(x):
    if x == 1: return 1
    return func(x-1) + x*x - x + 1

print(func(int(input())))

ZeroJudge 解題筆記：g422. PD.紅血球的快遞任務

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


ZeroJudge 題目連結：g422. PD.紅血球的快遞任務

解題想法

這題考 Dijkstra’s Shortest Path Algorithm。

Python 程式碼

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

import heapq

n, m, t = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))
cost = [float('inf')]*n
cost[0] = 0
pq = [(0, 0)]  # (cost, node)
while pq:
    cur_cost, u = heapq.heappop(pq)
    if u == t: break  # 已經走到終點
    if cur_cost > cost[u]: continue  # 如果已經找到比較低的成本，找下一筆資料
    for v, w in graph[u]:  # 依序取出 u 的子節點 v、成本 w
        if cost[u] + w < cost[v]:  # 如果從 u 走到 v 的成本較低
            cost[v] = cost[u] + w
            heapq.heappush(pq, (cost[v], v))
print(cost[t])

ZeroJudge 解題筆記：g309. pC. 傳遞杯子蛋糕(Cupcake)

作者：王一哲
日期：2025年11月4日


ZeroJudge 題目連結：g309. pC. 傳遞杯子蛋糕(Cupcake)

解題想法

先讀取節點之間的關係，如果是 -1 代表沒有這個子節點。用串列 cnt 儲存每個節點分配到的數量，根節點先分到全部的數量 k。接下來用 BFS 走訪每個節點，計算要平分的數量 m 及平均值 avg。

Python 程式碼

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

from collections import deque

n, k = map(int, input().split())  # n 個節點，有 k 個東西要分配
tree = [[0, 0] for _ in range(n)]  # 節點的關係，i: [left, right]
for _ in range(n):  # 讀取 n 行資料
    i, left, right = map(int, input().split())
    tree[i] = [left, right]
cnt = [0]*(n)  # 各節點分配到的數量
cnt[0] = k  # 根節點先分到全部的數量
que = deque([0])  # 待走訪節點，先放入 0
while que:  # 若 que 還有資料繼續執行
    u = que.popleft()  # 從 que 開頭取出待走訪節點 u
    left, right = tree[u]  # u 的左節點、右節點
    m = 1 + (left != -1) + (right != -1)  # 共有 m 個點要平分數量，至少有 1 個點
    tot = cnt[u]  # 目前 u 節點擁有的數量
    avg = tot//m  # tot 除以 m 的平均值
    cnt[u] = avg + tot%m  # u 的數量改成 avg 加上 tot 除以 m 的餘數
    if left != -1:  # 如果有左子節點
        cnt[left] = avg; que.append(left)  # left 分到的數量為 avg，left 加入 que
    if right != -1:
        cnt[right] = avg; que.append(right)  # right 分到的數量為 avg，right 加入 que
print(*cnt)

ZeroJudge 解題筆記：g308. pB. 跳跳布朗尼(Brownie)

作者：王一哲
日期：2025年11月3日


ZeroJudge 題目連結：g308. pB. 跳跳布朗尼(Brownie)

解題想法

將傳送門狀態存入串列 portal，將每格的布朗尼數量存入串列 brownie。起始位置為 cur，會先拿到這格的布朗尼，更新拿到的布朗尼總數 cnt，再從 protal 讀取傳送的目的地 nxt，將用過的傳送門改成 -1。用 while 迴圈重複以上的過程，直到 nxt 為 -1 時停止。

Python 程式碼

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

n, t = map(int, input().split())
portal = list(map(int, input().split()))
brownie = list(map(int, input().split()))
cur = t  # 目前的位置
cnt = brownie[cur]  # 拿到的布朗尼總數，預設為目前位置的數量
brownie[cur] = 0  # 將目前位置的布朗尼總數歸零
nxt = portal[cur]  # 下一個位置
portal[cur] = -1  # 將目前位置要傳送的位置設成 -1，代表已經走過這格
while nxt != -1:  # 當 nxt 不等於 -1 時繼續執行
    cur = nxt  # 更新 cur
    cnt += brownie[cur]  # 加上目前位置的數量
    brownie[cur] = 0  # 將目前位置的布朗尼總數歸零
    nxt = portal[cur]  # 下一個位置
    portal[cur] = -1  # 將目前位置要傳送的位置設成 -1，代表已經走過這格
print(cnt)  # 印出答案

ZeroJudge 解題筆記：g307. pA. 為了好吃的蘋果派(Apple Pie)

作者：王一哲
日期：2025年11月2日


ZeroJudge 題目連結：g307. pA. 為了好吃的蘋果派(Apple Pie)

解題想法

依序讀取編號 i = 0 到 n-1 的分數，將分數排序後存入串列 scores，計算除了最高、最低分數以外的平均分數 avg，如果 avg 大於等於 t，將 i 存入答案之中。

Python 程式碼

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

n, k, t = map(int, input().split())
ans = []
for i in range(n):
    scores = sorted(map(int, input().split()))
    avg = sum(scores[1:-1])/(k-2)
    if avg >= t: ans.append(i)
if not ans:
    print("A is for apple.")
else:
    for a in ans:
        print(a)

ZeroJudge 解題筆記：g217. A.成雙成對（pairs）

作者：王一哲
日期：2025年11月1日


ZeroJudge 題目連結：g217. A.成雙成對（pairs）

解題想法

只要數量最多的數字不超過一半就可以符合要求。

Python 程式碼

collections.Counter 有一個很好用的功能 most_common，語法為

[Counter物件].most_common(數量)

回傳值格式為 list，串列中的資料格式為 tuple，內容為 (key, 數量)。使用時間約為 16 ms，記憶體約為 3.4 MB，通過測試。

from collections import Counter

t = int(input())
for _ in range(t):
    n = int(input())
    cnt = Counter(map(int, input().split()))
    imax = cnt.most_common(1)[0][1]
    print("Yes" if imax <= n//2 else "No")

ZeroJudge 解題筆記：f935. 消失的二十年 - 續

作者：王一哲
日期：2025年10月31日


ZeroJudge 題目連結：f935. 消失的二十年 - 續

解題想法

最低價 min_price 預設為第 0 天的價格，最大獲利 max_proift 預設為 0。依序讀取第 1 天到最後一天的價格 price，如果當天賣出的獲利大於目前的 max_profit，更新 max_profit、最低買價 buy、最高賣價 sell； 如果 price 小於 min_price，更新 min_price。最後如果找不到低於 min_price 的𧶠價，max_profit 等於 0，輸出 0 -1 -1； 反之，輸出 max_profit buy sell。

Python 程式碼

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

prices = list(map(int, input().split()))  # 每天的價格
min_price = prices[0]  # 最低價格，預設為第 0 天的價格
max_profit = 0  # 最大獲利，預設為 0
buy = sell = -1  # 最大獲利對應的最低買價、最高賣價，預設為 -1
for price in prices[1:]:  # 依序讀取讀取第 1 天到最後一天的價格
    if price - min_price > max_profit:  # 更高的獲利
        max_profit = price - min_price  # 更新最大獲利
        buy = min_price  # 更新最低買價
        sell = price  # 更新最高賣價
    elif price < min_price:  # 更低的價格
        min_price = price  # 更新最低價格
if max_profit == 0: print("0 -1 -1")
else: print(f"{max_profit:d} {buy:d} {sell:d}")

ZeroJudge 解題筆記：f929. 程式老師的作業

作者：王一哲
日期：2025年10月30日


ZeroJudge 題目連結：f929. 程式老師的作業

解題想法

這題如果直接用 index 或是 find 找陣列中第一個 0 的索引值，速度會太慢，無法通過最後一筆測資。用一個最小優先佇列儲存陣列中所有 0 的索引值，如果需要將第一個 0 改成指定的值時，從最小優先佇列取出開頭的資料就能找到要修改的索引值，速度快很多。

Python 程式碼

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

import sys, heapq

n = int(sys.stdin.readline())  # 陣列長度
arr = list(map(int, sys.stdin.readline().split()))  # 陣列內容
pq = [i for i, a in enumerate(arr) if a == 0]  # 所有 0 的索引值
m = int(sys.stdin.readline())  # m 次操作
lines = sys.stdin.readlines()  # 讀取所有剩下的資料
ans = []  # 答案
for line in lines:  # 依序讀取事先存在 lines 的資料
    cmd = list(map(int, line.split()))  # 指令
    if cmd[0] == 1:  # 如果指令開頭是 1
        if pq:  # 如果 pq 有資料
            idx = heapq.heappop(pq)  # 取出 pq 開頭的資料
            arr[idx] = cmd[1]  # 修改 arr[idx]
    elif cmd[0] == 2 and arr[cmd[1]] != 0:  # 如果指令開頭是 2 而且指定的位置不是 0
        arr[cmd[1]] = 0  # 將指定的位置改成 0
        heapq.heappush(pq, cmd[1])  # 將這個位置加入 pq
    elif cmd[0] == 3:  # 如果指令開頭是 3
        if pq: ans.append(str(pq[0]) + "\n")  # 如果 pq 有資料，將 pq 開頭的資料轉成字串加上 \n 存入 ans 
        else: ans.append("-1\n")  # 反之，將 -1\n 存入 ans
sys.stdout.write("".join(ans))  # 將 ans 的資料接成很長的字串再輸出

ZeroJudge 解題筆記：f928. 連環炸彈.................Boom！

作者：王一哲
日期：2025年10月29日


ZeroJudge 題目連結：f928. 連環炸彈.................Boom！

解題想法

這題的標籤是「遞迴」，不過我是用 BFS 解題。先讀取這格的炸彈種類 k，如果 k 等於 1 只會炸掉自己，如果 k 等於 2 再檢查左右兩格，如果 k 等於 3 則檢查左、右兩側距離 k 及 2k 的格子。檢查過的格子如果有炸彈，將炸彈加入待走訪佇列 que，再將檢查過的格子改成 0。

Python 程式碼

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

from collections import deque

n = int(input())
bombs = list(map(int, input().split()))
que = deque([int(input())])
while que:
    x = que.popleft()
    k = bombs[x]  # 暫存這格的值
    bombs[x] = 0  # 將這格歸零
    if k == 2:  # 如果 k 等於 2，檢查左、右兩格是否出界、是否有炸彈
        if x-1 >= 0 and bombs[x-1] != 0: que.append(x-1)
        if x+1 < n and bombs[x+1] != 0: que.append(x+1)
    elif k >= 3:  # 如果 k 大於等於 3，檢查左、右四格是否出界、是否有炸彈
        if x-k >= 0 and bombs[x-k] != 0: que.append(x-k)
        if x-k-k >= 0 and bombs[x-k-k] != 0: que.append(x-k-k)
        if x+k < n and bombs[x+k] != 0: que.append(x+k)
        if x+k+k < n and bombs[x+k+k] != 0: que.append(x+k+k)
print(*bombs)

ZeroJudge 解題筆記：f885. 加總

作者：王一哲
日期：2025年10月28日


ZeroJudge 題目連結：f885. 加總

解題想法

這題考數學，要先推導公式。首先用等差級數公式 $$ \frac{(n+a)(n-a+1)}{2} \geq x ~\Rightarrow~ n^2 + n - a^2 + a - 2x \geq 0 $$ 用公式解 $$ n = \frac{-1 \pm \sqrt{1^2 - 4 \times (-a^2 + a - 2x)}}{2} = \frac{-1 \pm \sqrt{4a^2 - 4a + 8x + 1}}{2} $$ 從範例測資來看，答案應該是正整數，因此上式的解要取正值，如果計算結果不是正整數，則用 math.ceil 向上取最接近的正整數。

Python 程式碼

這題有卡 I/O，如果每次計算完之後就用 print 印出答案，在最後一筆測資會超時。改用 sys.stdion.readlines() 一次讀取所有測資，再將所有的計算結果全部存進串列之中，最後再用 sys.stdout.write 及 join 合併要輸出的答案，盡量縮短運算時間。使用時間約為 0.3 s，記憶體約為 15.7 MB，通過測試。

import sys, math

lines = sys.stdin.readlines()
t = int(lines[0])
ans = []
for line in lines[1:]:
    a, x = map(int, line.split())
    ans.append(str(math.ceil((-1 + math.sqrt(4*(a**2) - 4*a + 8*x + 1))/2)) + "\n")
sys.stdout.write("".join(ans))

ZeroJudge 解題筆記：f884. 柏恩的奶茶

作者：王一哲
日期：2025年10月27日


ZeroJudge 題目連結：f884. 柏恩的奶茶

解題想法

這題考數學，要先推導公式。依照題意，給定某個正整數 $n$，要找到另一個正整數 $x$，使 $x(x+1)(x+2)(x+3) + 1 = x$。先化簡算式 $$ x(x+1)(x+2)(x+3) + 1 = x^4 + 6x^3 + 11x^2 + 6x + 1 = (x^2 + 3x + 1)^2 $$ 因此題目可以改為求 $$ (x^2 + 3x + 1)^2 = n $$ 因為題目要求 $n, x \in N$，所以 $n$ 一定是平方數，假設 $x^2 + 3x + 1 \equiv k$，則 $k = \sqrt{n}$。在程式碼之中，可以先檢查

k = math.isqrt(n)  # Python 3.11 之後的寫法，舊版可用 k = int(math.sqrt(n))
if k*k != n:
    print(-1); return

將題目由解一元四次方程化簡為解一元二次方程式 $$ x^2 + 3x + 1 - k = 0 $$ 判別式 $$ D = 3^2 - 4\times(1-k) = 5 + 4k $$ 因為 $x$ 要有正整數解，$D = 5 + 4k$ 為平方數，$\sqrt{D} = \sqrt{5 + 4k}$ 為奇數且大於 3。由公式解可得 $$ x = \frac{-3 + \sqrt{5 + 4k}}{2} = \frac{-3 + \sqrt{5 + 4 \sqrt{n}}}{2} $$ 在程式碼之中，可以先檢查

d = math.isqrt(5+4k)  # Python 3.11 之後的寫法，舊版可用 d = int(math.sqrt(5+4k))
if d*d != k:
    print(-1); return
if (5+4*k)%2 == 0 or 5+4*k <= 3:
    print(-1); return

最後將題目給的 $n$ 值代入公式求解。題目看起來保證測資一定有解，以上三個檢查是否有解的部分可以跳過，直接代公式求解。

Python 程式碼

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

import sys, math

for line in sys.stdin:
    n = int(line)
    x = (-3+int(math.sqrt(5 + 4*int(math.sqrt(n)))))//2
    print(x, x+1, x+2, x+3)

ZeroJudge 解題筆記：f822. 紅林愛下棋

作者：王一哲
日期：2025年10月26日


ZeroJudge 題目連結：f822. 紅林愛下棋

解題想法

這題分成兩個部分。首先依序掃過每一格，如果這格是 .，用 list 儲存待走訪佇列，假設目前區塊的顏色 color 為 X，用四方位檢查找周圍的格子 (nr, nc)，如果 (nr, nc) 是 B 或 W，設定 color 的值； 如果 color 已經是 B 或 W，但是 (nr, nc) 的顔色與 color 不同，錯誤，無法計算領地大小。找到連通區塊之後，將 que 裡的格子改成 color 的值。第二部分，再用二層 for 迴圈，計算黑、白棋數量。最後按照題目的要求輸出答案。

Python 程式碼

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

def solve():
    grid = [list(input()) + ["#"] for _ in range(9)]  # 地圖，在最右側、最下方加 # 作為哨兵
    grid.append(["#"]*10)
    for i in range(9):  # 依序掃過每一格
        for j in range(9):
            if grid[i][j] == ".":  # 如果此格是 .
                que = [(i, j)]  # 將 (i, j) 加到待走訪佇列 que
                head = 0  # 從 que 讀取資料的索引值
                color = "X"  # 目前區塊的顏色，預設為 X
                ### BFS ###
                while head < len(que):  # 如果 head 還沒有出界繼續執行
                    r, c = que[head]; head += 1  # 從 que 讀取待走訪位置，head 加 1
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                        if grid[nr][nc] == "#": continue  # 如果此格是邊界，找下一格
                        if (color == "B" and grid[nr][nc] == "W") or \  # 區塊顏色 B、此格顏色 W
                           (color == "W" and grid[nr][nc] == "B"):      # 區塊顏色 W、此格顏色 B
                                print("Wrong"); return  # 錯誤，離開函式
                        elif (color == "B" or color == "W") and grid[nr][nc] == ".":  # 區塊為 B 或 W，此格為 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                        elif color == "X":  # 如果區塊還沒有決定顏色
                            if grid[nr][nc] == ".":  # 如果此格是 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                            elif grid[nr][nc] == "B" or grid[nr][nc] == "W":  # 如果此格是 B 或 W
                                color = grid[nr][nc]  # 更新區塊顏色
                ### End of BFS ###
                for r, c in que: grid[r][c] = color  # 將 que 之中的位置填入對應的顏色
    ### 已掃過所有格子，計算黑、白棋數量 ###
    B, W = 0, 0  # 黑、白棋數量
    for i in range(9):
        for j in range(9):
            if grid[i][j] == "B": B += 1
            elif grid[i][j] == "W": W += 1
    ### 印出題目要求的答案 ###
    print("Black wins!!" if B > W else "White wins!!")
    print(f"{B:d}:{W:d}")
    for row in grid[:9]: print("".join(row[:9]))
### 主程式 ###
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：f821. nAnB ( 正常版 )

作者：王一哲
日期：2025年10月25日


ZeroJudge 題目連結：f821. nAnB ( 正常版 )

解題想法

這題的數字不會重複，寫起來簡單很多。假設數字、位置皆相同的數量為 a，數字相同、位置不同的數量為 b，依序讀取猜測字串中的每個字元，先比較這個字元與答案中同樣位置的字元是否相同，如果相同則 a 加 1；如果前一個條件不成立，再檢查這個數字是否在答案當中，如果有則 b 加 1。

Python 程式碼

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

ans, m = input().split()  # 正確答案，詢問筆數
n = len(ans)  # 答案的字數
for _ in range(int(m)):  # 執行 m 次
    guess = input()  # 猜測的數字
    a, b = 0, 0  # 數字、位置皆正確的數量，數字正確、位置錯誤的數量
    for i, c in enumerate(guess):  # 依序取出 guess 的數字
        if ans[i] == c: a += 1  # 數字、位置皆正確
        elif c in ans: b += 1  # 數字正確、位置錯誤
    print(f"{a:d}A{b:d}B")

ZeroJudge 解題筆記：f803. 質數篩法練習

作者：王一哲
日期：2025年10月24日


ZeroJudge 題目連結：f803. 質數篩法練習

解題想法

這題可以用埃拉托斯特尼篩法建質數表，再用二分搜尋找指定的質數在表中的索引值。

Python 程式碼

原來測試時，使用時間約為 2.5 s，記憶體約為 323.6 MB，通過測試。但是在2025年10月23日測試時，最後一筆測資超時，好像沒有為 Python 使用者放寬時間限制，仍然為 1 s。

from bisect import bisect_left

n, m = map(int, input().split())
states = [True]*n
states[0] = states[1] = False
for i in range(2, int(n**0.5) + 1):
    if states[i]:
        states[i+i::i] = [False]*len(states[i+i::i])
primes = [i for i, is_prime in enumerate(states) if is_prime]
for _ in range(m):
    print(bisect_left(primes, int(input())) + 1)

改用 sys 加速並修改內層 for 迴圈的寫法仍然超時。

import sys
from bisect import bisect_left

result = []
lines = sys.stdin.readlines()
n, m = map(int, lines[0].split())
sieve = [True]*n
sieve[0] = sieve[1] = False
for i in range(2, int(n**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, n, i):
            sieve[j] = False
primes = [int(i) for i in range(n) if sieve[i]]
idx = 1
while idx < len(lines):
    x = int(lines[idx])
    idx += 1
    pos = bisect_left(primes, x) + 1
    result.append(f"{pos:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：f787. 宇辰的閃電

作者：王一哲
日期：2025年10月23日


ZeroJudge 題目連結：f787. 宇辰的閃電

解題想法

這題想要考 C 及 C++ 的結構體 (struct)，自訂結構體 Player，用來儲存玩家的姓名、血量、被電時的傷害、下個目標玩家編號、道具清單。由於 Python 的 list 可以儲存不同格式的資料，而且 Python 沒有 struct，所以我直接用 list 儲存玩家資料。

Python 程式碼

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

n, s = map(int, input().split())  # n 位玩家，一開始的目標為 s
players = [[]]  # 玩家資料，開頭放一個空的，資料依序為
                # [名字, 血量, 被電時的傷害, [道具清單], 下個目標玩家編號]
for i in range(1, n+1): # 讀取 1 ~ n 號玩家資料
    line = input().split()
    players.append([line[0], int(line[1]), int(line[2]),
                   line[3:-1], int(line[-1])])
visited = [False]*(1+n)  # 1 ~ n 號玩家是否已被攻擊過
while not visited[s]:  # 如果 s 號玩家還沒有被攻擊過則繼續執行
    visited[s] = True  # s 號玩家已經被攻擊過
    if players[s][2] >= players[s][1]:  # 傷害大於等於血量
        print(f"{players[s][0]:s} dead.")  # 已陣亡
    else:  # 反之
        players[s][1] -= players[s][2]  # 扣血
        for _ in range(players[s][2]):  # 從最後面開始掉道具
            if players[s][3]: players[s][3].pop()
        print(f"{players[s][0]:s} {players[s][1]:d} ", end="")
        print(*players[s][3])
    s = players[s][4]  # 更新目標

因為玩家持有的道具數量等於血量，所以不需要考慮還沒有陣亡但是已經沒有道具的狀況，可以刪掉第15、16行，第18行改成以下這樣。使用時間約為 83 ms，記憶體約為 9.6 MB，通過測試。

print(*players[s][3][:-players[s][2]])

ZeroJudge 解題筆記：f731. 老鼠的直播間

作者：王一哲
日期：2025年10月22日


ZeroJudge 題目連結：f731. 老鼠的直播間

解題想法

這題與 APCS實作題2016年3月第3題：線段覆蓋長度 解題觀念相同，將所有時段的開始時間 start 與 1 組合成數組，結束時間 end 與 -1 組合成數組，將數組加到串列之中，再依照時間排序。接下來依序讀取時間，更新目前線上的人數及最大值。

Python 程式碼

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

n = int(input())  # n 個時段
segs = []  # 時刻與人數變化，(start, 1) 或 (end, -1)
for _ in range(n):  # 讀取 n 行資料
    start, end = map(int, input().split())
    segs += [(start, 1), (end, -1)]
segs.sort()  # 依照時刻排序
cnt, imax = 0, 0  # 目前的人數，最多人數
for t, c in segs:  # 依序讀取時刻與人數變化
    cnt += c  # 更新人數
    imax = max(imax, cnt)  # 更新 imax
print(imax) 

ZeroJudge 解題筆記：f716. 計算學期成績

作者：王一哲
日期：2025年10月21日


ZeroJudge 題目連結：f716. 計算學期成績

解題想法

換算的公式為 $$ y = 45 \times \frac{x-a}{b} + 55 $$ 假設原始成績最高分為 $imax$、最低分為 $imin$，換算後成績最高分為 $100$、最低分為 $55$，代入上式可得 $$ 100 = 45 \times \frac{imax-a}{b} + 55 ~~~~~ 55 = 45 \times \frac{imin-a}{b} + 55 $$ 由以上2式可得 $$ b = imax - a ~~~~~ a = imin $$

Python 程式碼

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

scores = tuple(map(int, input().split()))
a = min(scores)
b = max(scores) - a
print(a, b)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 92 kB，通過測試。2025年10月15日重測，使用時間約為 0 ms，記憶體約為 48 kB，通過測試。

#include <cstdio>

int main() {
    int imin = 1E9, imax = 0, score;
    while(scanf("%d", &score) != EOF) {
        if (score < imin) imin = score;
        if (score > imax) imax = score;
    }
    printf("%d %d\n", imin, imax - imin);
    return 0;
}

ZeroJudge 解題筆記：f701. 連接字詞

作者：王一哲
日期：2025年10月20日


ZeroJudge 題目連結：f701. 連接字詞

解題想法

這題沒有說明要讀取的單字數量，用 C++ 寫起來會比較麻煩，用 getline 搭配 stringstream 及 vector 會比較方便。

Python 程式碼

以前測試時使用時間約為 19 ms，記憶體約為 3.3 MB。ZeroJudge 網站好像在 2025年10月更新過，同樣的程式碼使用時間約為 6 ms，記憶體約為 3 MB。

words = list(input().split())
conjuction = input()
n = len(words)
for i in range(n-1):
    print(f"{words[i]:s} {conjuction:s} ", end="")
print(words[-1])

可以用 join 將 " 連接詞 " 與串列 words 的內容接成一個字串再輸出，使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

words = list(input().split())
conjuction = input()
print(f" {conjuction} ".join(words))

ZeroJudge 解題筆記：f699. 品嘉的茶葉蛋

作者：王一哲
日期：2025年10月19日


ZeroJudge 題目連結：f699. 品嘉的茶葉蛋

解題想法

標準的 BFS 題目。因為不想檢查是否出界，我在地圖周圍加上 2 作為哨兵。另外開一個陣列儲存步數。

Python 程式碼

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

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m，最右側、最下方加上 2 作為哨兵
grid = [list(map(int, input().split())) + [2] for _ in range(n)]
grid.append([2]*(m+1))  # 最下方加 m+1 個 2
steps = [[0]*m for _ in range(n)]  # 記錄步數用的二維串列
ans = []  # 答案
que = deque([(0, 0)])  # 待走訪佇列
grid[0][0] = 2  # (0, 0) 設定為 2
while que:  # 如果 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
        if grid[nr][nc] == 2: continue  # 如果此格是 2 找下一格
        steps[nr][nc] = steps[r][c] + 1  # (nr, nc) 的步數為 (r, c) 的步數加 1
        if grid[nr][nc] == 1: ans.append(steps[nr][nc])  # 如果此格是 1，將 (nr, nc) 的步數加入 ans
        grid[nr][nc] = 2  # 此格設定為 2
        que.append((nr, nc))  # (nr, nc) 加入 que
if not ans: print("嘉油！")  # 沒有找到茶葉蛋
else:  # 有找到茶葉蛋，印出 ans 的內容
    for a in ans: print(a)

ZeroJudge 解題筆記：f680. 色塊數量

作者：王一哲
日期：2025年10月18日


ZeroJudge 題目連結：f680. 色塊數量

解題想法

標準的 BFS 題目。

Python 程式碼

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

from collections import deque

n = int(input())  # 地圖 n*n，最右側、最下方加上 0 作為哨兵
grid = [list(map(int, input().split())) + [0] for _ in range(n)]
grid.append([0]*(n+1))
### BFS ###
cnt = 0  # 色塊數量
for i in range(n):  # 依序掃過每一格
    for j in range(n):
        if grid[i][j] == 0: continue  # 如果此格是 0 找下一格
        color = grid[i][j]  # 此格的顏色
        grid[i][j] = 0  # 此格設定為 0
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列
        cnt += 1  # 色塊數量加 1
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭讀取並移除資料
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] != color: continue  # 如果此格顏色不一樣，找下一格
                grid[nr][nc] = 0  # 此格設定為 0
                que.append((nr, nc))  # (nr, nr) 加入待走訪佇列
### End of BFS ###
print(cnt)  # 印出答案

ZeroJudge 解題筆記：f647. 撲克牌

作者：王一哲
日期：2025年10月17日


ZeroJudge 題目連結：f647. 撲克牌

解題想法

我用串列儲存牌組，先用 for 迴圈産生按照花色、數字排列好的 52 張牌，接下來依照指令用串列切片修改內容。

Python 程式碼

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

deck = [""]*52
suits = ('S', 'H', 'D', 'F')
akqj = {1: 'A', 13: 'K', 12: 'Q', 11: 'J'}
for i in range(4):
    for j in range(1, 14):
        if 2 <= j <= 10: deck[i*13 +j-1] = suits[i] + str(j)
        else: deck[i*13 + j-1] = suits[i] + akqj[j]
n = int(input())
for _ in range(n):
    line = input().split()
    if line[0] == '1':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[a:b+1] + deck[:a] + deck[b+1:]
    elif line[0] == '2':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[:a] + deck[b+1:] + deck[a:b+1]
    elif line[0] == '3':
        k = int(line[1])
        deck = deck[52-k:] + deck[:52-k]
    else:
        k = int(line[1])
        deck = deck[k:] + deck[:k]
print(*deck[:5])

ZeroJudge 解題筆記：f634. 士兵歸來

作者：王一哲
日期：2025年10月16日


ZeroJudge 題目連結：f634. 士兵歸來

解題想法

我用集合 uni 儲存存活者的姓名、軍種、階級，再用另外兩個陣列 services、ranks 儲存各軍種、階級存活者的數量，用 cnt 儲存存活者總數。讀取 m 行資料之後，再依照題目要求的格式輸出答案。

Python 程式碼

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

n, m = map(int, input().split())  # 共派出 n 人，有 m 行資料
uni = set()  # (姓名 name, 軍種 service, 階級 rank)
services = [0]*4  # 海、陸、空軍存活人數，開頭有用不到的 0
ranks = [0]*4  # 軍官、士官、士兵存活人數，開頭有用不到的 0
cnt = 0  # 存活人數
for _ in range(m):  # 執行 m 次
    data = tuple(input().split())
    if data not in uni:  # 這筆資料組合不在 uni 之中，新的存活者
        uni.add(data)  # data 加入 uni
        cnt += 1  # 存活人數加 1
        services[int(data[1])] += 1  # 對應的軍種人數加 1
        ranks[int(data[2])] += 1  # 對應的階級人數加 1
print(f"navy:{services[1]:d} army:{services[2]:d} air:{services[3]:d}")
print(f"officer:{ranks[1]:d} sergeant:{ranks[2]:d} soldier:{ranks[3]:d}")
print(f"survival rate: {100.0*cnt/n:.1f}%")

ZeroJudge 解題筆記：f632. 渡船頭

作者：王一哲
日期：2025年10月15日


ZeroJudge 題目連結：f632. 渡船頭

解題想法

先讀取所有的乘客資料，在結束營業之前到的人才加入串列 passenger 之中，接下來依照時間由小到大排序。另外開一個最大優先佇列，儲存目前乘客會給的小費。再用一個 for 迴圈依序産生出發時刻，讀取當時已到站的乘客資料，將乘客會給的小費存入 pq 之中；再從 pq 取出資料加到利潤 profit 之中，直到 pq 沒有資料或是這趟人數到達上限為止。

Python 程式碼

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

import sys, heapq

t1, t2, k, p = map(int, sys.stdin.readline().split())  # 營業時間，間距，每趟人數
passenger = []  # 乘客到站時間、小費
for line in sys.stdin:  # 讀取資料直到 EOF 為止
    if line.strip() == "": continue  # 如果讀到空行，找下一行
    t, m = map(int, line.split())  # 這個乘客的到站時間、小費
    if t <= t2: passenger.append((t, m))  # 在結束營業之前到的人才加入
passenger.sort()  # 依照時間排序
tot, profit, idx, n = 0, 0, 0, len(passenger)  # 總載客人數，總收入，從 passenger 讀資料的索引值，人數
pq = []  # 存入目前乘客小費的優先佇列
for dep in range(t1, t2+1, k):  # 依序産生出發時刻
    while idx < n:  # 如果 idx 還沒有出界繼續執行
        t, m = passenger[idx]  # 到站時間、小費
        if t <= dep: heapq.heappush(pq, -m)  # 如果 t 小於等於發車時刻，m 加負號再加入 pq
        else: break  # 否則中止迴圈
        idx += 1  # idx 加 1
    cnt = 0  # 這趟已載人數
    while pq and cnt < p:  # 如果 pq 還有資料而且還沒有載滿
        profit += -heapq.heappop(pq)  # 從 pq 讀取並移除首項，轉為正值加到 profit
        cnt += 1; tot += 1  # 更新人數
print(tot, profit)  # 印出答案

ZeroJudge 解題筆記：f631. 同學會

作者：王一哲
日期：2025年10月14日


ZeroJudge 題目連結：f631. 同學會

解題想法

這題要用最大優先佇列儲存每個人目前有的錢，由於 Python 的 heapq 是最小優先佇列，要將每一筆資料都加上負號。

Python 程式碼

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

import sys, heapq

for line in sys.stdin:  # 繼續執行直到 EOF 為止
    if line.strip() == "": continue  # 遇到空行，找下一行
    n, m = map(int, line.split())  # n 個人，m 道菜
    money = list(map(int, sys.stdin.readline().split()))  # 每個人原來的錢
    dishes = list(map(int, sys.stdin.readline().split()))  # 每道菜的價格
    if sum(money) < sum(dishes):  # 所有人帶的錢小於所有菜的總價
        print("Oh My God")  # 印出 Oh My God
        continue  # 讀下一筆資料
    pq = [-m for m in money]  # 將 money 每一筆資料加負號存入 pq
    heapq.heapify(pq)  # pq 轉成最小優先佇列
    imax = -pq[0]  # 初始金額最大值
    for dish in dishes:  # 依序讀取每道菜的價格
        while pq and dish > 0:  # 當 pq 還有資料而且 dish 大於 0 時繼續執行
            m = -heapq.heappop(pq)  # 取出 pq 第一項加負號，變回正值
            if m > dish:  # 如果付完這道菜還有錢
                heapq.heappush(pq, -(m-dish))  # 剩下的錢加負號，存入 pq
                dish = 0  # 待付金額為 0
            elif m == dish: dish = 0  # 如果這個人的錢剛好夠用，待付金額為 0
            else: dish -= m  # 如果這個人的錢不夠，更新待付金額
    print(imax, -pq[0] if pq else 0)  # 印出 imax，如果 pq 有資料印出 -pq[0]，反之印出 0

ZeroJudge 解題筆記：f493. 水窪問題

作者：王一哲
日期：2025年10月13日


ZeroJudge 題目連結：f493. 水窪問題

解題想法

這類型的題目我習慣用 BFS 解題，已走訪的位置改成題目給的陸地符號 #，不需要另外開一個陣列儲存已走訪的位置，可以節省一些記憶體。

Python 程式碼

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

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m
grid = [list(input() + "#") for _ in range(n)]  # 讀取地圖資料，右側加上 #
grid.append(["#"]*(n+1))  # 最下方加上 n+1 個 #
cnt, imin, imax = 0, float('inf'), 0  # 數量，最小面積、最大面積
### BFS ###
for i in range(n):  # 依序掃過每一格
    for j in range(m):
        if grid[i][j] == "#": continue  # 如果是 #，找下一格
        grid[i][j] = "#"  # 此格改成 #
        cnt += 1  # 數量加 1
        area = 0  # 這個水漥的面積
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列 que
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭取出座標 (r, c)
            area += 1  # 面積加 1
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] == "#": continue  # 如果是 #，找下一格
                grid[nr][nc] = "#"  # 此格改成 #
                que.append((nr, nc))  # (nr, nc) 加入 que
        imin = min(imin, area)  # 更新 imin
        imax = max(imax, area)  # 更新 imax
### 結束 BFS ###
if cnt == 0:  # 如果 cnt 等於 0，印出 0 0 0
    print("0 0 0")
else:  # 反之印出 imax, imin, cnt
    print(imax, imin, cnt)

ZeroJudge 解題筆記：f455. 詠竣的哀鳳12

作者：王一哲
日期：2025年10月12日


ZeroJudge 題目連結：f455. 詠竣的哀鳳12

解題想法

這題是背包問題，用動態規畫處理，但是用 Python 好像沒辦法通過。

Python 程式碼

只能通過 60% 的測資。

t, n = map(int, input().split())  # 總時數 t，工作數量 n
dp = [0]*(t+1)  # 總時數 0 ~ t 對應的最大收入
work = ""  # 最高時薪的工作名稱
imax = 0.0  # 最高時薪
for _ in range(n):  # 執行 n 次
    s, m, h = input().split()  # 工作名稱，收入，需要的時間
    m = int(m); h = int(h)  # m, h 轉為 int
    mph = 1.0*m/h  # 時薪
    if mph > imax:  # 如果時薪較高，更新 imax, work
        imax = mph; work = s
    if h > t: continue  # 如時需要的時間大於 t，不能接工作，找下一筆
    for i in range(t, h-1, -1):  # 倒著更新 dp[t] ~ dp[h]
        dp[i] = max(dp[i], dp[i-h] + m)  # 如果接這個工作總收入變高則更新 dp[i]
print(dp[-1])  # 最高總收入在 dp[t-1], dp[-1]
print(work)  # 印出最高時薪的工作名稱

ZeroJudge 解題筆記：f418. Word Search Puzzle

作者：王一哲
日期：2025年10月11日


ZeroJudge 題目連結：f418. Word Search Puzzle

解題想法

這題我用二維陣列儲存英文字謎資料，再依照測資給的 r1, c1 及 r2, c2 判斷要向右、向下或是向右下方找答案。

Python 程式碼

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

h, w, r1, c1, r2, c2 = map(int, input().split())
r1 -= 1; c1 -= 1; r2 -=1; c2 -= 1  # 題目的座標從 1 開始
grid = [list(input()) for _ in range(h)]
if r1 == r2:  # 同一列，向右找
    print("".join(grid[r1][c1:c2+1]))
elif c1 == c2:  # 同一欄，向下找
    print("".join([grid[i][c1] for i in range(r1, r2+1)]))
else:  # 向右下方找
    print("".join([grid[r1+i][c1+i] for i in range(r2-r1+1)]))

ZeroJudge 解題筆記：f410. 芝麻街的郵件投遞

作者：王一哲
日期：2025年10月10日


ZeroJudge 題目連結：f410. 芝麻街的郵件投遞

解題想法

這題考排序，自訂比較式，先排單、雙號，雙號放前面、單號放後面，雙號門牌再由小到大排序，單號門牌再由大到小排序。

Python 程式碼

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

from functools import cmp_to_key

def mycmp(a, b):
    if a%2 == 0 and b%2 == 0:
        if a < b: return -1
        elif a > b: return 1
        else: return 0
    elif a%2 == 1 and b%2 == 1:
        if a > b: return -1
        elif a < b: return 1
        else: return 0
    elif a%2 == 0 and b%2 == 1: return -1
    elif a%2 == 1 and b%2 == 0: return 1
    else: return 0

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = cmp_to_key(mycmp))
print(*arr)

ZeroJudge 解題筆記：f408. 迷你蘋菓鎮

作者：王一哲
日期：2025年10月9日


ZeroJudge 題目連結：f408. 迷你蘋菓鎮

解題想法

將所有的門牌依照絕對值排序，再依序掃過每一個門牌，如果跟相鄰的門牌相乘小於 0 則答案加 1。

Python 程式碼

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

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = lambda x : abs(x))
cnt = 0
for i in range(1, n):
    if arr[i-1] * arr[i] < 0:
        cnt += 1
print(cnt)

ZeroJudge 解題筆記：f376. 芝麻街的團購

作者：王一哲
日期：2025年10月8日


ZeroJudge 題目連結：f376. 芝麻街的團購

解題想法

這題的測資不大，可以真的計算以每個點為中心的總距離，再找其中的最小值。實際上答案就是取中位數。

Python 程式碼

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

n = int(input())
psum = [0] + list(map(int, input().split()))
psum.sort()
for i in range(1, n+1): psum[i] += psum[i-1]
imin = float('inf')
ans = 0
for i in range(1, n+1):
    dis = (2*i-n-1)*(psum[i] - psum[i-1]) - psum[i-1] + psum[n] - psum[i]
    if dis < imin:
        imin = dis
        ans = psum[i] - psum[i-1]
print(ans)

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

n = int(input())
arr = sorted(list(map(int, input().split())))
print(arr[n//2] if n%2 else arr[n//2 - 1])

ZeroJudge 解題筆記：f348. 完全偶數

作者：王一哲
日期：2025年10月7日


ZeroJudge 題目連結：f348. 完全偶數

解題想法

我先寫一個函式 check 判斷輸入的整數 n 是否每一位都是偶數；再寫另一個函式 solve，找最接近 n 的完全偶數距離。

Python 程式碼

簡單但較慢的寫法，循序搜尋，使用時間約為 30 ms，記憶體約為 3 MB，通過測試。

def check(n):  # 檢查輸入的整數是否每一位都是偶數
    while n:
        if n%10%2 == 1:
            return False
        n //= 10
    return True

def solve(n):  # 輸入整數，找最接近的完全偶數距離
    if check(n): return 0  # 特例，n 是完全偶數，回傳 0
    lower, upper, cnt = n-1, n+1, 0  # 往下找、往上找、次數
    while True:  # 找到答案為止
        cnt += 1  # 次數加 1
        if check(lower): return cnt  # 如果 lower 是完全偶數，回傳 cnt
        if check(upper): return cnt  # 如果 uper 是完全偶數，回傳 cnt
        lower -= 1; upper += 1  # lower 減 1，upper 加 1
    return -1  # 預設的回傳值，用不到

print(solve(int(input())))

ZeroJudge 解題筆記：f332. 貝瑞的鐵線體積

作者：王一哲
日期：2025年10月6日


ZeroJudge 題目連結：f332. 貝瑞的鐵線體積

解題想法

如果函數為 $y = f(x)$，將此函數曲線以 $x$ 軸為轉軸旋轉，旋轉體體積為 $$ V = \pi \int_a^b y^2 dx $$

Python 程式碼

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

import math

t = int(input())  # 共 t 筆測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 多項式最高次方
    poly = list(map(int, input().split()))  # 多項式由高到低次方各項係數
    square = [0]*(2*n + 1)  # 多項式平方各項係數
    for i in range(n+1):
        for j in range(n+1):
            square[i+j] += poly[i]*poly[j]
    integral = [0]*(2*n + 1)  # 平方後積分結果，忽略常數項
    for i in range(2*n + 1):  # 計算積分式
        integral[i] = 1.0 * square[i] / (2*n + 1 - i)
    ans = 0.0  # 積分結果
    a, b = map(int, input().split())  # 積分下限、上限
    for i, c in enumerate(integral):  # 代入積分下限、上限
        ans += c * (b**(2*n + 1 - i) - a**(2*n + 1 - i))
    print(f"{math.pi*ans:.2f}")  # 印出答案時再乘以 pi

ZeroJudge 解題筆記：f291. 試算表大小

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


ZeroJudge 題目連結：f291. 試算表大小

解題想法

先將讀到的字串拆成左側字母、右側數字兩個部分，再從字母最後面往回讀取，計算是第幾欄，再將欄數乘以列數就是答案。

Python 程式碼

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

s = input()  # 輸入的儲存格編號
left = ""  # 左半邊的欄位
row = 0  # 列數
for i, c in enumerate(s):  # 依序讀取 s 的字元
    if c.isdigit():  # 如果 c 是數字，取出左半邊，中止迴圈
        left = s[:i]
        row = int(s[i:])
        break
b = 1  # 計算欄位的基底
col = 0  # 欄位編號
for c in left[::-1]:  # 從 left 最後面讀取字元
    col += b*(ord(c) - ord('A') + 1)  # 計算欄位
    b *= 26  # 基底乘以 26
print(row*col)  # 答案是列、欄相乘

ZeroJudge 解題筆記：f260. 愛八卦的同學

作者：王一哲
日期：2025年10月4日


ZeroJudge 題目連結：f260. 愛八卦的同學

解題想法

我用 BFS 找連通區塊數量，不過用 Python 的速度太慢，用 C++ 解題也要 0.3 s。

Python 程式碼

速度太慢，只能通過一筆測資。

import sys
from collections import deque

for line in sys.stdin:
    n, k = map(int, line.split())  # n 個人，k 組關係
    adj = [[] for _ in range(n)]  # 每個人與其它人的關係
    for _ in range(k):  # 讀取 k 行資料
        u, v = map(int, sys.stdin.readline().split())  # u, v 是朋友
        adj[u].append(v)
        adj[v].append(u)
    cnt = 0  # 小團體數量
    visited = [False]*n  # 是否已經檢查過
    for i in range(n):  # 依序讀取每一個人
        if visited[i]: continue  # 如果 i 已經檢查過，找下一個人
        visited[i] = True  # 設定為 True
        cnt += 1
        que = deque([i])
        while que:
            v = que.popleft()
            for u in adj[v]:
                if visited[u]: continue
                que.append(u)
                visited[u] = True
    print(cnt)

ZeroJudge 解題筆記：f257. 君王的處刑遊戲

作者：王一哲
日期：2025年10月3日


ZeroJudge 題目連結：f257. 君王的處刑遊戲

解題想法

我是用二維陣列儲存每一個人的驚恐值，預設值為 0，-1 代表已淘汰，Python 的最右側、最下方加上 -1 當作哨兵，C++ 周圍加上 -1 當作哨兵。每次檢查位置 (x, y) 的人，如果還沒有淘汰就設定成 -1，再檢查周圍 8 格，遇到還沒有被淘汰的人就將驚恐值加 1。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 二維陣列 n*n
    grid = [[0]*n + [-1] for _ in range(n)]  # 最右側、最下方加 -1 當作哨兵
    grid.append([-1]*(n+1))
    k = int(sys.stdin.readline())  # 要淘汰的人數
    for _ in range(k):  # 執行 k 次
        x, y = map(int, sys.stdin.readline().split())  # 要淘汰的人位置 (y, x)
        if grid[y][x] == -1: continue  # 已淘汰，找下一個
        grid[y][x] = -1  # 已淘汰，設定成 -1
        # 搜尋四周的 8 格
        for dy, dx in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
            ny, nx = y+dy, x+dx  # 檢查 grid[ny][nx]
            if grid[ny][nx] == -1: continue  # 已淘汰，找下一個
            grid[ny][nx] += 1  # 周圍的人驚恐值加 1
    # 執行完畢，要印出答案，不能印出最右側、最下方的哨兵，-1 要換成 x
    for row in grid[:n]:
        print("".join([str(i) if i != -1 else "x" for i in row[:n]]))

ZeroJudge 解題筆記：f164. 萬球同心移位之章

作者：王一哲
日期：2025年10月2日


ZeroJudge 題目連結：f164. 萬球同心移位之章

解題想法

這題絕對不要真的用鏈結串列解題，因為要找到鏈結串列中指定的值只能從頭開始依序往下找，一定會超時。用兩個陣列儲存每一個節點的左、右節點編號，移動節點時只要修改對應的節點編號即可。

Python 程式碼

最後一筆測資記憶體爆掉。

n, m, q = map(int, input().split())  # n 顆球，m 次操作，q 次查詢
pre = [(i-1+n)%n for i in range(n)]  # 每顆球的前一顆球
nxt = [(i+1)%n for i in range(n)]  # 每顆球的後一顆球
for _ in range(m):  # 執行 m 次
    d, a, b = input().split()  # 方向 d，a 球移到 b 球旁邊
    if a == b: continue  # 如果 a 等於 b，不移動
    a = int(a); b = int(b)  # 轉成整數
    nxt[pre[a]] = nxt[a]  # a 原來左側的球接到 a 原來右側的球
    pre[nxt[a]] = pre[a]  # a 原來右側的球接到 a 原來左側的球
    if d == 'R':  # 逆向
        le = pre[b]  # 暫存 b 原來左側的球
        nxt[le] = a  # b 原來左側的球接到 a
        pre[b] = a  # b 的左側接到 a
        pre[a] = le  # a 左側接到 le
        nxt[a] = b  # a 右側接到 b
    else:  # 順向
        ri = nxt[b]  # 暫存 b 原來右側的球
        pre[ri] = a  # b 原來右側的球接到 a
        nxt[b] = a  # b 的右側接到 a
        pre[a] = b  # a 的左側接到 b
        nxt[a] = ri  # a 的右側接到 ri
arr = tuple(map(int, input().split()))
for a in arr[:-1]: print(pre[a], nxt[a], end=" ")
print(pre[arr[-1]], nxt[arr[-1]])

ZeroJudge 解題筆記：e984. 連假時在做什麼？有沒有空？可以來打code嗎？

作者：王一哲
日期：2025年10月1日


ZeroJudge 題目連結：e984. 連假時在做什麼？有沒有空？可以來打code嗎？

解題想法

用一個自訂函式 find_lln 找第 k 項的 LunlunNumber。在函式中用一個 deque 儲存待處理的數字，先放入 1 ~ 9，再用一個 while 迴圈，當 que 還有資料繼續執行；在迴圈中每次取出 que 開頭的數字存入 num，計數器 cnt 數量加 1，如果 cnt 等於 k，已經找到答案，回傳 num；如果 cnt 小於 k，取出 num 的個位數 last_digit，計算 last_digit 加減 1、不變、加 1 的數值 next_digit，如果 next_digit 在 1 到 9 之中，將新的數值加入 que 之中。

Python 程式碼

單筆測資，使用時間約為 2 s，記憶體約為 93.2 MB，通過測試。

from collections import deque

def find_lln(k):  # 找第 k 位的 Lunlun Number
    que = deque([i for i in range(1, 10)])  # 待處理的數字，先放入 1 ~ 9
    cnt = 0  # 計數器
    while que:  # 當 que 還有資料繼續執行
        num = que.popleft()  # 取出 que 開頭的數字
        cnt += 1  # 計數器加 1
        if cnt == k:  # 如果是第 k 位
            return num  # 回傳 num 並離開函式
        last_digit = num%10  # 取出個位數
        for delta in (-1, 0, 1):  # 個位數的差值 -1, 0, 1
            next_digit = last_digit + delta  # 下一個個位數值
            if 0 <= next_digit <= 9:  # 如果在 0 ~ 9 之間
                que.append(num*10 + next_digit)  # 新的數值加入 que
    return 0  # 預設的回傳值，理論上不會用到

print(find_lln(int(input())))

ZeroJudge 解題筆記：e698. OREOREO!

作者：王一哲
日期：2025年9月30日


ZeroJudge 題目連結：e698. OREOREO!

解題想法

我先計算 O 的部分較寬及 RE 的部分較寬兩種狀況下，分別要印出的 O 及 RE 的字串。接下來讀取 n 塊餅乾的組成方式，依序輸出每一塊餅乾對應的形狀。

Python 程式碼

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

import sys

for line in sys.stdin:
    w1, h1 = map(int, line.split())
    w2, h2 = map(int, sys.stdin.readline().split())
    c1, c2 = sys.stdin.readline().split()
    if w1 > w2:  # O 的部分較寬
        O = c1*w1
        RE = " "*((w1-w2)//2) + c2*w2
    else:  # RE 的部分較寬
        O = " "*((w2-w1)//2) + c1*w1
        RE = c2*w2
    n = int(sys.stdin.readline())  # 接下來有 n 塊餅乾
    for _ in range(n):  # 執行 n 次
        cookie = sys.stdin.readline().strip()  # 餅乾的組成
        i = 0  # 從 cookie 讀取資料用的索引值
        while i < len(cookie):  # 如果 i 還沒有出界時繼續執行
            if cookie[i] == "O":  # 如果是 O
                for _ in range(h1): print(O)  # 印出 h1 行的 O
                i += 1  # i 加 1
            elif cookie[i] == "R":  # 如果是 RE
                for _ in range(h2): print(RE)  # 印出 h2 行的 RE
                i += 2  # i 加 2
        print()  # 跑完一塊餅乾要換行

ZeroJudge 解題筆記：e623. 2. PPAP

作者：王一哲
日期：2025年9月29日


ZeroJudge 題目連結：e623. 2. PPAP

解題想法

先用一個 while 迴圈，計算序號 n 是第 m 輪領到東西，計算時每一輪會將 n 減去這一輪的數量。跑完 while 迴圈之後，如果 n 等於 0，代表是第 m 輪的最後一個人，印出 Pineapple pen； 反之進到下一輪，先將 m 加 1，計算 n 對 m 取整數除法的結果，輸出對應的物品名稱。

Python 程式碼

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

n = int(input())  # 編號
m = 0  # 第 m 輪
s = 0  # 第 m 輪的數量，每次加 4
while n >= s+4:  # 如果 n 的數量大於等於 s+4，還有下一輸，繼續執行
    m += 1; s += 4  # m 加 1；s 加 4
    n -= s  # n 減去 s

if n == 0:  # 剛好是第 m 輪的最後一個人
    print("Pineapple pen")  # 印出 Pineapple pen
else:  # 要再到下一輪
    m += 1  # m 加 1
    if n%m == 0: n -= 1
    item = n // m
    if item == 0: print("Pen")
    elif item == 1: print("Pineapple")
    elif item == 2: print("Apple")
    else: print("Pineapple pen")

ZeroJudge 解題筆記：e622. 3. 虛擬寵物大師 (Master)

作者：王一哲
日期：2025年9月28日


ZeroJudge 題目連結：e622. 3. 虛擬寵物大師 (Master)

解題想法

我另外寫兩個函式，函式 ivcp 輸入 iv 值，回傳升級時增加的 cp 值；函式 upgrade 輸入原有的星塵沙子數量 star，iv 值、原來的 cp 值，計算升級後的 cp 值。

Python 程式碼

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

# 輸入 iv 值，回傳升級時增加的 cp 值
def ivcp(iv):
    if 0 <= iv <= 29: return 10
    elif 30 <= iv <=39: return 50
    elif 40 <= iv <= 45: return 100

# 輸入原有的星塵沙子數量 star，iv 值、原來的 cp 值，計算升級後的 cp 值
def upgrade(star, iv, cp):
    while star >= 1000:
        star -= 1000
        cp += ivcp(iv)
    return cp

# 解題過程
n, s = map(int, input().split())  # 寵物數量 n，原有的星塵沙子數量 s
imax, idx = 0, 0  # 升級後最高的 cp 值及寵物編號
for i in range(1, n+1):  # 讀取 n 行資料
    c, v = map(int, input().split())  # 讀取原來的 cp 值、iv 值
    re = upgrade(s, v, c)  # 呼叫 upgrade，代入 s, v, c，計算升級後的 cp 值
    if re > imax:  # 如果 re 大於 imax
        imax = re  # 更新 imax
        idx = i  # 更新 idx
print(f"{idx:d} {imax:d}")  # 印出答案

ZeroJudge 解題筆記：e621. 1. 免費停車 (Free Parking)

作者：王一哲
日期：2025年9月27日


ZeroJudge 題目連結：e621. 1. 免費停車 (Free Parking)

解題想法

這題應該是多行測資，但是題目沒有說清楚。讀取測資中的 A、B、C 三個數字之後，用 for 迴圈跑 i = A-1 到 i = B-1，當 i 不能被 C 整除就加入答案之中。

Python 程式碼

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

import sys

for line in sys.stdin:
    N = int(line)
    for _ in range(N):
        A, B, C = map(int, input().split())
        ans = []
        for i in range(A+1, B):
            if i%C != 0: ans.append(i)
        if ans: print(*ans)
        else: print("No free parking spaces.")

ZeroJudge 解題筆記：e494. 無窮級數之和(二)

作者：王一哲
日期：2025年9月26日


ZeroJudge 題目連結：e494. 無窮級數之和(二)

解題想法

這題考數學及大數運算，所以我只有寫 Python 版本。公式解 $$ \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots + \frac{1}{p} = \ln(\ln p) + M = \ln(\ln p) + 0.2614972128476427837554268386 $$ 由於輸出的小數位數很多，甚至要用到 decimal 函式庫的浮點數物件 Decimal 才行。

Python 程式碼

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

import sys, decimal

def solve(n):
    decimal.getcontext().prec = 1000  # 設定小數位數
    p = decimal.Decimal(n)  # 用 Decimal 格式的浮點數
    if p == decimal.Decimal(2):  # 特例，n 等於 2，回傳 0.5
        return decimal.Decimal('0.5')
    # 公式解，ln(ln(n)) + M
    ln_ln_p = p.ln().ln()
    M = decimal.Decimal('0.2614972128476427837554268386')
    return round(ln_ln_p + M, 3)

for line in sys.stdin:
    print(f"{solve(decimal.Decimal(line)):.3f}")

ZeroJudge 解題筆記：e484. 我是優質學生

作者：王一哲
日期：2025年9月25日


ZeroJudge 題目連結：e484. 我是優質學生

解題想法

這題要判斷輸入的數字是否為 2 到 10000 之間的質數，由於輸入只有一行，不要建質數表，直接判斷這個數是否為質數就好。

Python 程式碼

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

def is_prime(n):  # 判斷是否為質數
    if n <= 1: return False  # 特例，小於等於1，回傳 False
    if n == 2 or n == 3: return True  # 特例，等於 2 或 3，回傳 True
    if n%2 == 0 or n%3 == 0: return False  # 特例，可以被 2 或 3 整除，回傳 False
    for i in range(5, int(n**0.5)+1, 6):  # 依序檢查 5 ~ sqrt(n)，每次加 6
        if n%i == 0 or n%(i+2) == 0:  # 如果可以被 i 或 i+2 整除，回傳 Fasle
            return False
    return True  # 最後回傳 True

print("yes" if is_prime(int(input())) else "no")

ZeroJudge 解題筆記：e470. 無窮級數之和(一)

作者：王一哲
日期：2025年9月24日


ZeroJudge 題目連結：e470. 無窮級數之和(一)

解題想法

這題考數學，當 $n$ 很大時，有近似公式 $$ \sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + \frac{1}{2n} $$ 其中 $\gamma = 5772156649$。

Python 程式碼

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

import sys, math

def harmonic_number(n):
    if n <= 20:  # 如果 n 小於等於 20，直接用迴圈計算
        isum = 0
        for i in range(1, n+1): isum += 1/i
        return isum
    gamma = 0.5772156649  # 反之，代近似公式
    return math.log(n) + gamma + 1.0 / (2 * n)

for line in sys.stdin:
    print(f"{harmonic_number(int(line)):.3f}")

ZeroJudge 解題筆記：e447. queue 練習

作者：王一哲
日期：2025年9月23日


ZeroJudge 題目連結：e447. queue 練習

解題想法

這題就是考 queue 的操作，在 Python 要引入 collections 函式庫的 deque，在 C++ 要引入 queue 或是 deque 都可以。

Python 程式碼

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

from collections import deque

n = int(input())
arr = deque()
for _ in range(n):
    line = list(map(int, input().split()))
    if len(line) == 1:
        if line[0] == 2:
            if arr: print(arr[0])
            else: print(-1)
        elif line[0] == 3 and arr: arr.popleft()
    else:
        arr.append(line[1])

ZeroJudge 解題筆記：e446. 排列生成

作者：王一哲
日期：2025年9月22日


ZeroJudge 題目連結：e446. 排列生成

解題想法

這題不論用 Python 還是 C++ 都可以用遞迴窮舉所有的排列方式。在 Python 也可以用 itertools.permutaions，在 C++ 也可以用 next_permutation。但主要的困難之處是輸出速度，要加速才能過關。

Python 程式碼

窮舉，用 print 輸出，超時。

def solve(arr, n, used):
    if len(arr) == n:
        print(*arr)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(input()), set())

窮舉，用 sys.stdout.write 輸出，超時。

import sys

def solve(arr, n, used):
    if len(arr) == n:
        s = " ".join(map(str, arr)) + "\n"
        sys.stdout.write(s)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(sys.stdin.readline()), set())

用 itertools.permutations，用 sys.stdout.write 最後再一次輸出所有結果，最後一筆測資超出記憶體上限。

import sys, itertools

result = []
n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm))
    result.append(f"{s}\n")
sys.stdout.write("".join(result))

用 itertools.permutations，用 sys.stdout.write 逐行輸出結果。使用時間約為 12.3 s，記憶體約為 3.4 MB，通過測試。

import sys, itertools

n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm)) + "\n"
    sys.stdout.write(s)

ZeroJudge 解題筆記：e420. 灰姑娘的新衣

作者：王一哲
日期：2025年9月20日


ZeroJudge 題目連結：e420. 灰姑娘的新衣

解題想法

我用字典 color_idx 儲存各種顏色對應的衣服編號，另一個字典 idx_color 儲存各種衣服編號有的顏色，顔色不重複。最後再計算所有的組合數，輸出最多顔色的衣服，輸出完美搭配的顔色。

Python 程式碼

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

import sys
from collections import defaultdict

color_idx = defaultdict(list)  # 各種顏色對應的衣服編號，可重複
idx_color = defaultdict(set)  # 各種衣服編號有的顏色，不重複
cnt = 0  # 衣服編號
for line in sys.stdin:
    line = line.strip()  # 刪除最後的 \n
    cnt += 1  # 衣服編號加 1
    color_idx[line].append(cnt)  # 顏色 line 有的編號加上 cnt
    idx_color[cnt].add(line)  # 編號 cnt 有的顏色加上 line
    for s in sys.stdin:
        s = s.strip()  # 讀取一行字串，刪除最後的 \n
        if s == "@" or s == "#": break  # 讀到 # 或 @，中止迴圈
        color_idx[s].append(cnt)  # 顏色 s 有的編號加上 cnt
        idx_color[cnt].add(s)  # 編號 cnt 有的顏色加上 s，不重複
comb = 1  # 組合數
for v in idx_color.values(): comb *= len(v)
print(comb)
most_color = []
n = len(idx_color)  # 編號數量
perfect = []
imax = max([len(v) for v in color_idx.values()])
for k, v in color_idx.items():
    if len(v) == imax:
        most_color.append(k)
    if len(set(v)) == n:
        perfect.append(k)
print(",".join(sorted(most_color)))
print(",".join(sorted(perfect)))

ZeroJudge 解題筆記：e293. 花開花落，雨初臨

作者：王一哲
日期：2025年9月20日


ZeroJudge 題目連結：e293. 花開花落，雨初臨

解題想法

這題的題目敘述根本就是在寫小說，重點只有「要找出給定的數字在 100 以內的質因數」。解題時要先建表 primes，列出 0 到 100 之間的質數，只有 25 個，直接打進程式碼就好。接下來計算這些質數相乘的結果 pq，假設要檢查的數字為 $m$，如果 $s = gcd(m, pq)$ 等於 1，則 $m$ 在 0 到 100 之間沒有質因數；反之，從 primes 之中依序取出質數 prime，檢查 prime 是否為 s 的因數即可。不過這題的輸出最大會到 5000 位，要用大數運算，所以我只有用 Python 解題。

Python 程式碼

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

import sys, math

# 建表，2 ~ 100 之間的質數
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
          31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
          73, 79, 83, 89, 97}
# pq，2 ~ 100 所有的質數相乘
pq = 1
for prime in primes: pq *= prime
# 主要的解題過程
result = []  # 儲存結果用的空串列
lines = sys.stdin.readlines()
for line in lines[1:]:
    m = int(line)  # 轉成整數 m
    res = []  # 儲存 m 的答案用的空串列
    s = math.gcd(m, pq)
    if s == 1:  # m 在 0 到 100 之間沒有質因數
        result.append("Terrible Silence...\n")
    else:
        for prime in primes:  # 依序由 primes 中取出質數，檢查是否為 s 的因數
            if s%prime == 0:  # 如果 prime 是因數
                res.append(f"{prime:d}")  # prime 轉成字串加入 res
        result.append(" ".join(res) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e284. 放暑假了!!!!!

作者：王一哲
日期：2025年9月19日


ZeroJudge 題目連結：e284. 放暑假了!!!!!

解題想法

這題主要考輸入、輸出優化，因為測資數量極大，如果沒有優化輸入、輸出會超時。在 Python 我習慣用 sys.stdin.readlines() 一次讀取所有的測資，並將所有的輸出存在串列 result 之中，最後再用 sys.stdout.write("".join(result)) 一次印出所有答案。在 C++ 如果要用 cin 及 cout，必須加上 ios::sync_with_stdio(0); cin.tie(0);，不然就是改用 scanf 及 printf。事先用字典或集合建表，儲存 $2^0$ 到 $2^31$ 對應的值，讀取測資之後再判斷這個數字是否在表格之中，這樣速度會比較快。但是經過實測之後發現，C++ 的 map 及 unordered_map 都很慢，要用 set 才能過關； Python 的 dict, defaultdict, set 都能過關。

Python 程式碼

用 dict 建表，使用時間約為 4.2 s，記憶體約為 413.6 MB，通過測試。

import sys

table = dict()
x = 1
for _ in range(32):
    table[x] = True
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

用 set 建表，使用時間約為 4.1 s，記憶體約為 418.2 MB，通過測試。

import sys

table = set()
x = 1
for _ in range(32):
    table.add(x)
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e272. gcd(Fm,Fn)

作者：王一哲
日期：2025年9月18日


ZeroJudge 題目連結：e272. gcd(Fm,Fn)

解題想法

這題考數學，必須運用費氏數列的特性 $$ gcd(F_m, F_n) = F_{gcd(m, n)} $$ 如果直接計算 $F_m, F_n$ 的數值再取 $gcd$，在 $m, n$ 極大的狀況下會超時。

Python 程式碼

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

import sys, math

fib = [0]*94
fib[1] = 1
for i in range(2, 94):
    fib[i] = fib[i-1] + fib[i-2]

for line in sys.stdin:
    a, b = map(int, line.split())
    print(fib[math.gcd(a, b)])

ZeroJudge 解題筆記：e128. 新北100-1貪食蛇

作者：王一哲
日期：2025年9月17日


ZeroJudge 題目連結：e128. 新北100-1貪食蛇

解題想法

這題要找位置的數學規律，如果模擬移動的過程一定會超時。

Python 程式碼

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

import math, sys

def find_position(t):  # 輸入目前的時刻計算位置
    if t == 1: return (1, 1)  # 特例，t 等於 1，回傳 (1, 1) 並結束函式
    
    ring = math.floor(math.sqrt(t))  # 已走完的圈數
    #ring = math.isqrt(t)    # 已走完的圈數，Python 3.8 之後才有 math.isqrt
    
    t -= ring * ring  # t 扣掉已走完的圈數平方，換成位移量
    if t == 0:  # 如果 t 等於 0，剛好在這圈結束的位置
        if ring%2: return (1, ring)  # 如果是奇數圈，回傳 (1, ring) 並結束函式
        else: return (ring, 1)  # 如果是偶數圈，回傳 (ring, 1) 並結束函式
    else: ring += 1  # 其它狀況，圈數加 1
    
    x, y = 0, 0  # 座標 (x, y)
    if ring%2:  # 奇數圈
        if t > ring:  # 在底部向左移動
            x = 2*ring - t  
            y = ring
        else:  # 在右側向下移動
            x = ring
            y = t
    else:  # 偶數圈
        if t > ring:  # 在右側向上移動
            x = ring
            y = 2*ring - t
        else:  # 在底部向右移動
            x = t
            y = ring
    
    return (x, y)

for line in sys.stdin:
    t = int(line)
    if t == 0: break
    print(*find_position(t))

ZeroJudge 解題筆記：d985. Gran Turismo 5

作者：王一哲
日期：2025年9月16日


ZeroJudge 題目連結：d985. Gran Turismo 5

解題想法

依序讀取每一圈的時間，將單位換成 s，更新最短秒數、計算總秒數，最後輸出所有圈數的最短秒數及平均。

Python 程式碼

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

track = 0  # 圈數
N = int(input())  # N 組測資
for _ in range(N):  # 執行 N 次
    track += 1  # 圈數加 1
    print(f"Track {track:d}:")
    M = int(input())  # M 行資料
    best = float('inf')  # 最短秒數
    total = 0  # 總秒數
    for _ in range(M):  # 執行 M 次
        m, s = map(int, input().split())  # 單圈時間 m's"
        t = m*60 + s  # 換成秒數
        best = min(best, t)  # 新的最短秒數
        total += t  # 更新總秒數
    average = total // M  # 平均值
    print(f"Best Lap: {best//60:d} minute(s) {best%60:d} second(s).")
    print(f"Average: {average//60:d} minute(s) {average%60:d} second(s).")
    print()

ZeroJudge 解題筆記：d984. 棄保效應

作者：王一哲
日期：2025年9月15日


ZeroJudge 題目連結：d984. 棄保效應

解題想法

我用三層 if 解題，討論 A、B、C 三個人分別為最高票的狀況下，第一名票數減去第三名的票數之後是否仍大於第二名的票數。

Python 程式碼

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

import sys

for line in sys.stdin:
    a, b, c = map(int, line.split())  # 三個人的票數
    if a > b and a > c:  # A 最高票
        if b > c:  # B 第二名
            if a-c > b: print("A")  # A 減 C 的票數還贏
            else: print("B")  # 反之 B 贏
        else:  # C 第二名
            if a-b > c: print("A")  # A 減 B 的票數還贏
            else: print("C")  # 反之 C 贏
    elif b > a and b > c:  # B 最高票
        if a > c:  # A 第二名
            if b-c > a: print("B")  # B 減 C 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # C 第二名
            if b-a > c: print("B")  # B 減 A 的票數還贏
            else: print("C")  # 反之 C 贏
    else:  # C 最高票
        if a > b:  # A 第二名
            if c-b > a: print("C")  # C 減 B 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # B 第二名
            if c-a > b: print("C")  # C 減 A 的票數還贏
            else: print("B")  # 反之 B 贏

ZeroJudge 解題筆記：d881. 作業苦多

作者：王一哲
日期：2025年9月14日


ZeroJudge 題目連結：d881. 作業苦多

解題想法

這題可以寫迴圈直接跑，也可以先推導數學公式之後再代公式求解。

Python 程式碼

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

import sys

for line in sys.stdin:
    d = int(line)  # 公差的增量
    dp = [0]*51  # 儲存第 0 ~ 50 項的串列
    dp[1] = 1  # 第 1 項為 1
    b = 1  # 公差，預設為 1
    isum = 1  # 加總，先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        dp[i] = dp[i-1] + b  # 第 i 項為第 i-1 項加上 b
        isum += dp[i]  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

只要用到前一項，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    d = int(line)  # 公差的增量
    last = 1  # 第 1 項為 1
    b = 1  # 公差，預設為 1
    isum = 1  # 加總，先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        last += b  # 第 i 項為第 i-1 項加上 b
        isum += last  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

直接代公式，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    print(1275 + int(line)*19600)

ZeroJudge 解題筆記：d732. 二分搜尋法

作者：王一哲
日期：2025年9月13日


ZeroJudge 題目連結：d732. 二分搜尋法

解題想法

可以自訂二分搜尋法的函式，也可以用 Python 的 bisect.bisect_left 或是 C++ algorithm 函式庫的 lower_bound 解題。注意，這題的位數是從 1 開始計算，搜尋到的索引值要加 1 才是答案。

Python 程式碼

自己寫二分搜尋法，使用時間約為 1.1 s，記憶體約為 20.9 MB，通過測試。

def binary_search(arr, target):  # 自己寫二分搜尋法，代入串列 arr 及目標 target
    low, high = 0, len(arr)-1  # 索引值的下限、上限
    while low <= high:  # 如果 low 小於等於 high 繼續執行
        mid = (high - low) // 2 + low  # 計算中間值 mid
        if arr[mid] == target: return mid+1  # 找到目標，回傳 mid，離開函式
        if arr[mid] > target:  # 目標在左半邊，降低 high
            high = mid - 1
        else:  # 目標在右半邊，提升 low
            low = mid + 1
    if arr[low] != target: return 0  # 如果沒有找到目標，回傳 0

if __name__ == "__main__":
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    for t in map(int, input().split()):
        print(binary_search(arr, t))

bisect_left，使用時間約為 0.3 s，記憶體約為 20.9 MB，通過測試。

from bisect import bisect_left

n, k = map(int, input().split())
arr = list(map(int, input().split()))
for x in map(int, input().split()):
    idx = bisect_left(arr, x)
    if arr[idx] == x: print(idx+1)
    else: print(0)

ZeroJudge 解題筆記：d710. parking lot

作者：王一哲
日期：2025年9月12日


ZeroJudge 題目連結：d710. parking lot

解題想法

這題用字典儲存資料很方便，一個儲存廠牌對應的顏色，另一個儲存顏色對應的廠牌，最後再依照測資從字典中讀取資料並輸出。

Python 程式碼

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

import sys
from collections import defaultdict

for line in sys.stdin:
    if not line.strip(): continue  # 跳過空行
    n, m = map(int, line.split())  # n 輛車， m 個指示
    brands = defaultdict(list)  # 廠牌對應的顏色
    colors = defaultdict(list)  # 顏色對應的廠牌
    for _ in range(n):  # 讀取 n 行資料
        b, c = input().split()  # 廠牌 b，顏色 c
        brands[b].append(c)
        colors[c].append(b)
    for _ in range(m):  # 讀取 m 個指示
        x, y = input().split()
        if x == "brand":  # 如果 x 等於 brand
            for c in brands[y]:  # 依序取出 brands[y] 的顏色
                print(f"{y:s} {c:s}")
        elif x == "color":  # 如果 x 等於 color
            for b in colors[y]:  # 依序取出 colors[y] 的廠牌
                print(f"{b:s} {y:s}")
    print()  # 空一行

ZeroJudge 解題筆記：d681. BinaryCount

作者：王一哲
日期：2025年9月11日


ZeroJudge 題目連結：d681. BinaryCount

解題想法

每次讀取一行字串，直到 EOF 為止。將字串用空格分割，如果分割後的字串為 s，在 Python 可以用 int(s, 2) 轉換成 int，在 C++ 可以用 bitset。先儲存首項的數值，接下來一次讀取一個運算符號及整數，依照運算符號計算數值，同時組合要輸出的運算式。

Python 程式碼

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

import sys

for line in sys.stdin:
    arr = list(line.split())  # 分割讀到的字串
    equ = [arr[0]]  # 要輸出的算式，先放入 arr[0]
    last = int(arr[0], 2)  # 前一個計算結果，先放入 arr[0] 用 2 進位換算的整數
    n = len(arr)  # arr 的長度
    for i in range(1, n, 2):  # 依序處理 arr[1], arr[2] ~ arr[n-2], arr[n-1]
        op = arr[i]  # 運算符號
        if op == "and":  # 如果是 and
            equ.append("&&")  # 將 && 加入 equ
            last = last & int(arr[i+1], 2)  # 將 last 與 arr[i+1] 用 2 進位換算的整數取 &
        elif op == "or":  # 如果是 or
            equ.append("||")  # 將 || 加入 equ
            last = last | int(arr[i+1], 2)  # 將 last 與 arr[i+1] 用 2 進位換算的整數取 |
        equ.append(arr[i+1])  # 將 arr[i+1] 加入 equ
    print("".join(equ) + " = " + bin(last)[2:].zfill(5))  # 拼成要輸出的算式，計算結果要補 0

ZeroJudge 解題筆記：d643. 勞動的符咒

作者：王一哲
日期：2025年9月10日


ZeroJudge 題目連結：d643. 勞動的符咒

解題想法

如果輸入的字串 s 長度為 n，先找 n 的所有因數，再用字串切片，將 s 切成因數長度的子字串，將子字串排序後連接成新的字串 t。用集合 spells 儲存新的咒語，如果 t 不在 spells 之中才輸出。

Python 程式碼

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

s = input().strip()  # 讀取字串
n = len(s)  # 字串長度
factors = {1}  # n 的因數，先放入 1
for i in range(2, int(n**0.5)+1):  # 找 2 ~ sqrt(n)+1 之間的因數
    if n%i == 0:
        factors.add(i)
        factors.add(n//i)
spells = {s}  # 可能的咒語，先放入 s
for factor in sorted(factors):  # 測試由小到大的所有因數
    # 取因數長度的子字串，排序後接成新的字串 t
    t = "".join(sorted([s[i:i+factor] for i in range(0, n, factor)]))
    if t not in spells:  # 如果 t 不在 spells 之中
        spells.add(t)  # t 加入 spells
        print(t)  # 印出 t
if len(spells) == 1: print("bomb!")  # 如果 spells 只有一項，印出 bomb!

ZeroJudge 解題筆記：d637. 路過的鴨duck

作者：王一哲
日期：2025年9月9日


ZeroJudge 題目連結：d637. 路過的鴨duck

解題想法

這題考 0/1 背包問題，我習慣的寫法是先建立一個一維陣列 dp，分別對應食量為 0 ~ 上限 imax 對應的最大飽足感總和。依序讀取每個食物的體積 a 及飽足感 b，從 dp[imax] 往回更新總和至 dp[a] 為止，取 dp[i] 與 dp[i-a] + b 較大者，最後答案在 dp[imax] 。

Python 程式碼

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

n = int(input())  # n 顆飼料
imax = 100  # 食量上限
dp = [0]*(imax + 1)  # 吃 0 ~ 100 分別對應的最大飽足感
for _ in range(n):  # 依序讀取 n 行資料
    a, b = map(int, input().split())  # 飼料的體積 a、飽足感 b
    for i in range(imax, a-1, -1):  # 倒序檢查飽足感 imax ~ a
        dp[i] = max(dp[i], dp[i-a] + b)  # dp[i-a] + b 可能更大
print(dp[imax])  # 印出最大值

ZeroJudge 解題筆記：d636. 大爆炸bomb

作者：王一哲
日期：2025年9月8日


ZeroJudge 題目連結：d636. 大爆炸bomb

解題想法

這題考快速冪、平方求冪 (exponentiating by squaring)。

Python 程式碼

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

def exp(x, y, p):  # x 的 y 次方，取除以 p 的餘數
    t = 1  # 儲存結果用的變數
    while y:  # 如果 y 不等於 0 繼續執行
        if y&1: t = t*x%p  # 若 y 與 1 取 and 為 1，更新 t，乘上 x 再取 mod p
        y >>= 1  # y 除以 2
        x = x*x%p  # 更新 x，乘上 x 再取 mod p
    return t  # 回傳 t

print(exp(*map(int, input().split()), 10007))  # 印出 exp(a, b, p)

用 pow 作弊，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

print(pow(*map(int, input().split()), 10007))

ZeroJudge 解題筆記：d626. 小畫家真好用

作者：王一哲
日期：2025年9月7日


ZeroJudge 題目連結：d626. 小畫家真好用

解題想法

用 BFS 及四方位檢查解題，由於我比較懶得檢查邊界值，我會在周圍加上 + 當作哨兵避免出界。

Python 程式碼

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

n = int(input())  # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)]  # 讀取地圖資料，最右側加上 + 作為哨兵
grid.append(list("+"*(n+1)))  # 最下方加 n+1 個 + 作為哨兵
que = [tuple(map(int, input().split()))]  # 待走訪佇列，先放入起點
head = 0  # 從 que 讀取資料用的索引值
while head < len(que):  # BFS，當 head 還沒有出界繼續執行
    r, c = que[head]; head += 1  # 從 que 讀取要走訪的點 (r, c)，head 加 1
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
        nr, nc = r+dr, c+dc  # 要檢查的點 (nr, nc)
        if grid[nr][nc] == "+": continue  # 如果 grid[nr][nc] 是 +，找下一個點
        grid[nr][nc] = "+"  # grid[nr][nc] 改成 +
        que.append((nr, nc))  # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n]))  # 依序讀取 grid[:n][:n]，接成字串再輸出

改用 deque 儲存待走訪節點，使用時間約為 25 ms，記憶體約為 3.7 MB，通過測試。

from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)]  # 讀取地圖資料，最右側加上 + 作為哨兵
grid.append(list("+"*(n+1)))  # 最下方加 n+1 個 + 作為哨兵
que = deque([tuple(map(int, input().split()))])  # 待走訪佇列，先放入起點
while que:  # BFS，當 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除要走訪的點 (r, c)
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
        nr, nc = r+dr, c+dc  # 要檢查的點 (nr, nc)
        if grid[nr][nc] == "+": continue  # 如果 grid[nr][nc] 是 +，找下一個點
        grid[nr][nc] = "+"  # grid[nr][nc] 改成 +
        que.append((nr, nc))  # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n]))  # 依序讀取 grid[:n][:n]，接成字串再輸出

ZeroJudge 解題筆記：d623. 反方陣

作者：王一哲
日期：2025年9月6日


ZeroJudge 題目連結：d623. 反方陣

解題想法

假設矩陣 $$ M = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} $$ 其行列式值 $det(M) = ad - bc$。如果 $det(M) \neq 0$，$M$ 是可逆的，其反矩陣 $$ M^{-1} = \frac{1}{det(M)} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix} $$ 另外要注意，題目的說明是4個0表示結束，實際測資以一個零表示結束。

Python 程式碼

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

while True:
    line = list(map(int, input().split()))
    if len(line) == 1 and line[0] == 0: break  # 只有一個 0，中止迴圈
    a, b = line  # 方陣 [[a, b], [c, d]]
    c, d = map(int, input().split())
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        print("cheat!")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        print(f"{d/det:.5f} {-b/det:.5f}")
        print(f"{-c/det:.5f} {a/det:.5f}")

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

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    if lines[idx].strip() == "0": break  # 只有一個 0，中止迴圈
    a, b = map(int, lines[idx].split())  # 方陣 [[a, b], [c, d]]
    idx += 1
    c, d = map(int, lines[idx].split())
    idx += 1
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        result.append("cheat!\n")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        result.append(f"{d/det:.5f} {-b/det:.5f}\n")
        result.append(f"{-c/det:.5f} {a/det:.5f}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d586. 哈密瓜美語

作者：王一哲
日期：2025年9月5日


ZeroJudge 題目連結：d586. 哈密瓜美語

解題想法

這題用兩個字典建立數字轉英文、英文轉數字的對照表，再依照讀取到的測資開頭是數字或字母，判斷要從哪一個表格找答案。

Python 程式碼

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

s1 = "mjqhofawcpnsexdkvgtzblryui"  # 數字轉英文用的字串
s2 = "uzrmatifxopnhwvbslekycqjgd"  # 英文轉數字用的字串
ntoc, cton = dict(), dict()  # 數字轉英文、英文轉數字的對照表
for i, c in enumerate(s1, start=1): ntoc[str(i)] = c
for i, c in enumerate(s2, start=1): cton[c] = i
n = int(input())  # n 道謎題
for _ in range(n):  # 執行 n 次
    line = list(input().split())  # 讀取一行資料分割後存入串列
    m = int(line[0])  # 資料長度為 m
    if line[1].isalpha():  # 如果 line[1] 是字母
        print(sum(cton[c] for c in line[1:]))  # 依序讀取 line[1] ~ line[-1] 代入表中找數字求加總
    else:  # 如果 line[1] 是數字
        print("".join([ntoc[i] for i in line[1:]]))  # 依序讀取 line[1] ~ line[-1] 代入表中找字母組成字串

ZeroJudge 解題筆記：d584. 技能點數skill

作者：王一哲
日期：2025年9月4日


ZeroJudge 題目連結：d584. 技能點數skill

解題想法

依照職業及當時的等級更新技能點數即可。

Python 程式碼

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

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    job, level = map(int, line.split())
    tot = 0
    if job == 2 and level >= 8:  # 如果是法師，8 級一轉
        tot += 1 + (level-8)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    elif (job == 1 or job == 3 or job == 4) and level >= 10:  # 如果是劍士、弓箭手、盜賊，10 級一轉
        tot += 1 + (level-10)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    if job != 0 and level >= 30: tot += 1  # 如果不是初心者，30 級二轉，點數加 1
    if job != 0 and level >= 70: tot += 1  # 如果不是初心者，70 級三轉，點數加 1
    if job != 0 and level >= 120: tot += 3  # 如果不是初心者，120 級四轉，點數加 3
    result.append(f"{tot:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d575. 末日審判

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


ZeroJudge 題目連結：d575. 末日審判

解題想法

這題看起來很簡單，只要計算兩個點之間的距離是否小於、等於半徑即可，但是用 Python 解題時需要用 sys.stdin.readlines() 及 sys.stdour.write() 加速，否則會超時；用 C++ 解題要使用 long long，否則會溢位。

Python 程式碼

第8筆測資超時。

import sys

for line in sys.stdin:
    x0, y0, x1, y1, r = map(int, line.split())
    if abs(x0-x1) + abs(y0-y1) <= r: print("die")
    else: print("alive")

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

import sys

lines = sys.stdin.read().splitlines()  # 一次讀取所有資料，減少讀取次數
results = []  # 儲存要輸出的結果
for line in lines:  # 從 lines 依序讀取資料 line
    x0, y0, x1, y1, r = map(int, line.split())  # 用 split 拆開 line，轉成 int，存入變數
    if abs(x0-x1) + abs(y0-y1) <= r: results.append("die\n")  # 先將要輸出的字串加到 results
    else: results.append("alive\n")
sys.stdout.write("".join(results))  # 將 results 合併成一個很長的字串再一次輸出

ZeroJudge 解題筆記：d574. 節約符咒

作者：王一哲
日期：2025年9月2日


ZeroJudge 題目連結：d574. 節約符咒

解題想法

第4筆測資只有一行，用空格分隔數量與字串，用 Python 解題需要特別處理。依序讀取字串中每個字母，計算連續出現的相同字母數量，將數量與對應的字母組成字串。

Python 程式碼

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

line = list(input().split())  # 讀取一行資料並用空格分隔存成串列
n = int(line[0])  # 字串長度
if len(line) == 1: s = input().strip()  # 如果 line 只有一項，再讀取一行字串
else: s = line[1]  # 反之，字串在 line[1]
t = ""  # 儲存答案用的空字串
cnt = 1  # 連續相同字母的數量，預設為 1
last = s[0]  # 前一個字母，預設為 s[0]
for c in s[1:]:  # 依序讀取 s[1] ~ s[n-1]
    if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
    else:  # 反之，結算之的連續相同字母數量
        t += str(cnt) + last  # cnt 轉成字串加上 last，接到 t 之後
        cnt = 1  # cnt 重置為 1
        last = c  # last 重置為 c
t += str(cnt) + last  # 最後要再結算一次 cnt 與 last
if len(t) < n: print(t)  # 如果 t 較短，印出 t
else: print(s)  # 反之，印出 s

ZeroJudge 解題筆記：d566. 秒殺率

作者：王一哲
日期：2025年9月1日


ZeroJudge 題目連結：d566. 秒殺率

解題想法

這題要注意：

1. 此處的解題紀錄排在前面的資料代表時間越晚
2. 第 4 筆測資格式有問題，全部塞在同一行，用 Python 解題需要特別處理這筆測資。

Python 程式碼

理論上這樣寫應該要過關，但是第 4 筆測資格式有問題，全部塞在同一行，要再修改程式碼。

cnt = dict()  # 計數器，是否 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # AC 人數
n = int(input())  # n 筆資料
data = [input().split() for _ in range(n)]  # 先讀完所有的資料
for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
    if name not in cnt:  # 如果 name 不在 cnt 之中
        if state == "AC":  # 如果第一次就 AC
            fir += 1  # fir 加 1
            ac += 1  # ac 加 1
            cnt[name] = True  # cnt[name] 為 True
        else:  # 第一次沒有 AC
            cnt[name] = False  # cnt[name] 為 False
    elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
        ac += 1  # ac 加 1
        cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

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

import sys

cnt = dict()  # 計數器，是否第一次就 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # 全部 AC 的人數
for line in sys.stdin:  # 讀資料直到 EOF 為止
    data = line.split()  # 先試著分割資料
    if len(data) == 1:  # 如果只有一筆，是 n
        n = int(data[0])
        data = [input().split() for _ in range(n)]  # 先讀完所有的資料
        for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
    else:  # 為了測資 4 全部塞在一行的狀況
        n = int(data[0])
        for i in range(2*n, 0, -2):  # 反向讀取資料，先讀取時間較早的資料
            name, state = data[i-1], data[i]
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

ZeroJudge 解題筆記：d563. 等值首尾和

作者：王一哲
日期：2025年8月31日


ZeroJudge 題目連結：d563. 等值首尾和

解題想法

題目敘述有兩個問題：

1. 題目雖然說有兩行測資，第一行為一個數字 N，代表第二行有 N 個用空格分隔的數字，但實際上只有一行，如果用 Python 解題會出事。
2. 範例的寫法看起來好像從左、右加總的數量要一樣，但其實不需要，只要前綴和、後綴和相等就好，不看數量。

Python 程式碼

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

arr = list(map(int, input().split()))[1:]  # 讀取一行資料轉成串列，不取首項
psum = 0  # 前綴和
cand = set()  # 可能的加總
for a in arr:  # 依序讀取 arr 的資料
    psum += a  # 更新 psum
    cand.add(psum)  # psum 加入 cand
ssum = 0  # 後綴和
cnt = 0  # 答案
for a in arr[::-1]:  # 反向讀取 arr 的資料
    ssum += a  # 更新 ssum
    if ssum in cand: cnt +=1  # 如果 ssum 在 cand 之中，cnt 加 1
print(cnt)  # 印出 cnt

ZeroJudge 解題筆記：d561. 被秒殺的四捨五入

作者：王一哲
日期：2025年8月30日


ZeroJudge 題目連結：d561. 被秒殺的四捨五入

解題想法

這題在 Python 可以用 decimal 函式庫作弊，將數值存成 Decimal 格式的浮點數再四捨五入即可。比較正常的作法，是用字串格式儲存數字，依序判斷數字的正負號、整數位、小數點後第一位、小數點後第二位，最後再依照小數點後第三位的值判斷是否要捨去或進位。

Python 程式碼

用 decimal 函式庫作弊，使用時間約為 24 ms，記憶體約為 3.9 MB，通過測試。

from decimal import Decimal, ROUND_HALF_UP
import sys

for line in sys.stdin:
    # 將 line 轉成 Decimal 格式的十進位數字，4捨5入到小數點後第2位
    n = Decimal(line.strip()).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)
    if str(n) == "-0.00":
        print("0.00")  # -0.00 要輸出為 0.00
    else:
        print(n)

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

import sys

for line in sys.stdin:
    s = line.strip()  # 字串格式的數字
    negative = False  # 是否為負值，預設為 False
    if s[0] == '-':  # 如果 s[0] 是負號
        negative = True  # negative 設定為 True
        s = s[1:]  # 刪除 s[0]
    num = int(s[0])  # 取整數位加到 num
    s = s[2:]  # 刪除整數位、小數點
    if s and s[0] != '0':  # 處理小數點後第 1 位
        num += int(s[0])*0.1
    s = s[1:]  # 刪除 s[0]
    if s and s[0] != '0':  # 處理小數點後第 2 位
        num += int(s[0])*0.01
    s = s[1:]  # 刪除 s[0]
    if negative: num = -num  # 如果是負值，乘以 -1
    if s and s[0] in '56789':  # 如果 s[0] 大於等於 5，要 4 捨 5 入
        if negative: num -= 0.01  # 如果是負值，減 0.01
        else: num += 0.01  # 如果是正值，加 0.01
    if str(num) == "-0.0": print("0.00")  # 如果轉成字串等於 -0.0，要印出 0.00
    else: print(f"{num:.2f}")

使用 Python 及 C++ 産生重複數字的所有排列方式

作者：王一哲
日期：2025年8月30日

前言

由於最寫連續寫到好幾個題目，需要從測資讀取一列數字，再産生這列數字的所有排列方式，例如 d762. 10344 - 23 out of 5。我之前都是用 Python 的 itertools.permutations 偷懶，但是為了準備之後的課程，還是來研究一下如何用遞迴及回溯産生所有的排列方式。

Python itertools.permutations

這是一個效率很好的迭代器，官方說明書在此 itertools.permutations，通常會搭配 for 迴圈一起使用，語法為

for [産生的數組名稱] in itertools.permutations(可以迭代的物件):

例如要産生 [1, 2, 3, 2, 1] 的所有排列方式可以這樣寫

from itertools import permutations

nums = [1, 2, 3, 2, 1]
for perm in permutations(nums):
    print(*perm)

如果只考慮 5 個數字的排列方式，總共會有 $5! = 120$ 種，以上的程式碼會輸出 120 行。但是這裡面有不少重複的結果，如果只想輸出不重複的結果，可以再稍微修改一下程式碼，用集合記錄已經産生過的結果，這樣就只會輸出 30 行。

from itertools import permutations

nums = [1, 2, 3, 2, 1]
used = set()
for perm in permutations(nums):
    if perm in used: continue
    used.add(perm)
    print(*perm)

ZeroJudge 解題筆記：d555. 平面上的極大點

作者：王一哲
日期：2025年8月29日


ZeroJudge 題目連結：d555. 平面上的極大點

解題想法

先讀取所有點的座標存入二維串列 points，由大到小排序。用變數 max_y 記錄目前最高的 y 座標，預設值為負無窮大。從 points 之中依序讀取點的座標 x, y，如果符合以下兩種狀況，將 (x, y) 加入答案 ans 之中：

1. y 大於 max_y
2. ans 之中沒有任何一個點可以支配 (x, y)

最後將 ans 排序再印出。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    ca += 1
    print(f"Case {ca:d}:")
    n = int(line)
    point = sorted([tuple(map(int, input().split())) for _ in range(n)], reverse=True)
    ans = []  # 答案
    max_y = -float('inf')  # 目前最高的 y 座標，預設為極小值
    for x, y in point:  # 從 point 依序讀取點的座標 (x, y)
        if y > max_y:  # y 大於 max_y
            ans.append((x, y))  # (x, y) 加入 ans
            max_y = y  # 更新 max_y
        # 另一種可能性，ans 之中沒有任何點可以支配 (x, y)
        elif not any(px >= x and py >= y for px, py in ans):
            ans.append((x, y))
    ans.sort()  # 由小到大排序
    print(f"Dominate Point: {len(ans):d}")
    for x, y in ans: print(f"({x:d},{y:d})")

ZeroJudge 解題筆記：d526. Binary Search Tree (BST)

作者：王一哲
日期：2025年8月28日


ZeroJudge 題目連結：d526. Binary Search Tree (BST)

解題想法

這題要自訂二元樹類別，遞迴版比較簡潔。

Python 程式碼

遞迴版，使用時間約為 0.7 s，記憶體約為 4 MB，通過測試。

class Node:  # 自訂節點類別
    def __init__(self, data):
        self.data = data  # 資料
        self.left = None  # 左子樹
        self.right = None  # 右子樹

class BST:  # 自訂二元搜尋樹類別
    def __init__(self):
        self.root = None  # 根節點

    def insert(self, data):  # 插入節點
        if self.root is None:  # 如果沒有根節點
            self.root = Node(data)  # 設定根節點
        else:  # 如果有根節點
            self._insert(data, self.root)  # 遞迴，代入 data 及 self.root

    def _insert(self, data, current):  # 內部使用的插入方法
        if data < current.data:  # 如果要插入的資料小於目前節點的資料
            if current.left is None:  # 如果沒有左子樹
                current.left = Node(data)  # data 放在左子樹
            else:  # 如果有左子樹
                self._insert(data, current.left)  # 遞迴，代入 data 及左子樹
        elif data > current.data:  # 如果要插入的資料大於目前節點的資料
            if current.right is None:  # 如果沒有右子樹
                current.right = Node(data)  # data 放在右子樹
            else:  # 如果有右子樹
                self._insert(data, current.right)  # 遞迴，代入 data 及右子樹
    
    def delete(self, data):  # 刪除資料
        self.root = self._delete(self.root, data)
    
    def _delete(self, current, data):  # 內部使用的刪除資料方法
        if current is None:  # 如果 current 是空的
            return current  # 回傳 current 並離開函式
        # 找要刪除的節點
        if data < current.data:  # 如果要刪除的資料小於目前節點的資料
            current.left = self._delete(current.left, data)  # 遞迴，代入左子樹及 data
        elif data > current.data:  # 如果要刪除的資料大於目前節點的資料
            current.right = self._delete(current.right, data)  # 遞迴，代入右子樹及 data
        else:  # 找到要刪除的節點
            if current.left is None:  # 如果左子樹是空的
                return current.right  # 用右子樹取代 node
            elif current.right is None:  # 如果右子樹是空的
                return current.left  # 用左子樹取代 node
            # 有左、右子樹
            temp = self._findMin(current.right)  # 找右子樹中最小資料的節點
            current.data = temp.data  # current 的資料改成 temp 的資料
            current.right = self._delete(current.right, temp.data)  # 刪除右子樹中最小資料的節點
        return current
    
    def _findMin(self, current):  # 內部使用的找最小值方法
        while current.left is not None:  # 向下找左子樹直到空節點為止
            current = current.left
        return current
    
    def preorder(self):  # 前序走訪
        self._preorder(self.root)
        print()

    def _preorder(self, current):  # 內部使用的前序走訪
        if current:  # 如果 current 不是 None
            print(current.data, end=' ')  # 印出 current.data
            self._preorder(current.left)  # 遞迴，代入左子樹
            self._preorder(current.right)  # 遞迴，代入右子樹

import sys

for line in sys.stdin:
    n = int(line)  # 一行有 n 個數字
    tree = BST()  # 建立 BST 物件
    for data in map(int, input().split()):  # 依序讀取此行的數字
        tree.insert(data)  # 將資料插入 tree 之中
    tree.preorder()  # 前序走訪