ZeroJudge 解題筆記：b511. 換銅板

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


ZeroJudge 題目連結：b511. 換銅板

解題想法

這題我用函式遞迴窮舉所有面額硬幣、數量、總金額的組合，如果遇到總金額符合題目要求的組合就輸出答案。

Python 程式碼

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

def solve():
    import sys
    n = int(sys.stdin.readline())  # n 種面額
    coins = sorted(list(map(int, sys.stdin.readline().split())))  # 硬幣面額，由小到大排序
    target = int(sys.stdin.readline())  # 目標
    ### 主要的解題過程 ###
    def backtrack(curr, nums, total):
        if total == target:  # 遞迴出口，符合目標
            s = "(" + ",".join(map(str, nums)) + ")"  # 要輸出的字串
            sys.stdout.write(f"{s}\n")
            return
        if curr == n or total > target:  # 遞迴出口，已經到最後一種面額或超過目標
            return
        maxn = (target-total) // coins[curr]  # 這個面額可用的最大數量
        for i in range(maxn+1):  # 依序測試 0 ~ maxn 個
            nums[curr] = i  # 設定這個面額的數量
            backtrack(curr+1, nums, total + coins[curr]*i)  # 遞迴
    ### End of backtrack ###
    backtrack(0, [0]*n, 0)  # 從索引值 0、個數 0、加總 0 開始測試
### End of solve ###

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：b373. [福州19中]车厢重组

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


ZeroJudge 題目連結：b373. [福州19中]车厢重组

解題想法

這題實際上就是考氣泡排序法的交互次數。據說第二筆測資車廂編號的資料有問題，可能被空行分隔，不是只有一行，用 Python 解題時，需要加上一些濾掉空行的工具。

Python 程式碼

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

import sys

n = int(sys.stdin.readline())  # n 節車廂
arr = []  # 車廂編號
for line in sys.stdin:  # 讀取多行測資
    if not line.strip(): continue  # 如果是空行，讀下一行
    arr += list(map(int, line.split()))  # 如果不是空行，轉成串列接到 arr
### 氣泡排序法，找交換次數 ###
cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        if arr[i] > arr[j]:
            arr[i], arr[j] = arr[j], arr[i]
            cnt += 1
sys.stdout.write(f"{cnt:d}\n")

ZeroJudge 解題筆記：b367. 翻轉世界

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


ZeroJudge 題目連結：b367. 翻轉世界

解題想法

可以用二維串列儲存圖的內容，再從上下兩端逐行檢查，下方的列前後順序對調之後內容是否與上方的列相同；如果共有奇數列，還要再單獨檢查中間的列。也可以將圖的內容接成很長的一維串列，只要從兩端往中間依序檢查數字是否相同，寫起來比較簡單。

Python 程式碼

用二維串列儲存圖的內容，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

def check(grid):  # 輸入圖，判斷是否轉 180 度之後對稱
    n, m = len(grid), len(grid[0])  # 圖的尺寸
    for i in range(n//2):  # 從上下兩端往中間檢查
        if grid[i] != grid[n-i-1][::-1]:  # 如果將底下的列翻轉之後不相等
            return False  # 回傳 False
    if n%2 == 1:  # 如果為奇數列，再檢查中間的列
        if grid[n//2] != grid[n//2][::-1]:
            return False
    return True  # 最後回傳 True

t = int(input())  # t 張圖
for _ in range(t):  # 執行 t 次
    n, m = map(int, input().split())  # 圖的尺寸 n*m
    grid = [list(map(int, input().split())) for _ in range(n)]  # 讀取圖
    print("go forward" if check(grid) else "keep defending")

ZeroJudge 解題筆記：b265. Q11286 - Conformity

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


ZeroJudge 題目連結：b265. Q11286 - Conformity

解題想法

這個題目的中文敘述很奇怪。題目的意思應該是要統計各種課程組合的選課人數，例如

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100

第 2、4 列是一樣的課程組合，因此答案為 2。另一筆範例測資

3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444

因為 2、3、4 列是不一樣的課程組合，各有 1 個人選擇這個組合，題目是將所有最多選課人數的課程組合都加起來，所以答案為 3。

Python 程式碼

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

import sys
from collections import defaultdict

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    cnt = defaultdict(int)
    for _ in range(n):
        course = tuple(sorted(list(map(int, sys.stdin.readline().split()))))
        cnt[course] += 1
    ans = imax = 0
    for v in cnt.values():
        if v > imax:
            ans = v; imax = v
        elif v == imax:
            ans += v
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a982. 迷宮問題#1

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


ZeroJudge 題目連結：a982. 迷宮問題#1

解題想法

這題我用 BFS 解題。可以用兩個二維串列分別儲存地圖及步數，也可以用一個二維串列儲存步數，-1 代表邊界。

Python 程式碼

用兩個二維串列，分別儲存地圖及步數。使用時間約為 33 ms，記憶體約為 3.9 MB，通過測試。

from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input()) for _ in range(n)]  # 地圖資料
steps = [[0]*n for _ in range(n)]  # 步數資料
steps[1][1] = 1  # 起點為 (1, 1)，步數 1
que = deque([(1, 1)])  # 待走訪佇列，先放入 (1, 1)
while que:  # BFS
    r, c = que.popleft()  # 目前的座標 (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] == '#' or steps[nr][nc] != 0:  # 如果是邊界或已走過
            continue  # 找下一個點
        steps[nr][nc] = steps[r][c] + 1  # 更新 (nr, nc) 的步數
        que.append((nr, nc))  # (nr, nc) 加到 que
### End of BFS ###
# 如果 (n-2, n-2) 此格不是 0，有解；反之無解
print(steps[n-2][n-2] if steps[n-2][n-2] != 0 else "No solution!")

ZeroJudge 解題筆記：a981. 求和問題

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


ZeroJudge 題目連結：a981. 求和問題

解題想法

這題要用遞迴窮舉所有的組合，輸出其中符合條件的組合，並且要適當地剪枝，節省運算時間。不過我在 Python 一直沒有寫出能夠過關的程式碼，最後一筆測資超時。

Python 程式碼

最後一筆測資超時。

def solve():
    import sys
    lines = sys.stdin.readlines()
    head = 0
    while head < len(lines):
        n, m = map(int, lines[head].split())  # 讀取數量 n，要找的加總 m
        nums = sorted(list(map(int, lines[head+1].split())))  # 讀取候選的數值
        head += 2  # 從 lines 讀取資料的索引值
        choice = [False]*n  # 是否選這個數字
        have_ans = False  # 是否有解
        ### 主要的解題過程，輸入目前檢測的 nums 索引值，加總 ###
        def backtrack(curr, total):
            nonlocal have_ans  # 這樣才能改變外層 have_ans 的值
            if total == m:  # 有解，印出選擇的數字，結束遞迴
                have_ans = True
                solution = " ".join([str(num) for i, num in enumerate(nums) if choice[i]])
                sys.stdout.write(f"{solution}\n")
                return
            if curr == n or total > m: return # 已出界或是目標為負值，結束遞迴
            choice[curr] = True  # 選此項
            backtrack(curr + 1, total + nums[curr])  # 遞迴，索引值加 1，total 加上此項的值
            choice[curr] = False  # 回溯，不選此項
            backtrack(curr + 1, total)  # 遞迴，索引值加 1，total 不變
        ### End of backtrack ###
        backtrack(0, 0)  # 從索引值 0、加總 0 開始
        if not have_ans: sys.stdout.write("-1\n")  # 如果無解，印出 -1
        
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：a915. 二维点排序

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


ZeroJudge 題目連結：a915. 二维点排序

解題想法

這題在 Python 先將座標 (x, y) 組成 tuple 再存入 list，再用 sort 將 list 排序。在 C++ 可以用 pair 或自訂 struct 儲存座標 (x, y)，再存入 array 或 vector，再用 algorithm 函式庫的 sort 排序。

Python 程式碼

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

n = int(input())
arr = sorted([tuple(map(int, input().split())) for _ in range(n)])
for a in arr: print(*a)

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

n = int(input())
for a in sorted([tuple(map(int, input().split())) for _ in range(n)]): print(*a)

ZeroJudge 解題筆記：a746. 画蛇添足

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


ZeroJudge 題目連結：a746. 画蛇添足

解題想法

這題的測資 2 有空行，如果用 Python 需要過濾掉空行，否則會出錯。而且這題的記憶體限制很嚴格，如果用 Python 直接産生 $(n+2) \times (n+2)$ 的二維串列會超過記憶體上限。

Python 程式碼

第3行是為了濾掉測資中的空行，但是這樣測試不會過，因為本題的記憶體限制很嚴格，在第 7 行産生 $(n+2) \times (n+2)$ 的二維串列時會超過記憶體上限。

import sys

lines = [line for line in sys.stdin.readlines() if line.strip()]
idx = 0

while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    grid = [[" "]*(n+2) for _ in range(n+2)]
    for c in range(n+2):
        grid[0][c] = grid[n+1][c] = "-"
    for r in range(1, n+1):
        grid[r][0] = grid[r][n+1] = "|"
    ri, ci = map(int, lines[idx].split())
    idx += 1
    for _ in range(m-1):
        rf, cf = map(int, lines[idx].split())
        idx += 1
        if ri == rf:
            for c in range(min(ci, cf), max(ci, cf)+1):
                grid[ri][c] = "*"
        elif ci == cf:
            for r in range(min(ri, rf), max(ri, rf)+1):
                grid[r][ci] = "*"
        ri, ci = rf, cf
    for row in grid:
        sys.stdout.write("".join(row) + "\n")

ZeroJudge 解題筆記：a740. 质因数之和

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


ZeroJudge 題目連結：a740. 质因数之和

解題想法

測試 i = 2 ~ 根號 x 是否為 x 的因數，如果 i 是因數就繼續將 x 縮小為 1/i，直到 i 不是因數為止。最後如果 x 不等於 1，代表此時 x 是某一個質數，答案再加上 x。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)
    ans = 0
    for i in range(2, int(x**0.5)+1):  # 測試 2 ~ 根號 x
        while x%i == 0:  # 如果 i 可以整除 x
            ans += i  # 加上 i
            x //= i  # x 變為 1/i
    if x != 1: ans += x  # 如果 x 不是 1，x 為質數
    sys.stdout.write(f"{ans:d}\n")

ZeroJudge 解題筆記：a694. 吞食天地二

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


ZeroJudge 題目連結：a694. 吞食天地二

解題想法

題目中的 x 軸應該是對應到列，y 軸對應到欄，有點奇怪。解題技巧主要利用的是二維前綴和，産生前綴和的原則

psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1]

因為 $psum[i-1][j-1]$ 會被多加一次，最後要扣掉。用前綴和取範圍 $[r1, c1]$ 到 $[r2, c2]$ 區間和的原則

isum = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]

因為 $psum[r1-1][c1-1]$ 會被多扣一次，最後要加回來。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    psum = [[0]*(n+1) for _ in range(n+1)]  # 最上面、最左邊補 0
    for i in range(1, n+1):  # 讀取 n 行資料
        row = [0] + list(map(int, sys.stdin.readline().split()))
        for j in range(1, n+1):  # 處理前綴和
            psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + row[j]
    for _ in range(m):  # 讀取 m 行
        r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
        isum = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]
        sys.stdout.write(f"{isum:d}\n")

ZeroJudge 解題筆記：a693. 吞食天地

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


ZeroJudge 題目連結：a693. 吞食天地

解題想法

用前綴和解題，如果要求陣列中索引值 [left, right] 的區間和，即為前綴和 psum[right] - psum[left-1]。

Python 程式碼

逐行讀取測資、輸出結果，使用時間約為 0.5 s，記憶體約為 11.8 MB，通過測試。如果改用 print 輸出答案，使用時間約為 1.2 s，記憶體約為 11.7 MB。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    psum = [0] + list(map(int, sys.stdin.readline().split()))
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, sys.stdin.readline().split())
        isum = psum[right] - psum[left-1]
        sys.stdout.write(f"{isum:d}\n")

一次讀取所有測資，最後再一次輸出所有結果，使用時間約為 0.5 s，記憶體約為 36.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    psum = [0] + list(map(int, lines[idx].split()))
    idx += 1
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, lines[idx].split())
        idx += 1
        isum = psum[right] - psum[left-1]
        result.append(f"{isum:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a248. 新手訓練 ~ 陣列應用

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


ZeroJudge 題目連結：a248. 新手訓練 ~ 陣列應用

解題想法

理論上這題是要先計算 a, b 相除的商，接著再取 a %= b，每次將 a 乘以 10 倍之後除以 b，計算小數的部分直到 n 位數為止，但是這個作法在 Python 會太慢。反而可以利用 Python 支援大數運算的特性，直接將 a%b 乘以 $10^n$ 再除以 b 計算小數的部分，但是要記得在小數部分前面補 0 到 n 位數。

Python 程式碼

寫法1，超時。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.rstrip(): continue
    a, b, n = map(int, line.split())
    int_part = a//b
    a %= b
    res = [f"{int_part:d}."]
    for _ in range(n):
        a *= 10
        c = a//b
        res.append(f"{c:d}")
        a %= b
    result.append("".join(res) + "\n")
sys.stdout.write("".join(result))

寫法2，大數運算，使用時間約為 0.5 s，記憶體約為 17.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.rstrip(): continue
    a, b, n = map(int, line.split())
    int_part = a//b
    dec_part = str(a%b*(10**n) // b).zfill(n)
    result.append(f"{int_part:d}.{dec_part}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a528. 大數排序

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


ZeroJudge 題目連結：a528. 大數排序

解題想法

因為 Python 支援大數運算，可以直接排序。C++ 則要用字串格式，分成兩個字串 a、b 開頭都是 +，開頭都是 -，a 正 b 負、a 負 b 正，共 4 種狀況排序。

Python 程式碼

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

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    nums = sorted([int(sys.stdin.readline()) for _ in range(n)])
    result = [f"{num:d}\n" for num in nums]
    sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a524. 手機之謎

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


ZeroJudge 題目連結：a524. 手機之謎

解題想法

這題在 Python 可以用 itertools.permutations，在 C++ 可以用 algorithm 函式庫的 prev_permutation 産生所有的排列，速度很快。也可以用函式遞迴産生所有的排列方式。由於測資有空行，用 Python 解題時要記得跳過空行，否則會吃 RE。

Python 程式碼

寫法1，用 itertools.permutations 産生所有的排列，使用時間約為 0.2 s，記憶體約為 7.5 MB，通過測試。

import sys
from itertools import permutations

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    for arr in permutations(range(n, 0, -1), n):  # 從 n ~ 1 的數字取 n 個排列
        res = [f"{a:d}" for a in arr]  # arr 的內容轉成字串存入 res
        result.append("".join(res) + "\n")  # res 接成一個字串加入 result
sys.stdout.write("".join(result))  # 一次輸出所有的結果

寫法2，用函式遞迴窮舉所有的排列，使用時間約為 0.4 s，記憶體約為 7.5 MB，通過測試。

import sys

result = []
def perm(arr, nums, used, depth):
    # 代入已選數字串列 arr, 可用數字串列 nums，已選數字的集合 used，目標長度 depth
    if len(arr) == depth:  # 遞迴出口，如果 arr 長度等於 depth
        result.append("".join([f"{a:d}" for a in arr]) + "\n")  # 接成字串加入 result
        return
    for num in nums:  # 依序由 nums 讀取數字
        if num in used: continue  # 如果 num 已用過，找下一個數字
        arr.append(num)  # num 接到 arr 最後面
        used.add(num)  # num 加入 used
        perm(arr, nums, used, depth)  # 遞迴
        arr.pop()  # 從 arr 最後面移除數字
        used.remove(num)  # 從 used 移除 num

lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    perm([], list(range(n, 0, -1)), set(), n)
sys.stdout.write("".join(result))  # 一次輸出所有的結果

ZeroJudge 解題筆記：a417. 螺旋矩陣

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


ZeroJudge 題目連結：a417. 螺旋矩陣

解題想法

我是先填完矩陣的值再輸出，速度會慢一點。

Python 程式碼

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

def draw(n, m):
    ### 填格子 ###
    if m == 1:  # 方向順序是右、下、左、上
        dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)
    else:  # 方向順序是下、右、上、左
        dr, dc = (1, 0, -1, 0), (0, 1, 0, -1)
    matrix = [[0]*n for _ in range(n)]  # n*n 矩陣，預設值皆為 0
    r, c, v = 0, 0, 1  # 座標 (r, c)，值為 1
    d = 0  # 一開始朝右方或下
    while v < n*n:  # 還沒有填完
        matrix[r][c] = v  # 設定此格的值
        nr, nc = r+dr[d], c+dc[d]  # 要走的格子
        if nr < 0 or nr >= n or nc < 0 or nc >= n or matrix[nr][nc] != 0:  # 出界或已經填過了
            d = (d+1)%4  # 轉向
            nr, nc = r+dr[d], c+dc[d]  # 更新 (nr, nc)
        r, c = nr, nc  # 走到 (nr, nc)
        v += 1  # 值加 1
    matrix[r][c] = v  # 設定最後一格的值
    ### 輸出 ###
    for row in matrix:
        for c, v in enumerate(row):
            print(f"{v:5d}", end="\n" if c == n-1 else "")

T = int(input())
for t in range(T):
    if t > 1: print()
    draw(*map(int, input().split()))

ZeroJudge 解題筆記：a414. 位元運算之進位篇

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


ZeroJudge 題目連結：a414. 位元運算之進位篇

解題想法

假設二進位制數字 $n$ 要加 1，其進位次數等於 $n$ 從最右側向左算共有幾個連續的 1。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 65.9 MB，通過測試。這題的測資量很大，用 print 輸出會很慢，大約要 2 s。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n == 0: break
    cnt = 0
    while n&1:
        n >>= 1
        cnt += 1
    result.append(f"{cnt:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a410. 解方程

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


ZeroJudge 題目連結：a410. 解方程

解題想法

這題用克拉瑪公式，假設二元一次方程式為 $$ \left\{\begin{matrix} a_1 x + b_1 y &= c_1 \\ a_2 x + b_2 y &= c_2 \end{matrix}\right. $$ 令 $$ \Delta = \begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{vmatrix} ~~~~~\Delta_x = \begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \end{vmatrix} ~~~~~\Delta_y = \begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \end{vmatrix} $$ 有以下三種狀況

1. 如果 $\Delta \neq 0$，方程式恰有一組解，其解為 $x = \frac{\Delta_x}{\Delta}, ~ y = \frac{\Delta_y}{\Delta}$
2. 如果 $\Delta = 0$，但 $\Delta_x, \Delta_y$ 至少有一個不為 0，無解。
3. 如果 $\Delta = \Delta_x = \Delta_y = 0$，無限多組解。

Python 程式碼

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

a1, b1, c1, a2, b2, c2 = map(int, input().split())
delta = a1*b2 - a2*b1
deltax = c1*b2 - c2*b1
deltay = a1*c2 - a2*c1
if delta != 0:  # 恰有一組解
    print(f"x={deltax/delta:.2f}")
    print(f"y={deltay/delta:.2f}")
else:
    if deltax != 0 or deltay != 0: print("No answer")   # 無解
    elif deltax == 0 and deltay == 0: print("Too many") # 無窮多組解

ZeroJudge 解題筆記：a291. nAnB problem

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


ZeroJudge 題目連結：a291. nAnB problem

解題想法

先掃過一次答案與猜測的數字，計算位置、數字都對的數量 A，如果不是位置、數字都對，則用兩個串列記錄 0 ~ 9 各個數字的數量。接下來再掃過這兩個串列，計算位置不對、數字對的數量 B。但是這一題我在 Python 上遇到很大的困難，換了好幾種寫法都超時，用 C++ 會過關但是速度還不夠快，需要改變寫法。

Python 程式碼

超時。

import sys
   
result = []
for line in sys.stdin:
    if not line.rstrip(): continue
    ans = list(map(int, line.split()))
    n = int(sys.stdin.readline())
    for _ in range(n):
        guess = list(map(int, sys.stdin.readline().split()))
        A, B = 0, 0  # 位置、數字都對的數量 A，位置不對、數字對的數量 B
        cnt_a, cnt_g = [0]*10, [0]*10  # 0 ~ 9 各個數字的數量
        for a, g in zip(ans, guess):  # 先掃一輪
            if a == g: A += 1  # 位置、數字都對，A 加 1
            else:  # 反之，記錄數字對應的數量
                cnt_a[a] += 1
                cnt_g[g] += 1
        for a, g in zip(cnt_a, cnt_g):  # 計算 B 的數量
            if a >= g: B += g
            else: B += a
        result.append(f"{A:d}A{B:d}B\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a229. 括號匹配問題

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


ZeroJudge 題目連結：a229. 括號匹配問題

解題想法

我用函式遞迴枚舉所有可能的組合，但是 Python 的部分一直超時，C++ 的部分用 string 儲存字串會超時，要用字元陣列才能過關。

Python 程式碼

寫法1，用字串儲存答案，超時。

import sys

def solve(n):
    """
    輸入括號對數 n，枚舉所有合法的組合
    """
    if n == 0: return [""]  # 特例，回傳只有空字串的串列
    result = []  # 儲存組合用的串列
    def backtrack(curr, left, right):
        """
        回溯，輸入現在的字串 curr、左括號數量 left、右括號數量 right
        """
        if left == n and right == n:  # 找到新的組合，加到 result
            result.append(f"{curr}\n")
            return
        if left < n:  # 如果左括號數量不夠，回溯，加上 (
            backtrack(curr+"(", left+1, right)
        if right < left:  # 如果右括號比左括號少，回溯，加上 )
            backtrack(curr+")", left, right+1)
    ### End of backtrack ###
    backtrack("", 0, 0)  # 呼叫 backtrack
    return result

ca = 0
for line in sys.stdin:
    if not line.rstrip(): continue
    ca += 1
    if ca > 1: sys.stdout.write("\n")
    sys.stdout.write("".join(solve(int(line))))

ZeroJudge 解題筆記：a225. 明明愛排列

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


ZeroJudge 題目連結：a225. 明明愛排列

解題想法

這題在 Python 可以用內建的排序工具 sort，搭配 functools.cmp_to_key 與自訂比較式；在 C++ 可以用 algorithm 函式庫的 sort，搭配 lambda function 自訂比較式，寫起來會快很多。

Python 程式碼

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

import sys
from functools import cmp_to_key

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

for line in sys.stdin:
    n = int(line)
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort(key = cmp_to_key(mycmp))
    print(*arr)

ZeroJudge 解題筆記：a224. 明明愛明明

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


ZeroJudge 題目連結：a224. 明明愛明明

解題想法

先將所有字母轉成小寫，再用字典或表格計數，計算每個字母出現的次數，同時計算所有字母的數量 n。如果 n 是奇數，只能有一個字母的數量是奇數；如果 n 是偶數，所有的字母數量都必須是偶數。

Python 程式碼

寫法1，字典計數，使用時間約為 22 ms，記憶體約為 3.6 MB，通過測試。

import sys
from collections import defaultdict

def check(s):
    n = 0
    cnt = defaultdict(int)
    for c in s.lower():
        n += 1
        if c.isalpha():
            cnt[c] += 1
    even = sum(v%2 for v in cnt.values())
    if n%2 == 1:
        return even <= 1
    else:
        return even == 0

for line in sys.stdin:
    print("yes !" if check(line.rstrip()) else "no...")

ZeroJudge 解題筆記：a216. 數數愛明明

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


ZeroJudge 題目連結：a216. 數數愛明明

解題想法

方法1，使用函式遞迴，但是可能會因為遞迴次數太多而超時。方法2，找一般式，例如 $$ \begin{align*} f(1) &= 1\\ f(2) &= 2 + f(1)\\ f(3) &= 3 + f(3)\\ & \vdots \\ f(n) &= n + f(n-1) \end{align*} $$ 將以上式子相加可得 $$ f(n) = 1 + 2 + 3 + \dots + n = \frac{1}{2} \cdot n(n+1) $$ 接下來求 $g(n)$，先列出幾行 $$ \begin{align*} g(1) &= 1\\ g(2) &= f(2) + g(1)\\ g(3) &= f(3) + g(2)\\ & \vdots \\ g(n) &= f(n) + g(n-1) \end{align*} $$ 將以上式子相加可得 \begin{align*} g(n) &= f(1) + f(2) + f(3) + \dots + f(n)\\ &= \frac{1}{2} \sum_{i=1}^n (i^2 + i)\\ &= \frac{1}{2} \cdot \left [ \frac{1}{6} \cdot n(n+1)(2n+1) + \frac{1}{2} \cdot n(n+1) \right ]\\ &= \frac{1}{12} \cdot n(n+1) \left [ (2n+1) + 3 \right ] \\ &= \frac{1}{6} \cdot n(n+1)(n+2)\\ \end{align*}

Python 程式碼

方法1，使用函式遞迴，果然不意外地在測試題會超時。

import sys

def f(n):
    if n == 1: return 1
    else: return n + f(n-1)

def g(n):
    if n == 1: return 1
    else: return f(n) + g(n-1)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

方法2，找出一般式直接代入 n 求答案，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def f(n):
    return int(n*(n+1)/2)

def g(n):
    return int(n*(n+1)*(n+2)/6)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

ZeroJudge 解題筆記：a054. 電話客服中心

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


ZeroJudge 題目連結：a054. 電話客服中心

解題想法

先取英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起，存到一個對應的陣列之中。依照規則計算數字部分的編碼 code，加上英文字母對應的值要能被 10 整除，因此答案就是 (10 - code%10) % 10 對應的字母。

Python 程式碼

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

# 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
letters = ("BNZ", "AMW", "KLY", "JVX", "HU", "GT", "FS", "ER", "DOQ", "CIP")
s = input()  # 身分證字號
# 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
code = sum(int(c)*(8-i) for i, c in enumerate(s[:9])) + int(s[-1])
print(letters[(10 - code%10) % 10])

C++ 程式碼

使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
    string letters[10] = {"BNZ", "AMW", "KLY", "JVX", "HU", 
                          "GT", "FS", "ER", "DOQ", "CIP"};
    string s; cin >> s;  // 身分證字號
    // 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
    int code = 0;
    for(int i=0; i<9; i++) code += (s[i]-'0')*(8-i);
    code += s.back() - '0';
    cout << letters[(10 - code%10) % 10] << "\n";
    return 0;
}

ZeroJudge 解題筆記：a020. 身分證檢驗

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


ZeroJudge 題目連結：a020. 身分證檢驗

解題想法

英文字母轉換成整數的部分沒有固定的規律，用字典儲存對照會比較簡單。

Python 程式碼

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

letter = {"A": 10, "B": 11, "C": 12, "D": 13, "E": 14, "F": 15,
          "G": 16, "H": 17, "I": 34, "J": 18, "K": 19, "L": 20,
          "M": 21, "N": 22, "O": 35, "P": 23, "Q": 24, "R": 25,
          "S": 26, "T": 27, "U": 28, "V": 29, "W": 32, "X": 30,
          "Y": 31, "Z": 33}

s = input()
first = letter[s[0]]
code = first//10 + first%10*9
for i, c in enumerate(s[1:9], start=1): code += int(c)*(9-i)
code += int(s[-1])
print("real" if code%10 == 0 else "fake")

ZeroJudge 解題筆記：f698. 後序運算式求值

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


ZeroJudge 題目連結：f698. 後序運算式求值

解題想法

依序讀取算式的每個字串，如果是數字就轉成整數存入堆疊；如果是運算符號，從疊堆最上面取出兩個數字，依照運算符號種類計算兩個數字，再將計算結果存入堆疊。最後堆疊裡只會剩下一個整數，就是答案。

Python 程式碼

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

ans = []
for d in input().split():
    if d not in "+-*/":
        ans.append(int(d))
    elif d == "+":
        a = ans.pop(); b = ans.pop()
        ans.append(b + a)
    elif d == "-":
        a = ans.pop(); b = ans.pop()
        ans.append(b - a)
    elif d == "*":
        a = ans.pop(); b = ans.pop()
        ans.append(b * a)
    elif d == "/":
        a = ans.pop(); b = ans.pop()
        ans.append(b // a)
print(ans[0])

ZeroJudge 解題筆記：f377. 運算式轉換

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


ZeroJudge 題目連結：f377. 運算式轉換

解題想法

用堆疊處理算式，同時要注意括號配對的狀況。

Python 程式碼

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

import sys

for line in sys.stdin:
    tmp = []                                 # 暫存運算子及變數的串列
    ans = []                                 # 儲存答案的串列
    for d in line.split():                   # 依序從串列 data 取出字元並儲存到變數 d
        if d == ")":                         # 若 d 為 )
            while tmp[-1] != "(":            # 當 tmp 最後一項不是 ( 繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.pop()                        # 結束 while 迴圈後移除 tmp 最後一項，此時為 (
        elif d == "(":                       # 若 d 為 )
            tmp.append(d)                    # 將 d 加到 tmp 最後面
        elif d in "*/":                      # 若 d 為 */
            while tmp and tmp[-1] in "*/":   # 當 tmp 之中有資料且最後一項為 */ 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        elif d in "+-":                      # 若 d 為 ＋＝
            while tmp and tmp[-1] in "+-*/": # 當 tmp 之中有資料且最後一項為 +-*/ 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        else:                                # 若 d 不為 ()+-*/ 即為變數
            ans.append(d)                    # 直接加到 ans 最後面 
    # 移除 tmp 最後一項並加到 ans 最後面，直到 tmp 無資料時停止
    while tmp: ans.append(tmp.pop())
    print(*ans)

ZeroJudge 解題筆記：a017. 五則運算

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


ZeroJudge 題目連結：a017. 五則運算

解題想法

這題如果用 Python 解題，可以直接用 eval 求值。但是 Online Judge 網站通常不能使用 eval，還是要用堆疊處理算式。

Python 程式碼

由於題目要求用整數計算數值，需要先用 replace 將 / 換成 //。使用時間約為 21 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    print(eval(line.replace("/", "//")))

將所有的程式碼寫在同一行，使用時間約為 21 ms，記憶體約為 3.3 MB，通過測試。

[print(eval(line.replace("/", "//"))) for line in __import__("sys").stdin]

以下是採用 f377. 運算式轉換，將輸入的測資轉成後序運算式，再用 f698. 後序運算式的寫法，由後序運算式求值。使用時間約為 22 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    data = list(line.split())                # 輸入的測資儲存到串列 data
    tmp = []                                 # 暫存運算子及變數的串列
    ans = []                                 # 儲存後序運算資料的串列
    # 由輸入的測資轉成後序運算資料
    for d in data:                           # 依序從串列 data 取出字元並儲存到變數 d
        if d == ")":                         # 若 d 為 )
            while tmp[-1] != "(":            # 當 tmp 最後一項不是 ( 繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.pop()                        # 結束 while 迴圈後移除 tmp 最後一項，此時為 (
        elif d == "(":                       # 若 d 為 )
            tmp.append(d)                    # 將 d 加到 tmp 最後面
        elif d in "*/%":                     # 若 d 為 */%
            while tmp and tmp[-1] in "*/%":  # 當 tmp 之中有資料且最後一項為 */% 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        elif d in "+-":                      # 若 d 為 ＋＝
            while tmp and tmp[-1] in "+-*/%":# 當 tmp 之中有資料且最後一項為 +-*/% 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        else:                                # 若 d 不為 ()+-*/% 即為變數
            ans.append(d)                    # 直接加到 ans 最後面 
        #print("tmp = ", tmp)
        #print("ans = ", ans)
    # 移除 tmp 最後一項並加到 ans 最後面，直到 tmp 無資料時停止
    while tmp: ans.append(tmp.pop())
    # 由處理過的後序運算資料 ans 計算結果
    func = { "+": int.__add__,       # int.__add__(a, b) = a.__add__(b) = a + b
             "-": int.__rsub__,      # int.__rsub__(a, b) = a.__rsub__(b) = b - a 
             "*": int.__mul__,       # int.__mul__(a, b) = a.__mul__(b) = a * b
             "/": int.__rfloordiv__, # int.__rfloordiv__(a, b) = a.__rfloordiv__(b) = b // a
             "%": int.__rmod__       # int.__rmod__(a, b) = a.__rmod__(b) = b % a
            }
    result = []
    for a in ans:
        if a not in "+-*/%":         # 如果 a 不是 +-*/% 則為數字
            result.append(int(a))    # 加到 result 最後面
        else:   # 如果 a 是 +-*/% 其中一個，代入字典物件 func 轉成對應的函式，取出 result 最後兩個元素並代入求值
            result.append(func[a](result.pop(), result.pop()))
    print(result[0])

ZeroJudge 解題筆記：a034. 二進位制轉換

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


ZeroJudge 題目連結：a034. 二進位制轉換

解題想法

因為 Python 有內建整數轉成二進位字串的工具 bin，可以直接用 bin 解題。比較一般的作法是用 while 迴圈及位元運算，從個位數開始依序計算此位是 1 或 0，用字串儲存答案。

Python 程式碼

先用 int 將輸入字串 line 轉成整數，再用 bin 轉成2進位制，但是直接輸出時開頭會有 **0b**，所以再用 str 轉換成字串，只從索引值為2的位置開始輸出。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。
使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    print(str(bin(int(line)))[2:])

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

import sys

def convert(n):
    s = ""
    while n > 0:
        s = str(n&1) + s
        n >>= 1
    return s

for line in sys.stdin:
    print(convert(int(line)))

ZeroJudge 解題筆記：a015. 矩陣的翻轉

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


ZeroJudge 題目連結：a015. 矩陣的翻轉

解題想法

用二維陣列儲存矩陣資料，輸出時將列、欄的順序反過來就行了。

Python 程式碼

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

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 矩陣 m*n
    matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
    for c in range(n):
        for r in range(m):
            print(matrix[r][c], end="\n" if r == m-1 else " ")

ZeroJudge 解題筆記：a013. 羅馬數字

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


ZeroJudge 題目連結：a013. 羅馬數字

解題想法

這題最麻煩的地方在於 900、400、90、40、9、4 的轉換，分別換成 CM、CD、XC、XL、IX、IV。程式碼寫起來很長，我想不到更精簡的寫法。

Python 程式碼

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

import sys

# 羅馬數字字串 s 換成整數
def rton(s):
    # 字母換成對應的整數
    cton = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1}
    n = n1 = cton[s[0]]  # 第1位數
    for c in s[1:]:  # 依序讀取 s[1] ~ s[-1]
        n2 = cton[c]  # 對應的整數 n2
        if n2 > n1:  # 如果 n2 較大，n 加上 n2，減掉 2 倍 n1
            n = n - 2*n1 + n2
        else:  # 反之，直接加上 n2
            n = n + n2
        n1 = n2  # 更新 n1
    return n  # 回傳 n

# 整數換成羅馬數字
def ntor(n):
    s = ""  # 儲存結果用的空字串
    # 處理 1000 的倍數
    M = n//1000; s += "M"*M; n %= 1000
    # 處理 500 的倍數
    D = n//500; s += "D"*D; n %= 500
    # 處理 100 的倍數
    C = n//100; n %= 100
    if C == 4 and D == 1:  # 900
        s = s[:-1]  # 刪除最後一位
        s += "CM"  # 加上 "CM"
    elif C == 4 and D == 0:  # 400
        s += "CD"  # 加上 "CM"
    else: s += "C"*C  # 其它狀況，加上 C 個 "C"
    # 處理 50 的倍數
    L = n//50; n %= 50
    if L == 1: s += "L"  # 如果 L 等於 1，加上 "L"
    # 處理 10 的倍數
    X = n//10; n %= 10
    if X == 4 and L == 1:  # 90
        s = s[:-1]  # 刪除最後一位
        s += "XC"  # 加上 "XC"
    elif X == 4 and L == 0:  # 40
        s += "XL"  # 加上 "XL"
    else: s += "X"*X  # 其它狀況，加上 X 個 "X"
    # 處理 5 的倍數
    V = n//5; n %= 5
    if V == 1: s += "V"  # 如果 V 等於 1，加上 "V"
    # 處理 1
    I = n
    if I == 4 and V == 1:  # 9
        s = s[:-1]  # 刪除最後一位
        s += "IX"  # 加上 "IX"
    elif I == 4 and V == 0:  # 4
        s += "IV"  # 加上 "IV"
    else: s += "I"*I  # 其它狀況，加上 I 個 "I"
    # 回傳結果
    return s

for line in sys.stdin:
    if line.rstrip() == "#": break
    a, b = line.split()  # 羅馬數字 a, b
    na, nb = rton(a), rton(b)  # 轉成整數 na, nb
    diff = abs(na - nb)  # 差值
    print("ZERO" if diff == 0 else ntor(diff))

ZeroJudge 解題筆記：e925. pD. 學號檢查

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


ZeroJudge 題目連結：e925. pD. 學號檢查

解題想法

要檢查 4 個部分：

1. 大學部學號開頭要是 B
2. s[1], s[2] 必須是數字
3. s[3:7] 要在院、系、所的集合之中
4. s[7], s[8] 必須是數字

Python 程式碼

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

n = int(input())  # n 個院、系、組
dep = set(input() for _ in range(n))  # 院、系、組編號
cnt = 0  # 不合法的學號數量
for _ in range(10):  # 讀取 10 行資料
    s = input()  # 學號
    # 大學部學號開頭要是 B，s[1:3] 必須是數字，s[3:7] 要在 dep 之中，s[7:] 必須是數字
    if s[0] == 'B' and s[1:3].isdigit() and s[3:7] in dep and s[7:].isdigit():
        print("Y")  # 合法，印出 Y
    else:
        print("N")  # 不合法，印出 N
        cnt += 1  # 不合法的數量加 1
if cnt == 0: print("0")  # 全部合法，印出 0
elif cnt == 10: print("1")  # 全部不合法，印出 1
else: print(f"0.{cnt:d}")  # 其它狀況，印出 0.X

ZeroJudge 解題筆記：a010. 因數分解

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


ZeroJudge 題目連結：a010. 因數分解

解題想法

因為測資 n 不大，依序測試 2 ~ n 是否為因數，如果這個數字 i 是因數就繼續除下去，同時將 n 縮小為 n/i，直到 n 不能被整除為止，就能夠得到因數及對應的次方。

Python 程式碼

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

n = int(input())  # 要測試的數
ans = []  # 答案
fac = 2  # 要測試的因數，從 2 開始
""" 找因數及次方 """
while n > 1 and fac <= n:  # 如果 n 大於 1 且 fac 小於等於 n，還可以分解，繼續執行
    cnt = 0  # 次方
    while n%fac == 0:  # 如果 n 可以被 fac 整除，繼續執行
        cnt += 1; n //= fac  # 次方加 1，n 變為除以 fac 的值
    if cnt == 1:  # 如果次方等於 1
        ans.append(f"{fac:d}")  # ans 加入 fac
    elif cnt > 1:  # 如果次方大於 1
        ans.append(f"{fac:d}^{cnt:d}")  # ans 加入 fac 及次方
    fac += 1  # fac 加 1
""" 輸出答案 """
if not ans: print(n)  # 如果 ans 是空的，n 是質數，印出 n
else: print(" * ".join(ans))  # 反之，用 " * " 連接 ans 再輸出

ZeroJudge 解題筆記：a006. 一元二次方程式

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


ZeroJudge 題目連結：a006. 一元二次方程式

解題想法

先找判別式 $D = b^2 - 4ac$，如果 $D > 0$ 有相異實根，如果 $D = 0$ 為重根，如果 $D < 0$ 沒有實根。如果在 Python 可以用 math.sqrt 或是 0.5 次方開根號，如果在 C++ 可以用 cmath 函式庫的 sqrt 開根號。

Python 程式碼

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

import math

a, b, c = map(int, input().split())
D = b**2 - 4*a*c

if D > 0:
    x1 = int((-b + math.sqrt(D))/(2*a))
    x2 = int((-b - math.sqrt(D))/(2*a))
    print(f"Two different roots x1={x1:d} , x2={x2:d}")
elif D == 0:
    x = int(-b/(2*a))
    print(f"Two same roots x={x:d}")
else:
    print("No real root")

ZeroJudge 解題筆記：a005. Eva 的回家作業

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


ZeroJudge 題目連結：a005. Eva 的回家作業

解題想法

用迴圈檢查前 4 項是等差或等比數列，再補上第 5 項，最後輸出這 5 項。

Python 程式碼

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

t = int(input())
for _ in range(t):
    arr = list(map(int, input().split()))
    state = True  # True 為等差, False 為等比
    d = arr[1] - arr[0]  # 公差
    for i in range(1, 3):  # 檢查 arr[1] ~ arr[3]
        if arr[i+1] - arr[i] != d:  # 如果差不相等，為等比數列
            state = False
            break
    if state:  # 等差數列
        arr.append(arr[3] + d)
    else:  # 等比數列，題目保證是整數
        arr.append(arr[3] * (arr[3] // arr[2]))
    print(*arr)

ZeroJudge 解題筆記：p902. 凱撒密碼 (Cipher)

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


ZeroJudge 題目連結：p902. 凱撒密碼 (Cipher)

解題想法

用字母的 ASCII 編號平移後再除以 26 取餘數，換成平移後的字母。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = line.strip()  # 要加密的字串
    k = int(input())  # 位移量
    a = ""  # 儲存答案用的空字串
    for c in s:  # 從 s 依序讀取字元 c
        if c.islower():  # 如果 c 是小寫字母
            c = chr((ord(c)+k-ord('a'))%26 + ord('a'))
        elif c.isupper():  # 如果 c 是大寫字母
            c = chr((ord(c)+k-ord('A'))%26 + ord('A'))
        a += c  # a 加上 c
    print(a)

ZeroJudge 解題筆記：a981. 求和問題

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


ZeroJudge 題目連結：a981. 求和問題

解題想法

這題要用遞迴窮舉所有的組合，輸出其中符合條件的組合，並且要適當地剪枝，節省運算時間。不過我在 Python 一直沒有寫出能夠過關的程式碼，最後一筆測資超時。

Python 程式碼

最後一筆測資超時。

def solve():
    import sys
    lines = sys.stdin.readlines()
    head = 0
    while head < len(lines):
        n, m = map(int, lines[head].split())  # 讀取數量 n，要找的加總 m
        nums = sorted(list(map(int, lines[head+1].split())))  # 讀取候選的數值
        head += 2  # 從 lines 讀取資料的索引值
        choice = [False]*n  # 是否選這個數字
        have_ans = False  # 是否有解
        ### 主要的解題過程，輸入目前檢測的 nums 索引值，加總 ###
        def backtrack(curr, total):
            nonlocal have_ans  # 這樣才能改變外層 have_ans 的值
            if total == m:  # 有解，印出選擇的數字，結束遞迴
                have_ans = True
                solution = " ".join([str(num) for i, num in enumerate(nums) if choice[i]])
                sys.stdout.write(f"{solution}\n")
                return
            if curr == n or total > m: return # 已出界或是目標為負值，結束遞迴
            choice[curr] = True  # 選此項
            backtrack(curr + 1, total + nums[curr])  # 遞迴，索引值加 1，total 加上此項的值
            choice[curr] = False  # 回溯，不選此項
            backtrack(curr + 1, total)  # 遞迴，索引值加 1，total 不變
        ### End of backtrack ###
        backtrack(0, 0)  # 從索引值 0、加總 0 開始
        if not have_ans: sys.stdout.write("-1\n")  # 如果無解，印出 -1
        
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：p901. 香料 (Spices)

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


ZeroJudge 題目連結：p901. 香料 (Spices)

解題想法

這題用字典儲存每個編號的香料在貨架上的位置，速度較慢但程式好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個要找的香料
    si = list(map(int, input().split()))  # 要找的香料編號
    r, c = map(int, input().split())  # 貨架 r*c
    shelf = [list(map(int, input().split())) for _ in range(r)]  # 貨架上的香料編號
    table = dict()  # 各編號香料的位置
    for i in range(r):  # 依序掃過貨架每一格
        for j in range(c):
            table[shelf[i][j]] = (i+1, j+1)  # 題目的編號從 1 開始
    for s in si:  # 依序讀取要找的香料編號
        if s not in table: print(-1)  # 如果 s 不在 table 之中印出 -1
        else: print(*table[s])  # 反之印出編號

ZeroJudge 解題筆記：p900. 旅遊計畫 (Travel)

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


ZeroJudge 題目連結：p900. 旅遊計畫 (Travel)

解題想法

完整地掃過 i = 0 ~ 9 天的去程費用，再掃過 j = i ~ 9 的回程費用，更新最低費用。

Python 程式碼

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

import sys

for line in sys.stdin:
    going_trip = tuple(map(int, line .split()))  # 去程費用
    return_trip = tuple(map(int, input().split()))  # 回程費用
    start, end, imin = 0, 0, float('inf')  # 出發日、回程日、最低費用
    for i in range(10):  # 依序掃過 i = 0 ~ 9
        for j in range(i, 10):  # 依序掃過 j = i ~ 9
            fee = going_trip[i] + return_trip[j] + (j-i)*1000  # 費用
            if fee < imin:  # 如果是新的最低費用，更新 start, end, imin
                start, end, imin = i+1, j+1, fee
    print(start, end, imin)

ZeroJudge 解題筆記：o923. 陣列運算 (Array)

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


ZeroJudge 題目連結：o923. 陣列運算 (Array)

解題想法

我沒有想到比較快的作法，就是依照題目的規定處理陣列 1 或 2，直到輸出是 0 為止。

Python 程式碼

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

import sys

for line in sys.stdin:
    a = list(map(int, line.split()))  # 陣列 1
    b = list(map(int, input().split()))  # 陣列 2
    c = 1  # 輸出的值，預設為 1
    while c:  # 當 c 不是 0，繼續執行
        if c%2 == 1:  # 如果上一輪輸出是奇數，處理陣列 1
            if a[0]%3 == 0:  # 如果 a[0] 可以被 3 整除
                imax = max(a)  # 找出陣列 1 的最大值
                print(imax)  # 印出 imax
                c = imax  # 重設輸出的值
                for i in range(5):  # 掃過 a，如果 a[i] 等於 imax 則除以 2
                    if a[i] == imax: a[i] = imax//2
            else:  # 如果 a[0] 不能被 3 整除
                imin = 10000  # 最小值，預設為超出題目範圍的值
                for x in a:  # 依序掃過 a，找非 0 的最小值
                    if 0 < x < imin: imin = x
                print(imin)  # 印出最小值
                c = imin  # 重設輸出的值
                for i in range(5):  # 掃過 a，如果 a[i] 等於 imin 則減 1
                    if a[i] == imin: a[i] = imin-1
        else:  # 如果上一輪輸出是偶數，處理陣列 2
            if b[0]%3 == 0:  # 如果 b[0] 可以被 3 整除
                imax = max(b)  # 找出陣列 2 的最大值
                print(imax)  # 印出 imax
                c = imax  # 重設輸出的值
                for i in range(5):  # 掃過 b，如果 b[i] 等於 imax 則除以 2
                    if b[i] == imax: b[i] = imax//2
            else:  # 如果 b[0] 不能被 3 整除
                imin = 10000  # 最小值，預設為超出題目範圍的值
                for x in b:  # 依序掃過 b，找非 0 的最小值
                    if 0 < x < imin: imin = x
                print(imin)  # 印出最小值
                c = imin  # 重設輸出的值
                for i in range(5):  # 掃過 b，如果 b[i] 等於 imin 則減 1
                    if b[i] == imin: b[i] = imin-1

ZeroJudge 解題筆記：o922. 年貨大街 (Market)

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


ZeroJudge 題目連結：o922. 年貨大街 (Market)

解題想法

依序讀取商品編號及質量，計算總金額即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 款商品
    ps = [0] + list(map(int, input().split()))  # 各商品每公克價格，配合從1開始編號開頭加 0
    total = 0  # 總金額
    while True:  # 無窮迴圈
        x, g = map(int, input().split())  # x 商品買 g 公克
        if x == 0 and g == 0: break  # x, g 都是 0，中止迴圈
        total += ps[x]*g  # 更新 total
    print(total)

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

import sys

for line in sys.stdin:
    n = int(line)  # n 款商品
    ps = [0] + list(map(int, input().split()))  # 各商品每公克價格，配合從1開始編號開頭加 0
    total = 0  # 總金額
    x, g = -1, -1  # x 商品買 g 公克
    while x != 0 and g != 0:  # x, g 都是 0，中止迴圈
        x, g = map(int, input().split())  # x 商品買 g 公克
        total += ps[x]*g  # 更新 total
    print(total)

ZeroJudge 解題筆記：o921. 生日快樂 (Birthday)

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


ZeroJudge 題目連結：o921. 生日快樂 (Birthday)

解題想法

我會先將今天的日期及生日換算成從1月1日開始計算的天數，這樣在計算答案時比較方便。

Python 程式碼

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

import sys

month = (0, 31, 59, 90, 120, 151, 181,
         212, 243, 273, 304, 334, 365)  # 每月累計天數
for line in sys.stdin:
    m, d = map(int, line.split())  # 今天的月日
    today = month[m-1] + d  # 今天轉成從1月1日開始的天數
    mb, db = map(int, input().split())  # 生日的月日
    birthday = month[mb-1] + db  # 生日轉成從1月1日開始的天數
    print((birthday - today + 365) % 365)

ZeroJudge 解題筆記：o580. 因數計算 (Factor)

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


ZeroJudge 題目連結：o580. 因數計算 (Factor)

解題想法

我先寫一個找因數用的函式 num_of_factor，輸入整數 x，用 set 儲存 x 的因數，最後回傳因數的數量。在主程式中，讀取要找的範圍 start、end，依序找 start 到 end 的因數數量並更新答案。

Python 程式碼

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

import sys

def num_of_factor(x):  # 輸入 x，找 x 的因數
    factor = {1, x}  # 因數，一定有 1, x
    for i in range(2, int(x**0.5)+1):  # 暴力解，找 i = 2 ~ sqrt(x)
        if x%i == 0:  # 如果 x 可以被 i 整除
            factor.add(i)  # i 是 x 的因數
            factor.add(x//i)  # x//i 是 x 的因數
    return len(factor)  # 回傳因數的數量

for line in sys.stdin:
    start, end = map(int, line.split())  # 要計算 start ~ end 的因數數量
    ans, imax = 0, 0  # 因數最多的數字 ans，因數數量 imax
    for i in range(start, end+1):  # 依序代入 start ~ end
        fac = num_of_factor(i)  # 呼叫 num_of_factor 計算 i 的因數數量
        if fac > imax:  # 如果 fac 大於 imax，更新 ans 及 imax
            ans = i; imax = fac
    print(ans, imax)

ZeroJudge 解題筆記：n912. 吸血鬼 (Vampire)

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


ZeroJudge 題目連結：n912. 吸血鬼 (Vampire)

解題想法

我是用 BFS 及四方位檢查，依序更新每天獵人及吸血鬼的勢力範圍。

Python 程式碼

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

import sys

for line in sys.stdin:
    H, W, K = map(int, line.split())  # 地圖 H*W，K 天
    grid = [list(map(int, input().split())) + [2] for _ in range(H)]  # 地圖，每列最右側加一個 2
    grid.append([2]*(W+1))  # 最下方加一列 2
    hunter, vampire = set(), set()  # 獵人、吸血鬼位置
    for r in range(H):  # 依序掃過每一格，找出獵人、吸血鬼位置
        for c in range(W):
            if grid[r][c] == 1: hunter.add((r, c))
            elif grid[r][c] == -1: vampire.add((r, c))
    for _ in range(K):  # 執行 K 次
        ### 獵人行動回合 ###
        ht = []  # 暫存新的獵人位置
        for r, c in hunter:  # 依序讀取獵人位置
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
                if grid[nr][nc] == 1 or grid[nr][nc] == 2: continue  # 如果是獵人或出界，找下一格
                grid[nr][nc] = 1  # (nr, nc) 改為 1
                ht.append((nr, nc))  # (nr, nc) 加到 ht
        for h in ht: hunter.add(h)  # 將 ht 的資料加到 hunter
        ### 吸血鬼行動回合 ###
        vt = []  # 暫存新的吸血鬼位置
        for r, c in vampire:  # 依序讀取吸血鬼位置
            for dr, dc in ((1, 1), (1, -1), (-1, -1), (-1, 1)):  # 斜向四方位檢查
                nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
                if grid[nr][nc] == 0:
                    grid[nr][nc] = -1  # 如果是未佔領區域，改成 -1
                    vt.append((nr, nc))  # (nr, nc) 加到 ht
        for v in vt: vampire.add(v)  # 將 vt 的資料加到 vampire
        for h in ht:  # 將 ht 的資料從 vampire 移除
            if h in vampire: vampire.remove(h)
    for row in grid[:H]: print(*row[:W])  # 印出答案，不含最右側、最下方的 2

ZeroJudge 解題筆記：n910. 數織 (Nonogram)

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


ZeroJudge 題目連結：n910. 數織 (Nonogram)

解題想法

先處理每欄的提示，依序讀取此欄每列的資料，計算此欄有幾個連續的 1，如果沒有任何 1 則填入 0。再處理每列的提示，依序讀取此列每欄的資料，計算此列有幾個連續的 1，如果沒有任何 1 則填入 0。

Python 程式碼

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

import sys

for line in sys.stdin:
    N = int(line)  # 圖形 N*N
    grid = [list(map(int, input().split())) for _ in range(N)]  # 讀取地圖
    for c in range(N):  # 依序讀取每欄資料
        col = []  # 每欄提示
        cnt = 0  # 連續的 1 數量
        for r in range(N):  # 依序讀取每列資料
            if cnt != 0:  # 如果 cnt 不等於 0
                if grid[r][c] == 1: cnt += 1  # 如果 grid[r][c] 等於 1，cnt 加 1
                else:  # 如果 grid[r][c] 等於 0
                    col.append(cnt)  # 結算 cnt，將 cnt 加到 col
                    cnt = 0  # cnt 歸零
            elif grid[r][c] == 1: cnt = 1  # 如果 cnt 等於 0 而且 grid[r][c] 等於 1，cnt 設定為 1
        if cnt != 0: col.append(cnt)  # 如果 cnt 不等於 0，要再結算一次 cnt
        if col: print(*col)  # 如果 col 有資料，拆開後印出
        else: print(0)  # 如果 col 沒有資料，印出 0
    for r in range(N):  # 依序讀取每列資料
        row = []  # 每列提示
        cnt = 0  # 連續的 1 數量
        for c in range(N):  # 依序讀取每欄資料
            if cnt != 0:  # 如果 cnt 不等於 0
                if grid[r][c] == 1: cnt += 1  # 如果 grid[r][c] 等於 1，cnt 加 1
                else::  # 如果 grid[r][c] 等於 0
                    row.append(cnt)  # 結算 cnt，將 cnt 加到 col
                    cnt = 0  # cnt 歸零
            elif grid[r][c] == 1: cnt = 1  # 如果 cnt 等於 0 而且 grid[r][c] 等於 1，cnt 設定為 1
        if cnt != 0: row.append(cnt)  # 如果 cnt 不等於 0，要再結算一次 cnt
        if row: print(*row)  # 如果 row 有資料，拆開後印出
        else: print(0)  # 如果 row 沒有資料，印出 0

ZeroJudge 解題筆記：>n632. 熱門商品 (Commodity)

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


ZeroJudge 題目連結：n632. 熱門商品 (Commodity)

解題想法

因為商品的編號不連續，用字典計數比較方便，在 Python 中可以用預設的字典，也可以用 collections 函式庫中的 defaultdict 或 Counter，由於這題要找問卷中出現最多次的商品編號，用 Counter.most_common() 最方便。在 C++ 可以用 map 或 unordered_map，因為資料不需要排序，用 unordered_map 會比較快一點。

Python 程式碼

寫法1，使用預設的 dict。使用時間約為 0.8 s，記憶體約為 78.4 MB，通過測試。

import sys

for line in sys.stdin:
    K, N = map(int, line.split())  # K 份問卷，N 家商店
    cnt = dict()  # 問卷計數器
    for i in map(int, input().split()):  # 讀取問卷資料
        if i not in cnt: cnt[i] = 1  # 如果 i 不在 cnt 之中，cnt[i] 設定為 1
        else: cnt[i] += 1  # 如果 i 在 cnt 之中，cnt[i] 加 1
    popular = max([(v, k) for k, v in cnt.items()])[1]  # 最受歡迎的商品
    _ = tuple(map(int, input().split()))  # 每家商店的商品數量，用不到
    shop, imin = 0, float('inf')  # 積分最低的商店編號及分數
    for i in range(1, N+1):  # 依序讀取 N 家商店
        score = 0  # 積分
        for j in map(int, input().split()):  # 依序讀取這家商店販賣的商品
            if j in cnt: score += cnt[j]  # 如果有出現在問卷中，分數加 cnt[j]
        if score < imin:  # 更新 shop 及 imin
            shop = i; imin = score
    print(popular, shop)  # 印出答案

ZeroJudge 解題筆記：n631. 撲克 (Poker)

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


ZeroJudge 題目連結：n631. 撲克 (Poker)

解題想法

這題我用表格計數，計算 1 ~ 52 各有幾張牌，最少的張數就是完整的套牌數量。最後再完整地掃過表格，計算要補的張數。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 張牌
    cnt = [0]*53  # 1 ~ 52 號各有幾張，開頭多一個 0
    for i in map(int, input().split()): cnt[i] += 1  # 讀取 n 張牌，更新 cnt[i]
    imax = max(cnt)  # 同一張牌最多的數量
    deck = min(cnt[1:])  # 有幾套完整的牌
    need = 0  # 要補幾張牌
    for i in range(1, 53):  # 依序檢查每一張牌
        need += imax - cnt[i]  # 更新 need
    print(deck, need)

ZeroJudge 解題筆記：n630. 電影院 (Cinema)

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


ZeroJudge 題目連結：n630. 電影院 (Cinema)

解題想法

這題要注意輸出的格式，時、分都是兩位數，前面要補0。計算電影開場時刻的過程，將單位都換成分鐘會比較方便。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 部電影
    movie = [tuple(map(int, input().split())) for _ in range(n)]  # 電影開場時刻
    h0, m0 = map(int, input().split())  # 現在的時刻
    t0 = h0*60 + m0 + 20  # 現在的時刻加 20 分鐘，並以分鐘為單位
    idx = -1  # 第 idx 部電影
    for i, (h, m) in enumerate(movie):  # 依序讀取電影開場時刻
        t = h*60 + m  # 電影開場時刻換成分鐘
        if t >= t0:
            idx = i; break  # 更新 idx
    if idx == -1: print("Too Late")
    else: print(f"{movie[idx][0]:02d} {movie[idx][1]:02d}")

ZeroJudge 解題筆記：n362. 質數遊戲 (Primes)

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


ZeroJudge 題目連結：n362. 質數遊戲 (Primes)

解題想法

先寫一個函式 prime 判斷輸入的數字是否為質數；再寫另一個函式 solve，判斷輸入的數字是否可以由兩個質數相除。由於測資不太，如果輸入的數字是 $n$，這兩個函式都只要測試 $2$ 到 $\sqrt{n}$ 即可。

Python 程式碼

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

import sys

def prime(n):  # 檢查是否為質數
    for i in range(2, int(n**0.5)+1):  # 測試 2 ~ sqrt(n)
        if n%i == 0: return False  # 不是質數
    return True  # 是質數

def solve(n):  # 自訂函式求解
    for a in range(2, int(n**0.5)+1):  # 測試可能的因數 2 ~ sqrt(n)
        if n%a == 0:  # 如果 a 是因數
            b = n//a  # 另一個數
            if prime(a) and prime(b):  # 如果 a, b 都是質數
                print(a, b); return  # 印出 a, b，跳出函式
    print(0, 0)  # 印出 0, 0

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

ZeroJudge 解題筆記：n361. 數字旅館 (hotel)

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


ZeroJudge 題目連結：n361. 數字旅館 (hotel)

解題想法

按照題目給的 3 個條件判斷房號即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    for i, a in enumerate(map(int, input().split())):  # 依序讀取房號 a
        if a%3 == 0 and a%2 == 0: print("1", end='')
        elif a&1 and a%3: print("2", end='')
        elif a == int(a**0.5)*int(a**0.5) or (a%7 and a%2 == 0): print("3", end='')
        else: print("0", end='')
        print("", end='\n' if i == n-1 else ' ')

也可以先將答案存入串列，最後再一起印出來。使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    ans = []
    for i, a in enumerate(map(int, input().split())):  # 依序讀取房號 a
        if a%3 == 0 and a%2 == 0: ans.append(1)
        elif a&1 and a%3: ans.append(2)
        elif a == int(a**0.5)*int(a**0.5) or (a%7 and a%2 == 0): ans.append(3)
        else: ans.append(0)
    print(*ans)

ZeroJudge 解題筆記：m907. 方程式 (Equation)

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


ZeroJudge 題目連結：m907. 方程式 (Equation)

解題想法

我將這題分成 3 個部分：中序轉後序、由後序運算式求值、解方程式，分別寫一個對應的函式，在主程式中呼叫這 3 個函式解題。

Python 程式碼

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

import sys

def infix_to_postfix(tokens):  # 中序轉後序
    st = []  # 暫存運算子用的堆疊
    postfix = []  # 儲存後序運算式的串列
    precedence = {'(': 0, '+':1, '*': 2}  # 運算子優先順序
    for token in tokens:  # 由 tokens 依序讀取 token
        if token.isnumeric() or token == 'x':  # 如果 token 是數字或 k
            postfix.append(token)  # 直接加入 postfix
        elif token == '(':  # 如果 token 是 (
            st.append(token)  # 先加入 st
        elif token == ')':  # 如果 token 是 )
            while st and st[-1] != '(':  # 如果 st 還有資料而且最後一項是 (
                postfix.append(st.pop())  # 移除 st 最後一項並加入 postfix
            st.pop()  # 移除 st 最後一項的 (
        elif token in precedence:  # 如果 token 在 precedence 之中
            while st and st[-1] != '(' and precedence[token] <= precedence[st[-1]]:  # 如果 token 的優先順序小於等於 st 的最後一項
                postfix.append(st.pop())  # 移除 st 最後一項並加入 postfix
            st.append(token)  # token 加入 st
    while st:  # 清空 st，加到 postfix
        postfix.append(st.pop())
    return postfix  # 回傳 postfix

def myevaluate(postfix):  # 由後序運算式求值，於 ZeroJudge 名稱不能用 evaluate_postfix 或 evaluate
    st = []  # 暫存用的堆疊，內容為 (x 項係數, 常數項)
    for token in postfix:  # 由 postfix 依序讀取 token
        if token.isnumeric():  # 如果 token 是數字
            st.append((0, int(token)))  # token 轉成整數再加入 st
        elif token == 'x':  # 如果 token 是 x
            st.append((1, 0))  # x 項係數 1 加入 st
        elif token == '+':  # 如果 token 是 +
            x1, c1 = st.pop()  # 取出 st 最後兩項，相加後再加入 st
            x2, c2 = st.pop()
            st.append((x1+x2, c1+c2))
        elif token == '*':  # 如果 token 是 *
            x1, c1 = st.pop()  # 取出 st 最後兩項，相乘後再加入 st
            x2, c2 = st.pop()
            st.append((x1*c2 + x2*c1, c1*c2))  # 題目保證沒有 x 平方項
    return st[-1][0], st[-1][1]  # 回傳 st 最後一項

def solve_equation(left_side, right_side):  # 解方程式，代入左、右側式子
    left_x, left_c = myevaluate(infix_to_postfix(left_side.split()))
    right_x, right_c = myevaluate(infix_to_postfix(right_side.split()))
    return (right_c - left_c) // (left_x - right_x)

for line in sys.stdin:
    left_side = line.strip()  # 左側式子
    right_side = input().strip()  # 右側式子
    print(solve_equation(left_side, right_side))

ZeroJudge 解題筆記：m900. 色彩轉換 (Color)

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


ZeroJudge 題目連結：m900. 色彩轉換 (Color)

解題想法

按照題目給的公式換算即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    R, G, B = map(int, line.split())  # 紅、綠、藍比例 0 ~ 255
    imax, imin = max(R, G, B), min(R, G, B)  # 最大值、最小值
    L = imax + imin  # 平均值*2
    H, S = 0, 0  # H, S 值，預設為 0
    ### 計算 H ###
    if imax == imin: H = 0 # 如果 imax 等於 imin
    elif imax == R:  # 如果 imax 等於 R
        if G >= B: H = 60*(G-B)/(imax-imin)  # G 大於等於 B
        else: H = 60*(G-B)/(imax-imin) + 360  # G 小於 B
    elif imax == G: H = 60*(B-R)/(imax-imin) + 120  # 如果 imax 等於 G
    else: H = 60*(R-G)/(imax-imin) + 240  # 如果 imax 等於 B
    ### 計算 S  ###
    if imax == imin or L == 0: S = 0  # 如果 imax 等於 imin 或 L 等於 0
    elif 0 < L <= 255: S = (imax-imin)/(imax+imin)  # 如果 0 < L <= 255
    else: S = (imax-imin)/(510-imax-imin)  # 如果 L > 255
    H, S, L = round(H), round(S*255), round(L/2)
    print(H, S, L)

ZeroJudge 解題筆記：m802. 填字遊戲 (Puzzle)

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



ZeroJudge 題目連結：m802. 填字遊戲 (Puzzle)

解題想法

這題只有向下、向右填入字元兩種解法，依照測資檢查是否能填入指定的單字即可。注意，這題給的格子座標 (x, y) 是 (c, r)，跟二維陣列的索引值順序相反。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 格子維度
    grid = [['0']*n for _ in range(n)]  # 格子 n*n，先填入字元 0
    m = int(input())  # 填入 m 個單字
    solve = True  # 是否有解
    for _ in range(m):  # 執行 m 次
        d, s, c, r = input().split()  # 方向 d，字串 s，座標 (r, c)
        r, c = int(r), int(c)
        if d == 'V':  # 向下填
            if grid[r][c] != '0' and grid[r][c] != s[0]:  # 先檢查開頭，如果已填入字元而且不等於 s[0]
                solve = False  # 無解
            else: grid[r][c] = s[0]  # 填入 s[0]
            for j in range(1, len(s)):  # 往下填入剩下的字元
                nr = r+j  # 新的列
                if nr >= n or (grid[nr][c] != '0' and grid[nr][c] != s[j]):  # 如果出界或已填入字元而且不等於 s[j]
                    solve = False; break  # 無解，中止迴圈
                else: grid[nr][c] = s[j]  # 填入 s[j]
        elif d == 'H':  # 向右填
            if grid[r][c] != '0' and grid[r][c] != s[0]:  # 先檢查開頭，如果已填入字元而且不等於 s[0]
                solve = False  # 無解
            else: grid[r][c] = s[0]  # 填入 s[0]
            for j in range(1, len(s)):  # 往右填入剩下的字元
                nc = c+j  # 新的欄
                if nc >= n or (grid[r][nc] != '0' and grid[r][nc] != s[j]):  # 如果出界或已填入字元而且不等於 s[j]
                    solve = False; break  # 無解
                else: grid[r][nc] = s[j]  # 填入 s[j]
    print("Yes" if solve else "No")  # 印出答案

ZeroJudge 解題筆記：m801. 鏡像對稱 (Mirror)

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



ZeroJudge 題目連結：m801. 鏡像對稱 (Mirror)

解題想法

這題除了迴文字串的條件之外，另外要求字母必須是 AHIMOTUVWXY。

Python 程式碼

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

import sys

def test(s):
    letters = "AHIMOTUVWXY"  # 合法的字元
    n = len(s)  # s 的長度
    for i in range(n//2):  # 檢查是否為迴文，是否為合法的字元
        if s[i] != s[n-i-1] or s[i] not in letters or s[n-i-1] not in letters:
            return False
    if n%2 == 1 and s[n//2] not in letters:  # 如果 n 是奇數，再檢查一次中央的字元
        return False
    return True  # 如果以上的 return 都沒有觸發，符合要求，回傳 True

for line in sys.stdin:
    print("Yes" if test(line.strip()) else "No")

ZeroJudge 解題筆記：m800. 辦公室 (Office)

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



ZeroJudge 題目連結：m800. 辦公室 (Office)

解題想法

這題我沒有想到比較快的寫法。依序檢查每一格四周的格子比自己高或低的數量，將變化量儲存到另一個陣列，最後再更新每一格的值，重複以上的過程 k 次。

Python 程式碼

只能通過4筆測資然後就超時了。

import sys

for line in sys.stdin:
    h, w, k = map(int, line.split())  # 平面圖 h*w，共 k 天
    start = 0  # 一開始的加總 start
    grid = []  # 平面圖 grid
    for _ in range(h):  # 讀取 h 行資料
        grid.append(list(map(int, input().split())))
        start += sum(grid[-1])
    tmp = [0]*(h*w)  # 暫存變化量用的陣列，改成一維，節省記憶體
    for _ in range(k):  # 更新 k 次
        for r in range(h):  # 依序檢查每一格
            for c in range(w):
                tot, large, small = 0, 0, 0  # 四周共有 tot 格，比自己大的數量 large，比自己小的數量 small
                for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                    nr, nc = r+dr, c+dc  # 要檢查的位置 (nr, nc)
                    if nr < 0 or nr >= h or nc < 0 or nc >= w: continue  # 如果 (nr, nc) 出界，找下一個
                    tot += 1  # 更新 tot
                    if grid[nr][nc] > grid[r][c]: large += 1  # 更新 large
                    elif grid[nr][nc] < grid[r][c]: small += 1  # 更新 small
                if 2*large > tot: tmp[r*w + c] = 1  # 如果 large 過半，tmp[r*w + c] 等於 1
                elif 2*small > tot: tmp[r*w + c] = -1  # 如果 small 過半，tmp[r*w + c] 等於 -1
                else: tmp[r*w + c] = 0  # 否則 tmp[r*w + c] 等於 0
        for r in range(h):  # 更新每一格的值
            for c in range(w):
                grid[r][c] += tmp[r*w + c]
    end = 0  # k 天後的加總
    for row in grid: end += sum(row)
    print(end-start)  # 印出答案

ZeroJudge 解題筆記：m583. 精靈王國 (Kingdom)

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



ZeroJudge 題目連結：m583. 精靈王國 (Kingdom)

解題想法

我用一層 for 迴圈掃過所有的傳送點，如果這個點已經走過就找下一個點，如果還沒有走過就將它歸零；接下來再用一層 while 迴圈，不斷地找傳送到的下一個點 nxt，直到 nxt 等於 0 為止。

Python 程式碼

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

import sys

for line in sys.stdin:
    k = int(line)  # k 個傳送點
    imax = 0  # 同一個王國中最多的傳送點數量
    arr = [0] + list(map(int, input().split()))  # 傳送點資料，開頭多一個 0，改成 0 代表已走訪
    for i in range(1, k+1):  # 依序走訪傳送點 1 ~ k
        if arr[i] == 0: continue  # 如果 arr[i] 等於 0，找下一個點
        cnt = 0  # 同一個王國中的傳送點數量
        nxt = arr[i]  # 下一個位置
        arr[i] = 0  # 已走訪 arr[i]
        while nxt != 0:  # 繼續執行直到 nxt 等於 0
            cnt += 1  # cnt 加 1
            tmp = arr[nxt]  # 暫存 arr[nxt] 到 tmp
            arr[nxt] = 0  # 已走訪 arr[nxt]
            nxt = tmp  # 更新 nxt
        imax = max(imax, cnt)  # 更新 imax
    print(imax)

ZeroJudge 解題筆記：m582. 書房 (Study)

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



ZeroJudge 題目連結：m582. 書房 (Study)

解題想法

用一個陣列儲存答案，索引值是碎片編號減 1，內容為所在書架編號。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 個書架，m 張碎片
    ans = [0]*m  # 儲存答案用的串列，索引值是碎片編號減 1，內容為所在書架編號
    for i, a in enumerate(map(int, input().split()), start=1):  # 依序讀取各書架的碎片編號
        if a != 0: ans[a-1] = i  # 如果 a 不等於 0，設定 ans
    print(*ans)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n, m;  // n 個書架，m 張碎片
    while(scanf("%d %d", &n, &m) != EOF) {
        int ans[m];  // 儲存答案用的串列，索引值是碎片編號減 1，內容為所在書架編號
        for(int i=1; i<=n; i++) {  // 依序讀取各書架的碎片編號
            int a; scanf("%d", &a);
            if (a != 0) ans[a-1] = i;  // 如果 a 不等於 0，設定 ans
        }
        for(int i=0; i<m; i++) {
            printf("%d", ans[i]);
            if (i == m-1) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}

ZeroJudge 解題筆記：m581. 狼人殺 (Werewolves)

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



ZeroJudge 題目連結：m581. 狼人殺 (Werewolves)

解題想法

不斷讀取要淘汰的人編號，直到讀到 0、無解或是沒有狼人為止。特別容易出錯的地方在於，如果無解，仍然需要讀完測資，不能直接 break。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    arr = [-2] + list(map(int, input().split()))  # 每個人的身份，配合編號開頭多一項，-2 為已淘汰
    werewolves = sum([a == -1 for a in arr])  # 狼人數量
    solve = True  # 是否有解
    while True:  # 不斷讀取要淘汰的人
        k = int(input())  # 要淘汰的人編號
        if k == 0: break  # 讀到 0 中止迴圈
        elif arr[k] == -2:  # 如果 k 號已淘汰
            solve = False  # 無解，但是要讀完資料，不能 break
        else:
            if arr[k] == -1: werewolves -= 1  # 如果 k 號是狼人，數量減 1
            arr[k] = -2  # k 號淘汰
    if not solve: print("Wrong")  # 無解，印出 Wrong
    elif werewolves == 0: print("Townsfolk")  # 好人陣營獲勝
    else: print("Werewolves")  # 狼人陣營獲勝

ZeroJudge 解題筆記：m398. 超市排隊 (Supermarket)

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



ZeroJudge 題目連結：m398. 超市排隊 (Supermarket)

解題想法

依序計算三個櫃枱所需時間，再更新最短時間即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    abc = list(map(int, line.split()))  # 三個櫃枱的人數
    idx, imin = 0, float('inf')  # 櫃枱編號及所需最短時間
    for i, n in enumerate(abc, start=1):  # 依序讀取三個櫃枱的人數
        arr = list(map(int, input().split()))  # 每個顧客購買的商品數量
        t = 2 * (n - 1)  # 顧客前進所需時間
        for d in arr: t += 3*d # 依序讀取商品數量並更新時間
        if t < imin:  # 如果 t 小於 imin
            idx = i; imin = t  # 更新 idx 及 imin
    print(idx, imin)

ZeroJudge 解題筆記：m397. 烤肉 (BBQ)

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



ZeroJudge 題目連結：m397. 烤肉 (BBQ)

解題想法

注意，其中一種可能是 0 串。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m, x, y = map(int, line.split())  # 共 n 元，m 串，單價 x 元、y 元
    solve = False  # 是否有解
    for i in range(m+1):  # 依序檢查 0 ~ m 串
        j = m-i  # 另一種有 m-i 串
        if i*x + j*y == n:  # 有解
            solve = True; print(i, j); break
    if not solve: print("-1 -1")

ZeroJudge 解題筆記：l925. P.8 值班警衛 (Guard)

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



ZeroJudge 題目連結：l925. P.8 值班警衛 (Guard)

解題想法

産生警衛的組合之後立刻檢查這個組合是否能覆蓋所有的邊，不需要把所有組合都儲存起來，可以少用一點記憶體。

Python 程式碼

寫法1，産生所有可能的警衛組合，先存入串列中，最後才檢查每個組合是否能覆蓋所有的邊。最後一筆測資超出記憶體上限。

import sys

def sove(N, M, edges):  # 輸入節點數量N、邊的數量M、邊 edges
    # 産生所有可能的組合
    all_combs = []
    for i in range(1 << N):  # i = 0 ~ 2**N - 1
        comb = []  # 組合
        for j in range(N):  # j = 0 ~ N-1
            if (i >> j) & 1:  # 如果 i 向右移 j 位等於 1，comb 加入 j
                comb.append(j + 1)  # 因為編號從 1 開始
        all_combs.append(comb)  # comb 加入 all_combs
    # 找到可以複蓋所有邊而且數量最少的組合
    imin = N  # 最少的數量，預設為所有的節點數量N
    for comb in all_combs:  # 依序從 all_combs 取出 comb
        covered = True  # 是否覆蓋所有的邊，預設為 True
        for u, v in edges:  # 從 edges 依序讀取每個邊的端點 u, v
            if u not in comb and v not in comb:  # 如果 u, v 都不在 comb 之中
                covered = False; break  # comb 不能覆蓋所有的邊，中止迴圈
        if covered: imin = min(imin, len(comb))  # 如果 comb 可以覆蓋所有的邊，更新 imin
    return imin  # 回傳 imin

for line in sys.stdin:
    N, M = map(int, line.split())
    edges = [list(map(int, input().split())) for _ in range(M)]
    print(min_guards(N, M, edges))

寫法2，由寫法1修改而成，産生警衛的組合之後立刻檢查這個組合是否能覆蓋所有的邊，可以少用一點記憶體。使用時間約為 2 s，記憶體約為 3.3 MB，通過測試。

import sys

def solve(N, M, edges):  # 輸入節點數量N、邊的數量M、邊 edges
    imin = N  # 最少的數量，預設為所有的節點數量N
    for i in range(1 << N):  # i = 0 ~ 2**N - 1
        comb = []  # 組合
        for j in range(N):  # j = 0 ~ N-1
            if (i >> j) & 1:  # 如果 i 向右移 j 位等於 1，comb 加入 j
                comb.append(j + 1)  # 因為編號從 1 開始
        covered = True  # 是否覆蓋所有的邊，預設為 True
        for u, v in edges:  # 從 edges 依序讀取每個邊的端點 u, v
            if u not in comb and v not in comb:  # 如果 u, v 都不在 comb 之中
                covered = False; break  # comb 不能覆蓋所有的邊，中止迴圈
        if covered: imin = min(imin, len(comb))  # 如果 comb 可以覆蓋所有的邊，更新 imin
    return imin  # 回傳 imin

for line in sys.stdin:
    N, M = map(int, line.split())
    edges = [list(map(int, input().split())) for _ in range(M)]
    print(solve(N, M, edges))

ZeroJudge 解題筆記：l924. P.7 搜集寶藏 (Treasure)

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



ZeroJudge 題目連結：l924. P.7 搜集寶藏 (Treasure)

解題想法

但是這題的記憶體限制很嚴格，如果先將所有格子的資料存進二維陣列，不論是用 Python 或 C++ 記憶體都不夠。如果改用滾動陣列節省記憶體，Python 還是無法通過，C++ 勉強可以過關。

Python 程式碼

寫法1，先將所有格子的資料存進二維串列。但是這題的記憶體限制很嚴格，我用 Python 解題在第 2、5、8、9、12、18 筆測資記憶體爆掉。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 地圖 n*m
    grid = [list(map(int, input().split())) for _ in range(n)]  # 讀取地圖資料
    for i in range(1, n):  # 處理第 0 欄
        grid[i][0] += grid[i-1][0]
    for j in range(1, m):  # 處理第 0 列
        grid[0][j] += grid[0][j-1]
    for i in range(1, n):  # 處理 grid[1][1] ~ grid[n-1][m-1]
        for j in range(1, m):
            grid[i][j] += max(grid[i-1][j], grid[i][j-1])
    print(grid[n-1][m-1])  # 答案在 grid[n-1][m-1]

寫法2，用滾動陣列節省記憶體，結果第2筆測資就超時。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 地圖 n*m
    pre = list(map(int, input().split()))  # 讀取第 0 列地圖資料
    for j in range(1, m):  # 處理第 0 列
        pre[j] += pre[j-1]
    for _ in range(1, n):  # 處理第 1 ~ n-1 列
        cur = list(map(int, input().split()))  # 讀取一列地圖資料
        cur[0] += pre[0]  # 處理第 0 欄
        for j in range(1, m):  # 依序更新第 1 ~ m-1 欄
            cur[j] += max(pre[j], cur[j-1])
        pre, cur = cur, pre  # 交換 pre, cur 的資料
    print(pre[m-1])  # 答案在 pre[n-1][m-1]

ZeroJudge 解題筆記：l922. P.5 古堡長廊 (Castle)

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



ZeroJudge 題目連結：l922. P.5 古堡長廊 (Castle)

解題想法

我用字典儲存英文單字對應的整數字元。讀取畫的字串及年份時，將年份轉成整數與單字對應的字元組成 tuple 或 pair，儲存到 list 或 vector 之中，依照年份排序，再將排序後的字元組成答案。

Python 程式碼

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

import sys

num = {"ONE": '1', "TWO": '2', "THREE": '3', "FOUR": '4', "FIVE": '5',
       "SIX": '6', "SEVEN": '7', "EIGHT": '8', "NINE": '9'}
for line in sys.stdin:
    n = int(line)  # n 幅畫
    data = []  # 資料
    for _ in range(n):  # 讀取 n 筆資料
        s, y = input().split()  # 字串 s，年份 y
        data.append((int(y), num[s]))  # y 轉成整數，s 代入 num 換成字元
    data.sort()  # 依照年份排序
    print(''.join([m for _, m in data]))  # 將字元組成字串再印出

ZeroJudge 解題筆記：l921. P.4 草圖 (Sketch)

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



ZeroJudge 題目連結：l921. P.4 草圖 (Sketch)

解題想法

因為這題要檢查的範圍比較大，要加兩層題目沒有用到的符號作為哨兵，避免走訪時出界。

Python 程式碼

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

import sys

# 右、右下、下、左下、左、左上、上、右上，距離2格，距離1格
two = ((0, 2), (2, 2), (2, 0), (2, -2), (0, -2), (-2, -2), (-2, 0), (-2, 2))
one = ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1))
sym = ('-', '\\', '|', '/', '-', '\\', '|', '/')

for line in sys.stdin:
    R = int(line)  # 圖形 (2*R - 1) * (2*R - 1)，要加上點之間的格子
    grid = [['#']*(2*R - 1) + ['!']*2 for _ in range(2*R - 1)]  # 圖形先填入 #，最後以 ! 作為哨兵
    grid += [['!']*(2*R +1), ['!']*(2*R +1)]  # 最下方加 2 列 ! 作為哨兵
    N = int(input())  # N 個點
    ps = []  # 點的位置
    for _ in range(N):  # 讀取 N 行資料
        r, c = map(int, input().split())  # 座標 (r, c)
        r *= 2; c *= 2  # 配合 grid 的維度要乘以 2
        ps.append((r, c))  # (r, c) 加入 ps
        grid[r][c] = '&'  # grid[r][c] 標記成 &
    for r, c in ps:  # 從 ps 依序取出點的座標
        for i in range(8):  # 8 方向檢查
            nr, nc = r+two[i][0], c+two[i][1]  # 要檢查的座標 (nr, nc)，距離 2 格
            if grid[nr][nc] == '&':  # 如果 grid[nr][nc] 是 &
                cr, cc = r+one[i][0], c+one[i][1]  # 距離 1 格的位置
                if grid[cr][cc] == '#':  # 如果 grid[cr][cc] 還沒有標記
                    grid[cr][cc] = sym[i]
                elif ((i == 3 or i == 7) and grid[cr][cc] == '\\') or \
                     ((i == 1 or i == 5) and grid[cr][cc] == '/'):
                    grid[cr][cc] = 'X'
    for row in grid[:2*R - 1]: print(''.join(row[:2*R - 1]))

ZeroJudge 解題筆記：fl920. P.3 建築倒塌 (Collapse)

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



ZeroJudge 題目連結：fl920. P.3 建築倒塌 (Collapse)

解題想法

這題可以用陣列儲存建築物狀態，不斷檢查每棟建築物是否需要更新狀態，直到沒有再更新狀態為止。如果改用集合儲存還要檢查的建築物位置，速度會更快一些。

Python 程式碼

寫法1，不斷檢查每棟建築物是否需要更新狀態，直到沒有再更新狀態為止。使用時間約為 0.3 s，記憶體約為 3.4 MB，通過測試。

import sys

def solve(s):  # 輸入建築物狀態
    n = len(s)  # 建築物數量
    if n <= 1:  # 特例，將 s 組成字串再印出，跳出函式
        print(''.join(s)); return
    cont = True  # 是否需要繼續更新狀態
    while cont:
        t = s[:]  # 暫存建築物狀態
        cont = False  # 先改成 False
        for i in range(n):  # 依序掃過每棟建築物
            if i == 0 and s[i] == 'X' and s[i+1] == 'L':  # 最左側建築物被右側建築物向左壓
                t[i] = 'L'; cont = True
            elif i == n-1 and s[n-1] == 'X' and s[n-2] == 'R':  # 最右側建築物被左側建築物向右壓
                t[n-1] = 'R'; cont = True
            elif 1 <= i <= n-2:  # 中間的建築物
                if s[i-1] == 'R' and s[i+1] == 'L':  # 左側向右倒，右側向左倒，中間不動
                    pass
                elif s[i-1] == 'R' and s[i] == 'X':  # 左側向右倒，中間原來還沒倒
                    t[i] = 'R'; cont = True
                elif s[i+1] == 'L' and s[i] == 'X':  # 右側向左倒，中間原來還沒倒
                    t[i] = 'L'; cont = True
        s = t[:]  # t 的資料存到 s
    print(''.join(s))  # 將 s 組成字串再印出

for arr in sys.stdin:
    arr = list(arr.strip())  # 建築物狀態
    solve(arr)

ZeroJudge 解題筆記：f934. 消失的二十年

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



ZeroJudge 題目連結：f934. 消失的二十年

解題想法

這是 l919. P.2 珠寶交易 (Jewel) ) 簡化題，只要計算一次買賣的最大獲利。

Python 程式碼

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

buy, profit = float('inf'), 0  # 最低買價，利潤
for p in map(int, input().split()):  # 讀取每天的價格
    buy = min(buy, p)  # 更新最低買價
    profit = max(profit, p - buy)  # 更新最大利潤
print(profit)

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

buy, profit = float('inf'), 0  # 最低買價，利潤
for p in map(int, input().split()):  # 讀取每天的價格
    if p < buy: buy = p  # 更新最低買價
    if p - buy > profit: profit = p - buy  # 更新最大利潤
print(profit)

ZeroJudge 解題筆記：l919. P.2 珠寶交易 (Jewel)

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



ZeroJudge 題目連結：l919. P.2 珠寶交易 (Jewel)

解題想法

這題理論上用貪心法就能解，有通過範例測資，但是無法送出解答。

Python 程式碼

無法送出解答。

import sys

for line in sys.stdin:
    n = int(line)  # n 天
    buy = float('inf')  # 最低買價，預設為正無窮大
    profit = 0  # 最大利潤，預設為 0
    best_buy_dat, best_sell_day = 0, 0  # 最佳買入、𧶠出時機
    buy_day = 0  # 買入時機
    for i, p in enumerate(map(int, input().split()), start=1):  # 第 i 天，價格 p
        if p < buy:  # 如果當天的價格小於 buy，更新 buy 及 buy_day
            buy = p; buy_day = i
        elif p - buy > profit:  # 價差大於 profit
            profit = p - buy  # 更新 profit
            best_sell_day = i  # 更新 sell_day
            best_buy_day = buy_day  # 更新 best_buy_day
    if profit > 0: print(best_buy_day, best_sell_day)
    else: print(-1)

ZeroJudge 解題筆記：l918. P1. 彈珠汽水 (Soda)

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



ZeroJudge 題目連結：l918. P1. 彈珠汽水 (Soda)

解題想法

這題有一個陷阱，如果 $N = 1$，每喝一瓶汽水就可以再換一瓶新的汽水，如果寫 while 迴圈的條件時只考慮是否還有沒喝的汽水，這樣會變成無窮迴圈。

Python 程式碼

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

m, n, k = map(int, input().split())  # m 瓶彈珠汽水，n 個瓶子再換一瓶汽水，想要喝到 k 瓶
t, b = 0, 0  # 總瓶數，空瓶數
while m > 0 and t < k:  # 如果還有沒喝的汽水而且還沒有喝到想要的瓶數
    t += m; b += m  # 更新 t, b，加上 m
    m = b//n  # 用空瓶換汽水
    b %= n  # 剩下的空瓶
print("YES" if t >= k else "NO")  # 依照 t 是否大於等於 k 印出答案

ZeroJudge 解題筆記：k931. P8. 切割蜂蜜 (Honey)

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



ZeroJudge 題目連結：k931. P8. 切割蜂蜜 (Honey)

解題想法

這題有 3 個重點：

1. 要設計儲存六角形蜂巢資料的方式，我是用二維串列，偶數列的欄位為 1, 3, 5, ...，奇數列的欄位為 0, 2, 4, ...，這個寫法的優點是讀取資料時索引值比較好寫，缺點是會浪費接近一半的二維串列空間。
2. 用動態規畫計算從左到右切割到每一格時最小的累積損失量，取這一格的左上、左側、左下之中的最小值，再加上這格原來的值。
3. 為了避免檢查邊界值要寫一堆 if，我選擇在四周 (C++) 或是最右側、最下方 (Python) 加上正無窮大的值當作哨兵，缺點是要多花一點記憶體。

經過測試，這個寫法在目前通過測試的人當中，C++ 及 Python 使用的時間都最短，可能其他人都很認真地檢查是否出界吧！

Python 程式碼

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

import sys

oo = float('inf')
for line in sys.stdin:
    H, W = map(int, line.split())  # 晶格的高與寬
    grid = [[-1]*(2*W+2) for _ in range(H)]  # 晶格 (H+1)*(2*W+2)
    grid.append([oo]*(2*W+2))  # 最下方補一列 oo
    for r in range(H):  # 讀取 H 行資料
        row = list(map(int, input().split()))
        if r%2 == 0:  # 如果是偶數列，欄位為 1, 3, 5, ..., 2*W - 1
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i+1] = v
            grid[r][2*W] = grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
        else:  # 如果是奇數列，欄位為 0, 2, 4, ..., 2*W
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i] = v
            grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
    # 動態規畫，grid[r][c] 改成到這格損失的值，加上左上、左側、左下最小值
    for c in range(2, 2*W+1):  # 依序掃過第 2 ~ 2*W 欄
        if c%2 == 0:  # 如果是偶數欄，列為 1, 3, 5, ...
            for r in range(1, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
        else:  # 如果是奇數欄，列為 0, 2, 4, ...
            for r in range(0, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
    # 找出答案，在每一列的最後一格，不含 oo
    ans = oo  # 答案預設為最大值
    for r in range(H):  # 依序掃過每一列
        if r%2 == 0: ans = min(ans, grid[r][2*W-1])  # 如果是偶數列
        else: ans = min(ans, grid[r][2*W])   # 如果是奇數列
    print(ans)

ZeroJudge 解題筆記：k930. P7. 興建圍籬 (Fence)

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



ZeroJudge 題目連結：k930. P7. 興建圍籬 (Fence)

解題想法

這題我用 BFS，但是在 Python 不論是用 deque 或 list 都太慢，在 C++ 用 queue 或 vector 都要跑 0.1 s。

Python 程式碼

寫法1，用 deque 儲存待走訪的佇列，但是速度不夠快，只能通過 60% 的測資。

import sys
from collections import deque

for line in sys.stdin:
    H, W = map(int, line.split())  # 地圖 H*W
    grid = [list(map(int, input().split())) for _ in range(H)]  # 讀取地圖
    num = 1  # 花地編號
    ans = []  # 答案
    for i in range(H):  # 依序掃過每一格
        for j in range(W):
            if grid[i][j] == 1:  # 如果此格是花地
                tot = 0  # 這區的圍籬數量
                que = deque([(i, j)])  # 待走訪的佇列
                num += 1  # 編號加 1
                while que:  # 如果 que 還有資料繼續執行
                    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
                    grid[r][c] = num  # 設定 grid[r][c] 的編號
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                        nr, nc = r+dr, c+dc  # 要檢查的格子 (nr, nc)
                        if 0 <= nr < H and 0 <= nc < W:  # 如果 nr, nc 沒有出界
                            if grid[nr][nc] == 1:  # 如果是還沒有編號的花地
                                grid[nr][nc] = num  # 設定編號
                                que.append((nr, nc))  # (nr, nc) 加入 que
                            elif grid[nr][nc] == 0:  # 如果是空地
                                tot += 1  # (r, c) 需要加一片圍籬
                ans.append(tot)  # 將 tot 加入 ans
    print(*sorted(ans))  # 將 ans 排序後印出

ZeroJudge 解題筆記：k926. P3. 錯字校正 (Correction)

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



ZeroJudge 題目連結：k926. P3. 錯字校正 (Correction)

解題想法

這題測資不大，按照題目的要求模擬替換字母的過程，最後再計算原來的字串與替換後的字串不同的字母數量即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = list(line.strip())  # 輸入的字串
    t = list(input().strip())  # 正確的字串
    n = int(input())  # 修正次數
    for _ in range(n):  # 讀取 n 行修正資料
        x, y = list(input().split())  # x 替換成 y
        for i in range(len(s)):  # 依序由 s 讀取字元
            if s[i] == x: s[i] = y  # 如果 s[i] 是 x 則換成 y
    diff = sum([a != b for a, b in zip(s, t)])  # 計算 s, t 之中對應位置不相同的字母數量
    print(diff)

ZeroJudge 解題筆記：k925. P2. 海底探險 (Adventure)

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



ZeroJudge 題目連結：k925. P2. 海底探險 (Adventure)

解題想法

這題我沒有想到比較簡潔的寫法，只能按照題目的敘述模擬烏龜的運動過程，程式碼寫起來很長。

Python 程式碼

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

import sys

def solve(L, T, hs):
    rem = T-1  # 剩下的探索時間，先減 1
    hmax = max(hs)  # 最高區塊高度
    imax = hs.index(hmax)  # 最高區塊位置
    t1 = hmax - hs[0]  # 上升到最高區塊高度需要的時間
    rem -= t1  # 更新 rem
    if rem <= 0: return 1  # 已經用完探索時間，還在起點區塊，回傳 1
    t2 = imax  # 向右游到最高區塊需要的時間
    rem -= t2  # 更新 rem
    if rem <= 0: return T-t1  # 向右游到的區塊 T-1-t1+1
    if imax == L-1:  # 如果游到最右邊
        hmin = min(hs[1:L-1])  # hs[1] ~ hs[L-2] 最低點
        imin = L-2 - hs[1:L-1][::-1].index(hmin)  # hs[1] ~ hs[L-2] 最低點位置
        t3 = L-1-imin  # 向左游到 imin 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return L-(rem+t3)  # 游到區塊 2 前時間就到了
        return imin + 1  # 可以游到區塊 imin + 1
    else:  # 不是游到最右邊
        hmax2 = max(hs[imax+1:])  # imax 右側最高的區塊高度
        imax2 = hs[imax+1:].index(hmax2) + imax + 1  # hmax2 的位置
        t3 = imax2-imax  # 向右游到 imin2 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return imax+rem+t3+1  # 游到 imax2 + 1 前時間就到了
        return imax2 + 1  # 可以游到 imax2 + 1

for line in sys.stdin:
    L = int(line)  # L 個區塊
    hs = list(map(int, input().split()))  # 各區塊高度
    T = int(input())  # 探索時間
    print(solve(L, T, hs))

ZeroJudge 解題筆記：k924. P1. 數字結合 (Combination)

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



ZeroJudge 題目連結：k924. P1. 數字結合 (Combination)

解題想法

先將兩個字串合併，再計算奇數位數和、偶數位數和，如果兩者的差是 11 的倍數印出 Yes，反之印出 No。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = "".join(line.split())  # 兩個整數合併
    odd, even = 0, 0  # 奇數位數和，偶數位數和
    for i, c in enumerate(s):  # 計算奇數位數和、偶數位數和
        if i%2 == 1: odd += int(c)
        else: even += int(c)
    dif = abs(odd - even)
    print("Yes" if dif%11 == 0 else "No")

ZeroJudge 解題筆記：k866. 8.運送隕石 (Delivery)

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



ZeroJudge 題目連結：k866. 8.運送隕石 (Delivery)

解題想法

我用 priority queue 儲存隕石重量，每次處理最重的隕石，將重量除以 2 之後再放回 priority queue 之中，處理 m 次之後，priority queue 最上面的資料就是答案。

Python 程式碼

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

import sys, math, heapq

for line in sys.stdin:
    n, m = map(int, line.split())  # n 顆隕石，m 顆炸彈
    ws = []  # 每顆隕石的重量，為了將最大值放上面，要加負號
    for w in map(int, input().split()): heapq.heappush(ws, -w)
    for _ in range(m):  # 執行 m 次
        w = -heapq.heappop(ws)  # 取出最大值
        h = w/2  # 除以2
        heapq.heappush(ws, -h)  # 加入兩個 -h
        heapq.heappush(ws, -h)
    print(math.ceil(-ws[0]))

ZeroJudge 解題筆記：k865. 7.幼稚園 (Kindergarten)

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



ZeroJudge 題目連結：k865. 7.幼稚園 (Kindergarten)

解題想法

我是用兩層的 for 迴圈，先讀取第 i 個人的身高 h，裡面再用兩個 for 迴圈，分別向左、向右找較高的人，取向左、向右交換次數較少者。這樣的寫法效率不夠高，Python 過不了，C++ 可以通過測試。

Python 程式碼

速度太慢，只能通過 40% 的測資，需要再找到更有效率的寫法。

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    hs = list(map(int, input().split()))  # 身高
    ans = 0  # 交換次數
    for i, h in enumerate(hs):  # 讀取第 i 個人的身高 h
        toleft = 0  # 向左找較高的人數
        for j in range(i-1, -1, -1):
            if hs[j] > h: toleft += 1
        toright = 0  # 向右找較高的人數
        for j in range(i+1, n):
            if hs[j] > h: toright += 1
        if toleft <= toright: ans += toleft  # 取向左、向右交換次數較少者
        else: ans += toright
    print(ans)

ZeroJudge 解題筆記：k854. P8.簡易數織 (Nonogram)

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



ZeroJudge 題目連結：k854. P8.簡易數織 (Nonogram)

解題想法

這題我試著用 dp 計算可能的組合，但是最後一筆測資極大，用 Python 最後一筆測資超時。後來我把題目丢到 Gemini 2.0 Flash，它提供了一個數學化的解法，才能在時限內順利解出來。

Python 程式碼

最後一筆測資超時。

import sys

def solve(w, n, arr):
    mod = 10**9 + 7  # 要取餘數用的整數
    imin = sum(arr) + n - 1  # 黑色區塊總和 + 至少需要的空格數量
    if imin > w:  # 需要的格子數大於 w
        print(0); return  # 印出 0，跳出函式
    dp = [[0]*(n+1) for _ in range(w+1)]  # dp[i][j] 填到第 i 格時放入第 j 段黑色區塊
    for i in range(w+1): dp[i][0] = 1  # 初始化，填滿 0 ~ w 格、沒有黑色區塊，只有一種方式
    for i in range(1, w+1):  # 填滿 1 ~ w 格
        for j in range(1, n+1):  # 放入第 j 段黑色區塊
            block = arr[j-1]  # 黑色區塊長度
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod  # 不放這個黑色區塊
            if i >= block:  # 可以放入這個黑色區塊
                if j == 1:  # 第 1 個黑色區塊，前面可以不需要是空格
                    dp[i][j] = (dp[i][j] + dp[i-block][j-1]) % mod
                elif i >= block+1:  # 不是第 1 個黑色區塊，前面必須是空格
                    dp[i][j] = (dp[i][j] + dp[i-block-1][j-1]) % mod
    print(dp[w][n]); return

for line in sys.stdin:
    w, n = map(int, line.split())  # w 個格子，n 段連續的黑色區塊
    arr = list(map(int, input().split()))  # 各段連續黑色區塊的長度
    solve(w, n, arr)

ZeroJudge 解題筆記：l919. P.2 珠寶交易 (Jewel)

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



ZeroJudge 題目連結：l919. P.2 珠寶交易 (Jewel)

解題想法

這題理論上用貪心法就能解，有通過範例測資，但是無法送出解答。

Python 程式碼

無法送出解答。

import sys

for line in sys.stdin:
    n = int(line)  # n 天
    buy = float('inf')  # 最低買價，預設為正無窮大
    profit = 0  # 最大利潤，預設為 0
    best_buy_dat, best_sell_day = 0, 0  # 最佳買入、𧶠出時機
    buy_day = 0  # 買入時機
    for i, p in enumerate(map(int, input().split()), start=1):  # 第 i 天，價格 p
        if p < buy:  # 如果當天的價格小於 buy，更新 buy 及 buy_day
            buy = p; buy_day = i
        elif p - buy > profit:  # 價差大於 profit
            profit = p - buy  # 更新 profit
            best_sell_day = i  # 更新 sell_day
            best_buy_day = buy_day  # 更新 best_buy_day
    if profit > 0: print(best_buy_day, best_sell_day)
    else: print(-1)

ZeroJudge 解題筆記：k853. P7.直播趕場 (Live)

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



ZeroJudge 題目連結：k853. P7.直播趕場 (Live)

解題想法

採用類似〈APCS實作題2016年3月第3題：線段覆蓋長度〉計算重疊線段厚度的寫法，讀到開始直播時刻厚度加 1，讀到直播結束時刻厚度減 1；假設目前檢查的時間端點為 [start, end+1]，若厚度小於等於螢幕數量，可以觀看的時數加上厚度乘以端點距離，若厚度大於螢幕數量，可以觀看的時數加上螢幕數量乘以端點距離。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, s = map(int, line.split())  # n 個螢幕，s 個直播
    cast = []  # 直播開始、結束時刻，開始厚度加 1，結束厚度減 1
    for _ in range(s):  # 讀取 s 行資料
        start, end = map(int, input().split())
        cast += [(start, 1), (end+1, -1)]  # 結束時刻要加 1
    cast.sort()  # 排序
    last = 0  # 正在檢查的範圍開始時刻
    thick = 0  # 厚度，正在直播的頻道數量
    ans = 0  # 答案，可以觀看的直播總時數
    for p, t in cast:  # 依序讀取時刻及厚度變化
        if thick > 0:  # 如果目前直播頻道數量大於 0
            ans += min(thick, n)*(p-last)  # 更新 ans，加上 thick, n 較小值乘以 p-last
        thick += t  # 更新厚度
        last = p  # 更新 last
    print(ans)

ZeroJudge 解題筆記：k851. P5.辨識碼 (Identification)

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



ZeroJudge 題目連結：k851. P5.辨識碼 (Identification)

解題想法

我是用字串分割的方式，按照題目要求的長度分割字串，將每個子字串的數字加總存入集合 isum 之中，如果 isum 之中已經有同樣的值就是國民，不需要再檢查後面的子字串。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)  # 分組數字 x 個
    n = sys.stdin.readline().strip()  # 身分證號
    m = len(n)  # 長度
    isum = set()  # 各組的加總
    flag = False  # 是否為國民，預設為 False
    for i in range(m-x, -1, -x):  # 從最後往前取長度為 x 的子字串
        s = n[i:i+x]  # 子字串
        tot = sum([int(c) for c in s])  # 加總
        if tot in isum:  # 如果 isum 之中已經有 tot
            flag = True; break  # 是國民，中止迴圈
        isum.add(tot)  # tot 加入 isum
    print("Yes" if flag else "No")  # 印出答案

ZeroJudge 解題筆記：k849. P3.骨牌 (Domino)

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



ZeroJudge 題目連結：k849. P3.骨牌 (Domino)

解題想法

這題是有向圖，我用集合 child 儲存子節點編號，用字典 nxt 儲存每個節點的子節點編號，讀取 n 行資料存入 child 及 nxt，再掃瞄一輪找出根節點（第一張牌），最後用一個 while 迴圈第根節點開始掃過所有的節點並將節點編號存入串列 ans。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 組資料，n 張牌
    child = set()  # 不是第一張牌的編號
    nxt = dict()  # 下一張牌的編號
    for _ in range(n):  # 讀取 n 行資料，u 的下一張是 v
        u, v = map(int, input().split())
        child.add(v)
        nxt[u] = v
    start = 0  # 第一張牌
    for u in nxt.keys():  # 從 nxt 的 keys 之中找第一張牌
        if u not in child:  # 只有一個 u 不在 child 之中
            start = u; break  # 找到就可以中止迴圈
    ans = [start]  # 先將 start 加入 ans
    while nxt[ans[-1]] != -1:  # 如果 ans 最後一項的下一張不是 -1 繼續執行
        ans.append(nxt[ans[-1]])  # 將找到的牌加入 ans
    print(*ans)

ZeroJudge 解題筆記：k848. P2.卡牌評分 (Card)

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



ZeroJudge 題目連結：k848. P2.卡牌評分 (Card)

解題想法

分成兩個部分，先掃過全部的卡牌資料並找最大值，再掃一輪計算每張牌的積分。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 張卡牌
    S, A, D, H = [0]*n, [0]*n, [0]*n, [0]*n  # 積分，攻擊力，防禦力，生命力
    amax, dmax, hmax = 0, 0, 0  # 最高攻擊力，最高防禦力，最高生命力
    for i in range(n):  # 讀取 n 張牌的資料並找最大值
        a, d, h = map(int, input().split())
        A[i] = a; amax = max(amax, a)
        D[i] = d; dmax = max(dmax, d)
        H[i] = h; hmax = max(hmax, h)
    for i in range(n):  # 計算每張牌的積分
        if A[i] == amax: S[i] += 1
        if D[i] == dmax: S[i] += 1
        if H[i] == hmax: S[i] += 1
    print(S.index(max(S)) + 1)  # 印出最高積分卡牌編號

ZeroJudge 解題筆記：k847. P1.租車費用 (Rent)

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



ZeroJudge 題目連結：k847. P1.租車費用 (Rent)

解題想法

按照題目的計費規則寫就行了，先算租車天數，分成每租滿 10 天以及未滿 10 天兩個部分計費。

Python 程式碼

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

import sys

month = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = sum(month[m1: m2]) - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)

月份的天數改成前綴和，如果輸入的月份是 $m1, m2$，要算計算 $m2-1$ 到 $m1$ 月份的天數 $psum[m2-1] - psum[m1-1]$。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

import sys

psum = (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = psum[m2-1] - psum[m1-1] - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)