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()  # 前序走訪

ZeroJudge 解題筆記：d326. 程式設計師的面試問題(二)

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


ZeroJudge 題目連結：d326. 程式設計師的面試問題(二)

解題想法

這題考二進位制補數的觀念，用 C++ 的 bitset 寫起來超快。

Python 程式碼

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

import sys

def negative(num):  # 輸入 10 進位負整數，輸出其補數加 1
    s = bin(num)[3:]  # 轉成 2 進位制字串，刪除開頭的 -0b
    s = s.zfill(32)  # 前面補 0 到 32 位數
    t = ''  # 儲存輸出結果的空字串
    for c in s:  # 從 s 依序讀取字元 c
        if c == '0': t += '1'  # 如果 c 是 0，將 1 加到 t
        else: t += '0'  # 如果 c 是 1，將 0 加到 t
    return int(t, 2)+1  # 將 t 轉回整數、加 1，再回傳

result = []
for line in sys.stdin:
    v, a ,b = map(int, line.split())  # 要計算的整數 v，第 a 位數改成 b
    if v < 0:  # 如果 v 是負數
        vb = f"{negative(v):032b}"  # 呼叫 negative 代入 v 計算結果，再用 format 輸出成 32 位數的 2 進位制整數字串
    else:  # 反之，直接用 format 輸出成 32 位數的 2 進位制整數字串
        vb = f"{v:032b}"
    ans = f"{vb[:31-a]}{b:d}{vb[32-a:]}\n"  # 用切片將第 a 位數換成 b
    result.append(ans)
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d244. 一堆石頭

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


ZeroJudge 題目連結：d244. 一堆石頭

解題想法

這題我是用字典計數，再用另一個集合記錄編號，如果某個編號的石頭有 3 個，將編號從集合中移n除，集合中最後只剩下一個編號，這個編號就是答案。如果是用 Python 解題，可以用 collections 函式庫中的 Counter，這個物件的速度更快。

Python 程式碼

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

from collections import Counter

cnt = Counter(map(int, input().split()))  # 計數器
for k, v in cnt.items():  # 依序由 cnt 讀取 key 與 value
    if v == 2:  # 如果 v 等於 2
        print(k); break  # 印出 k，中止迴圈

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

cnt = dict()  # 計數器
nums = set()  # 數字集合
for v in map(int, input().split()):  # 依序讀取值
    if v not in cnt:  # 如果 v 不在 cnt 之中
        cnt[v] = 1  # cnt[v] 等於 1
        nums.add(v)  # v 加入 nums
    else: cnt[v] += 1  # 如果 v 在 cnt 之中，cnt[v] 加 1
    if cnt[v] == 3: nums.remove(v)  # 如果 cnt[v] 等於 3，從 nums 中移除
print(*nums)  # nums 只剩一個值，就是答案

ZeroJudge 解題筆記：d212. 東東爬階梯

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


ZeroJudge 題目連結：d212. 東東爬階梯

解題想法

先找規律，假設走到第 $i$ 階的走法存在表格 $dp[i]$ 之中。

1. 走到第 0 階、第 1 階，只有一種走法，即 $dp[0] = 1, dp[1] = 1$。
2. 走到第 2 階，可以先走到第 1 階再往上走 1 階，也可以從第 0 階直接往上走 2 階，有 2 種走法，即 $dp[2] = dp[1] + dp[0] = 2$。
3. 走到第 3 階，可以先走到第 2 階再往上走 1 階，也可以先走到第 1 階直接往上走 2 階，有 3 種走法，即 $dp[3] = dp[2] + dp[1] = 3$。
4. 走到第 4 階，可以先走到第 3 階再往上走 1 階，也可以先走到第 2 階直接往上走 2 階，有 5 種走法，即 $dp[4] = dp[3] + dp[2] = 5$。
5. 走到第 $i$ 階，可以先走到第 $i-1$ 階再往上走 1 階，也可以先走到第 $i-2$ 階直接往上走 2 階，即 $dp[i] = dp[i-1] + dp[i-2]$。

看到這裡應該已經發現了，答案就是費氏數列。因為這題有多筆測資，而且題目範圍不大，最多到 99 階，所以先建表算出走到第 0 階至走到第 99 階的走法，讀取一個數量 $n$ 之後再查表找答案，這樣會比較快。

Python 程式碼

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

import sys

dp = [0]*100  # 建表，內容為走到指定階數的走法
dp[0] = dp[1] = 1  # 第 0 階、第 1 階，只有一種走法
for i in range(2, 100): dp[i] = dp[i-1] + dp[i-2]  # 第 2 階開始，走法等於前兩項的和

for n in sys.stdin: print(dp[int(n)])  # 讀取 n 代入 dp 找答案

ZeroJudge 解題筆記：d166. 反轉表

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


ZeroJudge 題目連結：d166. 反轉表

解題想法

實際上有多筆測資，讀取到 EOF 才停止，如果整行只有一個 -1 要 continue 不能 break。 倒著往回讀資料，像是範例中的資料為

2 3 6 4 0 2 2 1 0

共有 9 個數字，代表 1 ~ 9 前面各有幾個數字比自己還大，因為最後一位是 9，前面不可能有比 9 大的數，因此資料中這格一定是 0，先將 9 放到儲存答案的陣列之中。

9

倒數第 2 位代表 8，前面有 1 位比 8 大的數字，代表 8 放在 9 後面，因此陣列為

9 8

倒數第 3 位代表 7，前面有 2 位比 7 大的數字，代表 7 放在最後面，因此陣列為

9 8 7

倒數第 4 位代表 6，前面有 2 位比 6 大的數字，代表 6 放在 7、8 之間，因此陣列為

9 8 6 7

倒數第 5 位代表 5，前面沒有比 5 大的數字，代表 5 放最前面，因此陣列為

5 9 8 6 7

我們可以看出，位數對應的值代表這個位數要插入陣列中的索引值，依照這個方式寫程式碼即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    rev = tuple(map(int, line.split()))  # 反轉表
    n = len(rev)  # n 個數字
    if n == 1 and rev[0] == -1: continue  # 如果整行只有 -1，讀下一筆
    arr = []  # 輸出答案用的串列
    for i in range(n, 0, -1):  # 倒著讀反轉表
        arr.insert(rev[i-1], i)  # 依照反轉表的值將位數插入 arr 之中
    print(*arr)  # 印出 arr

ZeroJudge 解題筆記：d119. 有獎徵答：換零錢

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


ZeroJudge 題目連結：d119. 有獎徵答：換零錢

解題想法

這題考動態規畫，使用的硬幣及鈔票面額有 (1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000)，先計算總金額為 0 ~ 50000 元所有的硬幣及鈔票面額組合數，再依照讀到的測資總金額查表、輸出答案。

Python 程式碼

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

dp = [0]*(50001)  # 0 ~ 50000 各種金額組合數
dp[0] = 1  # 沒有用任何硬幣，1 種組合數
coins = (1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000)  # 可用的面額，要由小到大排序

for coin in coins:  # 依序讀取各種面額
    for j in range(coin, 50001):  # 依序更新 dp[coin] ~ dp[50000]
        dp[j] += dp[j - coin]  # dp[j] 的方法數要加上 dp[j - coin]

while True:
    arr = list(map(int, input().split()))  # 讀取一行資料
    if len(arr) == 1 and arr[0] == 0: break  # 如果 arr 長度為 1 而且等於 0，中止迴圈
    print(dp[sum(arr)] - 1)  # 查表找答案，要扣掉題目給的 1 種組合

ZeroJudge 解題筆記：d115. 數字包牌

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


ZeroJudge 題目連結：d115. 數字包牌

解題想法

這題通常是用自訂函式及遞迴，窮舉所有的組合。如果用 Python 解題，可以使用迭代器 itertools.combinations。這題的測資不太，看起來兩者效率差不多。

Python 程式碼

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

def solve(idx, arr, maxdepth, choose):
    if len(choose) + len(arr) - idx < maxdepth:  # 如果剩下的數字不夠用，跳出函式
        return
    if len(choose) == maxdepth:  # 如果 choose 長度等於 maxdepth，印出 choose
        print(*choose); return
    for i in range(idx, len(arr)):  # 依序讀取 arr[idx] ~ arr[-1]
        choose.append(arr[i])  # arr[i] 加入 choose
        solve(i+1, arr, maxdepth, choose)  # 遞迴，idx 改成 i+1
        choose.pop()  # 移除 choose 最後一筆資料

while True:  # 無窮迴圈
    line = list(map(int, input().split()))  # 讀取一行資料
    if len(line) == 1 and line[0] == 0: break  # 如果只有一個 0，中止迴圈
    n, m = line[0], line[-1]  # n 個數取 m 個
    arr = sorted(line[1:-1])  # 可用的數字
    solve(0, arr, m, [])  # 呼叫 solve 解題
    print("")  # 最後要換行

ZeroJudge 解題筆記：c669. missing and duplicate

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


ZeroJudge 題目連結：c669. missing and duplicate

解題想法

先讀取數列，將數列由小到大排序，取最小值 $imin$、最大值 $imax$、項數 $n$，等差數列加總理論值 $$ theory = \frac{(imin + imax) \times n}{2} $$ 如果實際上的數列加總為 $isum$，兩者相減 $$ diff = theory - isum = 缺少的項 - 重複的項 $$ 再用 set 刪除數列中重複的項，計算 set 的加總 $sum(uni)$，重複的項 $$ dup = isum - sum(uni) $$ 最後可以得到缺少的項 $$ mis = diff + dup $$

Python 程式碼

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

T = int(input())
for _ in range(T):
    arr = sorted(list(map(int, input().split())))  # 排序後的數列
    imin, imax, n = arr[0], arr[-1], len(arr)  # 最小值、最大值、數量
    isum = sum(arr)  # arr 的加總
    theory = (imin + imax) * n // 2  # 理論上的等差數量加總
    diff = theory - isum  # arr 加總與理論值的差
    uni = set(arr)  # 刪除重複的數字
    dup = isum - sum(uni)  # 重複的數字
    mis = dup + diff  # 遺失的數字
    print(mis, dup)

ZeroJudge 解題筆記：c665. 進制轉換

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


ZeroJudge 題目連結：c665. 進制轉換

解題想法

先建立兩個對照表，table 是串列格式，用來找出 0 ~ 35 對應的字元；val 是字典格式，用來找出 0 ~ 35 字元對應的數值。用自訂函式 convert，將 a 進位制的字串 s 先轉換成 10 進位制的整數 d，再將 d 轉換成 b 進位制的字串 t。

Python 程式碼

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

import sys

# 0 ~ 35 對應的字元表格
table = [str(i) for i in range(10)]
for i in range(26): table.append(chr(i+ord('A')))

# 0 ~ 35 字元對應的數值
val = dict()
for i in range(10): val[str(i)] = i
for i in range(26): val[chr(i+ord('A'))] = i+10

# 主要的解題過程，a 進位制字串 s，轉成 b 進位制
def convert(s, a, b):
    d = 0  # 10 進位制的數字
    base = 1  # a 進位制基底
    for c in s[::-1]:  # 依序讀取 s[-1] ~ s[0]
        d += val[c]*base  # 更新 d
        base *= a  # 更新 base
    t = ""  # 儲存轉換後結果的空字串
    while d:  # 如果 d 大於 0 繼續執行
        t = table[d%b] + t  # d%b 代入 table 找出對應的字元
        d //= b  # 更新 d
    return t  # 回傳 t

for line in sys.stdin:
    n, b1, b2 = line.split()
    b1 = int(b1); b2 = int(b2)
    print(convert(n, b1, b2))

ZeroJudge 解題筆記：c658. 小新的提款卡密碼

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


ZeroJudge 題目連結：c658. 小新的提款卡密碼

解題想法

先列出 1 ~ $10^{10}$ 之間的完全平方數 sq，將 sq 之中數字 0 ~ 9 的數量組成字串 dig，用字典儲存資料，以 dig 作為 key，以 sq 作為 value。讀取測資時，直接從表格中找出對應的答案，如果不在表格之中則印出 0。

Python 程式碼

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

import sys

def digits(num):  # 計算整數 0 ~ 9 的數量
    cnt = [0]*10  # 計數器
    for c in num: cnt[int(c)] += 1  # 從 nu 依序讀取字元 c 計算數量
    return "".join([str(i) for i in cnt])  # 取出 cnt 的資料組成字串再回傳

table = dict()  # 各種 0 ~ 9 出現數量對應的完全平方數
for i in range(1, 100000):  # 題目最大到 1E10，表格只要算 1 ~ 100000-1
    sq = i*i  # i 平方
    dig = digits(str(sq))  # 轉成 0 ~ 9 的數量字串
    if dig not in table: table[dig] = [sq]  # 如果 dig 不在 table 之中，新增 [sq]
    else: table[dig].append(sq)  # 反之，串列加入 sq

for line in sys.stdin:  # 讀取字串直到 EOF 為止
    dig = digits(line.strip())  # 計算 0 ~ 9 的數量
    if dig not in table: print(0)  # 如果 dig 不在 table 之中印出 0
    else: print(*table[dig])  # 反之印出 table[dig]

ZeroJudge 解題筆記：c657. 最長連續字母

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


ZeroJudge 題目連結：c657. 最長連續字母

解題想法

依序讀取字串內容，如果這一個字母與前一個字母相同，連續相同字母長度加1；反之，更新最大值，重設連續相同字母長度為1。讀取完最後一個字母之後， 要再更新一次最大值。

Python 程式碼

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

import sys

for line in sys.stdin:
    line = line.strip()  # 讀取一行字串
    imax, cnt = 0, 1  # 最長連續字母長度，目前的連續字母長度
    ans = last = line[0]  # 答案對應的字母，目前的字母，預設為 line[0]
    for c in line[1:]:  # 依序讀取 line[1] ~ line[-1]
        if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
        else:  # 如果 c 不等於 last
            if cnt > imax:  # 如果 cnt 大於 imax
                imax = cnt; ans = last  # 更新 imax, ans
            cnt = 1; last = c  # 重設 cnt, last
    if cnt > imax:  # 最後要再檢查一次
        imax = cnt; ans = last
    print(ans, imax)  # 印出答案

ZeroJudge 解題筆記：c560. SF 愛運動

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


ZeroJudge 題目連結：c560. SF 愛運動

解題想法

用動態規畫解題，假設 $dp[i]$ 代表走到第 $i$ 階的方法數，走到第 1 階、1 種方法；走到第 2 階、1 種方法；走到第 3 階、2 種方法；走到第 4 階以上、$dp[i] = dp[i-1] + dp[i-3]$。

Python 程式碼

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

n, m = map(int, input().split())
ss = list(map(int, input().split()))
MOD = 1000000007
dp = [0]*(n+1)
dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2
for i in range(4, n+1): dp[i] = (dp[i-1] + dp[i-3]) % MOD
now, ans = 0, 1
for s in ss:
    ans = (ans * dp[s-now]) % MOD
    now = s

ans = (ans * dp[n-now]) % MOD
print(ans)

ZeroJudge 解題筆記：c440. Bert Love QQ !

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


ZeroJudge 題目連結：c440. Bert Love QQ !

解題想法

由左向右依序讀取字元，目前讀到的 Q 總數為 tq，左側的 Q 加權後數量為 lq。讀到 Q 時答案 ans 加上 lq，並將 tq 加 1；讀到 A 時將 lq 加上 tq，相當於讀到第2個A時，第1個A左側的Q有效數量為2倍。

Python 程式碼

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

s = input()  # 要測試的字串
n = len(s)  # 字串長度
ans, lq, tq = 0, 0, 0  # 答案ans，左側Q的數量lq，Q的總數tq 
for c in s:  # 依序取出字元
    if c == 'Q':  # 如果讀到 Q
        ans += lq  # ans 加上 lq
        tq += 1  # tq 加 1
    elif c == 'A':  # 如果讀到 A
        lq += tq  # lq 加上 tq
# end of for loop
print(ans)  # 印出答案

ZeroJudge 解題筆記：c435. MAX ! MAX ! MAX !

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


ZeroJudge 題目連結：c435. MAX ! MAX ! MAX !

解題想法

假設陣列 d 共有 n 項，用變數 small 記錄目前的最小值，變數 large 記錄目前的最大值，兩者預設值皆為 d[0]。由左向右掃過 d[1] ~ d[n-1]，如果 d[i] 小於 small，找到新的最小值，可能有新的答案；如果 d[i] 大於 large，重設 small 及 large。

Python 程式碼

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

n = int(input())  # 數量 n
d = list(map(int, input().split()))  # 要檢測的資料 d
small = large = d[0]  # 目前的最小值 small、最大值 large，先預設為 d[0]
ans = tmp = 0  # 答案 ans，暫存差距用的 tmp，先預設為 0
for i in range(1, n):  # 依序檢測 d[1] ~ d[n-1]
    if d[i] < small:  # 如果 d[i] 小於 small
        small = d[i]  # 更新 small 為 d[i]
        ans = max(large - small, tmp)  # ans 更新為 large - small 及 tmp 較大者
    elif d[i] > large:  # 如果 d[i] 大於 large
        tmp = ans  # 先將 ans 暫存到 tmp
        small = large = d[i]  # 更新 small、large 為 d[i]
# end of for loop
print(ans)  # 印出答案

ZeroJudge 解題筆記：c364. 我鄙視你

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


ZeroJudge 題目連結：c364. 我鄙視你

解題想法

從每個人開始，向左、向右各找一次遞減序列。

Python 程式碼

從第9筆測資開始超過記憶體上限。

n = int(input())  # 人數
hs = [1000000001] + list(map(int, input().split())) + [1000000001]  # 身高，兩端加上很大的值
pre = [0]*(n+2)  # 前綴和
st = [0]  # 左側較高的人編號，先放入0
ans = [0]*(n+2)  # 每個人對應的答案，先預設為0
for i in range(1, n+1):  # 依序掃過第 1 ~ n 個人
    pre[i] = pre[i-1] + hs[i]  # 計算前綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] = pre[i-1] - pre[st[-1]]  # 更新答案為第 i-1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

post = [0]*(n+2)  # 後綴和
st = [n+1]  # 右側較高的人編號，先放入n+1
for i in range(n, 0, -1):  # 依序掃過第 n ~ 1 個人
    post[i] = post[i+1] + hs[i]  # 計算後綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] += post[i+1] - post[st[-1]]  # 更新答案為第 i+1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

for i in range(1, n+1): print(ans[i])  # 印出答案

ZeroJudge 解題筆記：c356. Justin 愛加密

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


ZeroJudge 題目連結：c356. Justin 愛加密

解題想法

這題記憶體只有 16 MB，據說 Python 至少要用 32MB，如果記憶體太少一定會遇到 RE: code 127。要用 cstdio 函式庫中的 fgets，每次讀取指定長度的字元，這樣才能過關。

Python 程式碼

超過記憶體上限。

n = int(input())
s = input()
m = len(s)
d = -1
w = m//n
for i in range(0, m, n):
    d = (d+1)%w
    print(s[i+d], end="")
print()

ZeroJudge 解題筆記：c317. 硬幣問題！前傳

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


ZeroJudge 題目連結：c317. 硬幣問題！前傳

解題想法

原則上盡量用面額最大的硬幣，這樣使用的硬幣總數會越少。

Python 程式碼

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

n = int(input())
for _ in range(n):
    x, a, b = map(int, input().split())
    na = x//a  # 硬幣 a 的數量
    x %= a  # x 剩下的數值
    nb = x//b  # 硬幣 b 的數量
    if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
        print(na+nb)  # 找到答案，印出 na+nb
    else:  # 否則要測試將硬幣 a 換回來的狀況
        while na > 0:  # 如果還有硬幣 a
            na -= 1  # na 減 1
            x += a  # x 加 a
            if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
                nb = x//b  # 找到硬幣 b 正確的數量
                break  # 中止 while 迴圈
        # 如果 x 可以被 b 整除印出 na+nb，否則印出 -1
        print(na+nb if x%b == 0 else "-1")

ZeroJudge 解題筆記：c315. I, ROBOT 前傳

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


ZeroJudge 題目連結：c315. I, ROBOT 前傳

解題想法

依序讀取測資並更新位置即可。

Python 程式碼

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

n = int(input())
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
x, y = 0, 0
for _ in range(n):
    a, b = map(int, input().split())
    x += dirs[a][0]*b
    y += dirs[a][1]*b
print(f"{x:d} {y:d}")

C++ 程式碼

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int x = 0, y = 0;
    for(int i=0; i<n; i++) {
        int a, b; cin >> a >> b;
        x += dirs[a][0]*b;
        y += dirs[a][1]*b;
    }
    cout << x << " " << y << "\n";
    return 0;
}

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

#include <cstdio>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int x = 0, y = 0;
    for(int i=0; i<n; i++) {
        int a, b; scanf("%d %d", &a, &b);
        x += dirs[a][0]*b;
        y += dirs[a][1]*b;
    }
    printf("%d %d\n", x, y);
    return 0;
}

ZeroJudge 解題筆記：c276. 沒有手機的下課時間

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


ZeroJudge 題目連結：c276. 沒有手機的下課時間

解題想法

其實就是猜數字。先掃過一次，找出位置、數字皆正確的部分，再掃過一次，找出數字對、位置錯的部分。

Python 程式碼

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

ans = input()  # 答案
n = int(input())  # 猜測次數
for _ in range(n):  # 執行 n 次
    guess = input()  # 猜測的數字
    a, b = 0, 0  # 位置數字皆正確的個數 a，只有數字正確的個數 b
    ar, gr = [], []  # ans 及 guess 中檢測完位置及數字後剩下的部分
    for i in range(4):  # 先掃過一次
        if guess[i] == ans[i]:  # 位置數字皆正確
            a += 1  # a 加 1
        else:  # 否則將此位數加入 ar 及 gr
            ar.append(ans[i])
            gr.append(guess[i])
    for g in gr:  # 由 gr 依序取出數字
        if g in ar:  # 如果 ar 之中有 g 
            b += 1  # b 加 1
            ar.pop(ar.index(g))  # 將 ar 之中的 g 移除一個
    print(f"{a:d}A{b:d}B")  # 印出答案

ZeroJudge 解題筆記：c184. 盈虧互補

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


ZeroJudge 題目連結：c184. 盈虧互補

解題想法

先找出 n 包含 1 的因數 fac 及加總 facSum，如果 facSum 等於 n，n 是完全數；如果 facSum 不等於 n，還要再找 facSum 的因數 fac2 及加總 facSum2，如果 facSum2 等於 n，則兩者是友好數。

Python 程式碼

用 set 儲存因數，用 join 組合要輸出的因數加總算式。使用時間約為 39 ms，記憶體約為 3.5 MB，通過測試。

n = int(input())  # 要測試數字 n
fac = {1}  # 儲存 n 的因數，先放入 1
for i in range(2, int(n**0.5)+1):
    if n%i == 0:
        fac.add(i)
        fac.add(n//i)
facSum = sum(fac)  # n 的因數加總
print("+".join(map(str, sorted(fac))) + "=" + f"{facSum:d}")  # 印出 n 的因數及加總
if n == facSum:  # 如果 n 等於 facSum
    print(f"{n:d} is perfect.")  # n 是完全數
elif len(fac) == 1:  # 如果 fac 只有 1
    print("=0")  # 印出 =0
    print(f"{n:d} has no friends.")  # 不可能有友好數
else:  # 其它狀況
    n2 = facSum  # 要檢測 facSum 是否為友好數
    fac2 = {1}  # 儲存 n2 的因數，先放入 1
    for i in range(2, int(n2**0.5)+1):
        if n2%i == 0:
            fac2.add(i)
            fac2.add(n2//i)
    facSum2 = sum(fac2)  # n2 的因數加總
    print("+".join(map(str, sorted(fac2))) + "=" + f"{facSum2:d}")  # 印出 n2 的因數及加總
    if facSum2 == n:  # 如果 facSum2 等於 n，兩者是友好數
        print(f"{n:d} and {n2:d} are friends.")
    else:  # 否則 n 沒有友好數
        print(f"{n:d} has no friends.")

ZeroJudge 解題筆記：b911. 我想跟Kevin借筷子系列4

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


ZeroJudge 題目連結：b911. 我想跟Kevin借筷子系列4

解題想法

先列出幾種可能性

1. n = 0, data = [0], ans = 0
2. n = 1, data = [1], ans = 1
3. n = 2, data = [1, 2] => [0, 1] => [0, 0], ans = 2
4. n = 3, data = [1, 2, 3] => [1, 0, 1] => [0, 0, 0], ans = 2
5. n = 4, data = [1, 2, 3, 4] => [1, 0, 1, 2] => [0, 0, 0, 1] => [0, 0, 0, 0], ans = 3
6. n = 5, data = [1, 2, 3, 4, 5] => [1, 2, 0, 1, 2] => n = 2 的狀況，ans = 1 + 2 = 3
7. n = 6, data = [1, 2, 3, 4, 5, 6] => [1, 2, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
8. n = 7, data = [1, 2, 3, 4, 5, 6, 7] => [1, 2, 3, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
9. n = 8, data = [1, 2, 3, 4, 5, 6, 7, 8] => [1, 2, 3, 0, 1, 2, 3, 4] => n = 4 的狀況，ans = 1 + 3 = 4

找出規律，數量 n 如果可以除以 2 則 ans 加 1，直到 n = 1 時 ans 加 1 或是 n = 2 時 ans 加 2。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)
    ans = 0
    while n >= 1:
        if n == 1:
            ans += 1
            break
        elif n == 2:
            ans += 2
            break
        else:
            ans += 1
            n //= 2
    print(ans)

與上方的寫法邏輯相同，但改用遞迴，使用時間約為 24 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    def solve(x, a=0):
        if x == 1: return 1
        if x == 2: return 2
        return 1 + solve(x//2, a)
    # end of def
    print(solve(n))

ZeroJudge 解題筆記：b897. 10219 - Find the ways !

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


ZeroJudge 題目連結：b897. 10219 - Find the ways !

解題想法

這題就是在計算組合數 $$ C^n_k = \frac{n!}{(n-k)! k!} = \frac{n(n-1)(n-2) \dots (n-k+1)}{k(k-1)(k-2) \dots \times 2 \times 1} $$ 取 $\log_{10}$ $$ \begin{align*} ans &= \log_{10} n + \log_{10} (n-1) + \log_{10} (n-2) + \dots + \log_{10} (n-k+1) \\ & ~~~~- (\log_{10} k + \log_{10} (k-1) + \log_{10} (k-2) + \dots + 0) \end{align*} $$ 最後再無條件進位到整數即為答案。
改用史特靈公式取近似，由其中一個表達式史特靈級數 $$ \ln n! = n \ln n - n + \frac{1}{2} \ln (2 \pi n) + \frac{1}{12n} - \frac{1}{360n^3} + \dots $$ 若忽略高次項並用換底公式換成以10為底的對數 $$ \begin{align*} \frac{\log_{10} n!}{\log_{10} e} &= n \cdot \frac{\log_{10} n}{\log_{10} e} - n + \frac{1}{2} \cdot \frac{\log_{10} (2 \pi n)}{\log_{10} e} \\ \log_{10} n! &= n \log_{10} n - n \log_{10} e + \frac{1}{2} \log_{10} (2 \pi) + \frac{1}{2} \log_{10} n \\ \log_{10} n! &\approx (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \end{align*} $$ 因此 $C^n_k$ 取 $\log_{10}$ $$ \begin{align*} & \\ \log_{10} C^n_k \approx & (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \\ & - [(n-k + 0.5) \log_{10} (n-k) - 0.4343 (n-k) + 0.39909] \\ & - [(k + 0.5) \log_{10} k - 0.4343 k + 0.39909] \end{align*} $$ 但是上式的第二行中有 $\log_{10}(n-k)$，當 $n=k$ 時會出問題，程式碼之中需要排除這個特例。

Python 程式碼

理論上用 math 函式庫中的 comb 可以很方便地計算組合數，但是這個函式在 Python 3.8 才加入，ZeroJudge 網站的 Python 版本為 3.6.9，不能用。

from math import comb, log10, ceil
import sys

for line in sys.stdin:
    n, k = map(int, line.split())
    print(ceil(log10(comb(n, k))))

改成不使用 comb，直接取 log10 ，還是會超時。

from math import log10, ceil
import sys

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == k: print("1")
    else:
        ans = 0
        for i in range(n, n-k, -1): ans += log10(i)
        for i in range(k, 1, -1): ans -= log10(i)
        print(ceil(ans))

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

from math import log10, ceil
import sys

def fac(x):
    return (x+0.5)*log10(x) - 0.4343*x + 0.39909

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == k: print("1")
    else: print(ceil(fac(n) - fac(n-k) - fac(k)))

ZeroJudge 解題筆記：b893. 勘根定理

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


ZeroJudge 題目連結：b893. 勘根定理

解題想法

因為 $-2147483647 \leq x^6 \leq 2147483647 ~\Rightarrow -36 \leq x \leq 36$，只要一路由 $-36$ 每次加 1 檢測到 $36$ 即可。 這題的敘述有問題，題目中說無解時輸出 N0THING! >\\<，但實際上是 N0THING! >\\\<。

Python 程式碼

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

def func(x):
    return a*x**5 + b*x**4 + c*x**3 + d*x**2 + e*x + f

a, b, c, d, e, f = map(int, input().split())
if a == b == c == d == e == f == 0:
    print("Too many... = =\"")
else:
    real = False
    for i in range(-36, 36):
        if func(i) == 0:
            print(f"{i:d} {i:d}")
            real = True
        elif func(i)*func(i+1) < 0:
            print(f"{i:d} {i+1:d}")
            real = True
    if not real: print("N0THING! >\\\\\\<")

ZeroJudge 解題筆記：b877. 我是電視迷

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


ZeroJudge 題目連結：b877. 我是電視迷

解題想法

這題可以用 if 判斷頻道號碼是否已經超過上限，從最前面繞回來；也可以取餘數找下一個頻道號碼。

Python 程式碼

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

a, b = map(int, input().split())
if b > a: print(b-a)
else: print(100-a+b)

將第2、3行合併。使用時間約為 17 ms，記憶體約為 3.3 MB，通過測試。

a, b = map(int, input().split())
print(b-a if b > a else 100-a+b)

取餘數，因為 Python 的取餘數若遇到被除數是負值，會先將被除數加上除數之後再取餘數，餘數和除數同號，不需要像 C++ 要在程式碼中自己加上除數量值。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

a, b = map(int, input().split())
print((b-a)%100)

ZeroJudge 解題筆記：b860. 獨角蟲進化計算器

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


ZeroJudge 題目連結：b860. 獨角蟲進化計算器

解題想法

用 while 迴圈不斷更新糖果、獨角蟲、鐵殼蛹的數量，直到獨角蟲的數量歸零為止。

Python 程式碼

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

c, w = map(int, input().split())  # 讀取糖果數量 c，獨角蟲數量 w
k = 0  # 鐵殼蛹數量 k

while w > 0:  # 如果 w 大於 0 繼續執行
    if c >= 12 and w >= 1:  # 如果 c 大於等於 12 而且 w 大於等於 1 才能進化
        c -= 10  # c 減 10，先用掉 12 顆，進化得 1 顆，再將鐵殼蛹送給博士得 1 顆
        w -= 1  # 進化，獨角蟲數量 w 減 1
        k += 1  # 鐵殼蛹數量 k 加 1
    else:  # 否則將獨角蟲送給博士換糖果
        w -= 1
        c += 1
# end of while loop
print(k)  # 印出答案

ZeroJudge 解題筆記：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

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


ZeroJudge 題目連結：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

解題想法

共有 $n$ 片花瓣，第一次拔1片，接下來每次比上一次多拔 $m$ 片，假設共拔 $k$ 次，拔掉的花瓣總數為 $$ t = k + [m + 2m + 3m + \dots + (k-1)m] = k + \frac{(k-1)km}{2} = \frac{1}{2} [m k^2 + (2-m) k] $$ 若要剛好拔完，則 $t = n$，且 $k \in N$ 才能符合條件，因此 $$ mk^2 + (2-m)k - 2n = 0 $$ 若有正整數的根，輸出 "Go Kevin!!"，否則輸出 "No Stop!!"。

Python 程式碼

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

import sys, math

for line in sys.stdin:  # 讀取多行測資直到 EOF 為止
    n, m = map(int, line.split())  # 花瓣數量 n，每次多拔的花瓣數量 m
    if m == 0:  # 如果 m 等於 0 一定有解
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    a, b, c = m, 2-m, -2*n  # 一元二次方程式的係數
    D = b*b - 4*a*c  # 判別式
    if D < 0:  # 判別式小於 0 無實數解
        print("No Stop!!")  # 印出 No Stop!!，繼續檢測下一行
        continue
    x1 = (-b + math.sqrt(D)) / (2*a)  # 較大的根
    x2 = (-b - math.sqrt(D)) / (2*a)  # 較小的根
    if x1 > 0 and int(x1) == math.ceil(x1):  # 如果 x1 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    elif x2 > 0 and int(x2) == math.ceil(x2):  # 如果 x2 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    else: print("No Stop!!")  # 否則印出 No Stop!!

ZeroJudge 解題筆記：b762. 英國聯蒙

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


ZeroJudge 題目連結：b762. 英國聯蒙

解題想法

這題用字典或串列儲存對應的訊息，寫起來會比較簡潔。

Python 程式碼

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

act = {"Get_Kill": 1, "Get_Assist": 2, "Die": 3}  # 輸入的狀態
# 連續擊殺數對應的訊息
kill_mess = ["",
             "You have slain an enemie.",
             "You have slain an enemie.",
             "KILLING SPREE!",
             "RAMPAGE~",
             "UNSTOPPABLE!",
             "DOMINATING!",
             "GUALIKE!",
             "LEGENDARY!"]
# 陣亡時連續擊殺數對應的訊息
die_mess = [ "You have been slained.",
             "SHUTDOWN."]

N = int(input())  # 指令數量
cont = 0  # 連續擊殺數
kill = 0  # 總擊殺數
ast = 0  # 助攻次數
die = 0  # 陣亡次數
for _ in range(N):
    a = act[input().strip()]  # 讀取 N 行指令，要用 strip() 刪除某些測資後方多的 \t 或空白
    if a == 1:  # 如果是 Get_Kill
        cont += 1  # 連續擊殺數加 1
        if cont >= 8: print(kill_mess[8])  # 如果連續擊殺數大於等於 8，印出 kill_mess[8]
        else: print(kill_mess[cont])  # 否則印出 kill_mess[cont]
    elif a == 2: ast += 1  # 如果是 Get_Assist 助攻數加 1
    elif a == 3:  # 如果是 Die
        if cont < 3: print(die_mess[0])  # 如果連續擊殺數小於 3，印出 die_mess[0]
        else: print(die_mess[1])  # 否則印出 die_mess[1]
        die += 1  # 陣亡次數加 1
        kill += cont  # 更新擊殺總數
        cont = 0  # 連續擊殺數歸零
kill += cont  # 最後要再加上一次連續擊殺數
print(f"{kill:d}/{die:d}/{ast:d}")  # 印出答案

ZeroJudge 解題筆記：b759. 我明明就有說過= =

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


ZeroJudge 題目連結：b759. 我明明就有說過= =

解題想法

這題可以只用字串切片或是索引值組合出每次要印出的內容，也可以每次都更新字串的內容，兩種方法的速度都很快。

Python 程式碼

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

X = input()
for i in range(len(X)):
    print(X[i:]+X[:i])

每次印出字串後，重新組合字串。使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

X = input()
for i in range(len(X)):
    print(X)
    X = X[1:] + X[0]

ZeroJudge 解題筆記：b604. Center of Symmetry

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


ZeroJudge 題目連結：b604. Center of Symmetry

解題想法

比較直接的作法，先將所有的點座標 (x, y) 存入集合之中，同時計算所有點座標的平均值 (xc, yc)。接下來從集合中取出一個點，計算對稱點的座標 (xn, yn)，檢查 (xn, yn) 是否在集合之中，如果沒有就可以印出 no 並停止檢查，反之從集合中移除 (xn, yn)，重複這個過程直到集合清空為止。如果集合可以清空，印出 yes。
另一個作法，是將所有的點存入陣列、由小到大排序。因為排在陣列最前面的點，其對稱點一定在陣列的最後面。由陣列兩端向中間檢查，只要頭尾兩個點不對稱，就可以印出 no 並停止檢查。如果可以檢查完整個陣列，印出 yes。

Python 程式碼

寫法1，從集合 points 中取出點，找到對稱點並移除。使用時間約為 0.1 s，記憶體約為 5.8 MB，通過測試。

def solve(n):
    points = set()  # 儲存點 (x, y) 的集合
    xc, yc = 0, 0  # 中心點座標 (xc, yc)
    for _ in range(n):  # 讀取 n 個點
        x, y = map(int, input().split())  # 讀取點座標 (x, y)
        x *= 2; y *= 2  # 為了使 (xc, yc) 皆為整數，先將 (x, y) 乘以 2
        xc += x; yc += y  # 先計算加總
        points.add((x, y))  # 將 (x, y) 加入 points
    ### end of for loop ###
    xc //= n; yc //= n  # 除以 n，取平均
    while points:  # 如果 points 還有資料繼續執行
        x, y = points.pop()  # 從 points 隨機取出一筆資料
        xn, yn = 2*xc - x, 2*yc - y  # 計算對稱點座標 (xn, yn)
        if (xn, yn) not in points:  # 如果 (xn, yn) 不在 points 之中
            return False  # 回傳 False
        points.remove((xn, yn))  # 否則從 points 中移除 (xn, yn)
    ### end of while loop ###
    return True  # 跑到這行代表有解，回傳 True

while True:
    n = int(input())  # 讀取點數 n
    if n == 0: break  # 如果讀到 0 中止迴圈
    print("yes" if solve(n) else "no")

ZeroJudge 解題筆記：b603. 拋物線方程式

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


ZeroJudge 題目連結：b603. 拋物線方程式

解題想法

這題考數學。假設開口向上或向下的抛物線頂點為 $(h, k) = (x_1, y_1)$，其方程式為 $$ y = A(x-h)^2 + k = A(x-x_1)^2 + y_1 $$ 線上另一個點為 $(x_2, y_2)$，將這個點代入上式可得 $$ y_2 = A(x_2 - x_1)^2 + y_1 ~\Rightarrow~ A = \frac{y_2 - y_1}{(x_2 - x_1)^2} $$ 另外二次曲線的通式為 $$ y = Ax^2 + Bx + C $$ 將上式與第1式比較係數，由 $x$ 項可得 $$ B = -2Ax_1 = -2 \times \frac{y_2 - y_1}{(x_2 - x_1)^2} \times x_1 $$ 由常數項可得 $$ C = Ax_1^2 + y_1 = \frac{y_2 - y_1}{(x_2 - x_1)^2} \times x_1^2 + y_1 $$ 為了將係數化為整數，將每一項同乘以 $x_2 - x_1$，再換成此題要求的型式 $ay = bx^2 + cx + d$，4個係數分別為 $$ \begin{align*} a &= x_2 - x_1 \\ b &= (x_2 - x_1) A = \frac{y_2 - y_1}{x_2 - x_1} \\ c &= (x_2 - x_1) B = -\frac{2x_1 (y_2 - y_1)}{x_2 - x_1} \\ d &= (x_2 - x_1) C = \frac{x_1^2 (y_2 - y_1)}{x_2 - x_1} + y_1 (x_2 - x_1) \end{align*} $$ 因為 $a$ 必須是正值，最後要再檢查一下係數的正負號。由以上的公式得到的係數可能需要約分。

Python 程式碼

第9行的 math.gcd，我使用的 Python 版本為 3.10.12，可以一次輸入多個參數求最大公因數，但是 ZeroJudge 網站的 Python 版本為 3.6.9，每次只能輸入2個參數。使用時間約為 21 ms，記憶體約為 3.4 MB，通過測試。

from math import gcd

def solve(x1, y1, x2, y2):
    a = x2-x1
    b = (y2-y1)//(x2-x1)
    c = -2*x1*(y2-y1)//(x2-x1)
    d = x1*x1*(y2-y1)//(x2-x1) + y1*(x2-x1)
    if a < 0:
        a, b, c, d = -a, -b, -c, -d
    g = gcd(gcd(gcd(a, b), c), d)
    if g != 1:
        a, b, c, d = a//g, b//g, c//g, d//g
    return a, b, c, d

while True:
    try:
        x1, y1, x2, y2 = map(int, input().split())
        a, b, c, d = solve(x1, y1, x2, y2)
        print(f"{a:d}y = {b:d}x^2 + {c:d}x + {d:d}")
    except EOFError: break

ZeroJudge 解題筆記：b595. Special Touring Car Racing

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


ZeroJudge 題目連結：b595. Special Touring Car Racing

解題想法

依序掃過 i = 1 ~ n 站，先計算從起點直接開到第 i 站的成本，再用另一層 for 迴圈，計算以 j = 1 ~ i-1 站為前一個停靠站到第 i 站的成本，更新第 i 站最低成本及前一個停靠站。最後再從終點往起點找出各停靠站的編號，將編號反向輸出。

Python 程式碼

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

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)  # 讀取 n
    if n == 0: break  # 如果 n 等於 0 中止迴圈
    stop = [0] + list(map(int, sys.stdin.readline().split()))  # 讀取停靠站位置，加入 stop[0] = 0 
    cost = [float('inf')]*(n+1)  # 移動到第 i 站的成本，預設為極大的值
    prev = [0]*(n+1)  # 移動到第 i 站之前停靠的前一站
    for i in range(1, n+1):  # 依序檢查第 1 ~ n 站
        cost[i] = min(cost[i], (200 - stop[i])**2)  # 計算由開頭直接走到第 i 站的成本
        for j in range(1, i):  # 依序檢查由第 1 ~ i-1 站走到第 i 站的成本
            val = cost[j] + (200 - (stop[i] - stop[j]))**2
            if val < cost[i]:  # 如果 val 小於 cost[i] 目前的值
                prev[i] = j; cost[i] = val  # 更新 prev[i] 為 j、 cost[i] 為 val
    ### end of for loop ###
    ans = [n]  # 答案，先加入終點 n
    idx = n  # 由 prev 讀取資料的索引值
    while prev[idx] != 0:  # 如果 prev[idx] 不等於 0 繼續執行
        ans.append(prev[idx])  # 將 prev[idx] 加入 ans
        idx = prev[idx]  # 更新 idx 為 prev[idx]
    print(*([0] + ans[::-1]))  # 反序列印

ZeroJudge 解題筆記：b594. A Marvelous Pet

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


ZeroJudge 題目連結：b594. A Marvelous Pet

解題想法

這題比較直接的想法，是用兩個指針從小到大掃過一次，變數 low 從 1 到 n-2，變數 high 從 2 到 n-1，區間 [low, high] 之間的加總為 isum。每次更新時有三種可能性：

1. 如果 isum = n，答案 ans 加 1，再將整個區間向右平移，isum 減去 low，low 加 1，high 加 1，isum 加上 high。
2. 如果 isum > n，isum 減去 low，再將 low 加 1。
3. 如果 isum < n，high 加 1，再將 isum 加上 high。

這個寫法用 Python 會超時，用 C++ 可以過關。 另一種寫法會利用到等差級數和公式，假設首項為 $a$、項數為 $k$、公差為 $1$，級數和 $$ s = \frac{k[a + a + (k-1)]}{2} = \frac{k(2a+k-1)}{2} $$ 依照題目的要求 $s = n$、$a = 1$，上式的 $k$ 必須有正整數的解，因此 $$ 2n = k^2 + k ~\Rightarrow~ k^2 + k -2n = 0 ~\Rightarrow~ k = \frac{-1 \pm \sqrt{1 + 8n}}{2} $$ 要測試的 $k$ 值上限為 $$ k_{max} = \frac{\sqrt{1 + 8n} - 1}{2} $$ 先寫一個 for 迴圈，依序測試 $2 \leq k \leq k_{max}$，判斷 $k$ 值是否為解的步驟為

1. $mod(2n, k) = 0$
2. $tmp = \frac{2n}{k} - k + 1 > 0$
3. $mod(tmp, 2) = 0$
4. $a = \frac{tmp}{2}, a \leq 1, a+k-1 < n$

Python 程式碼

寫法1，超時。

import sys

def solve(n):
    low, high, isum, ans = 1, 2, 3, 0
    while low < n-1 and high < n:
        if isum == n:
            ans += 1
            isum -= low
            low += 1
            high += 1
            isum += high
        elif isum > n:
            isum -= low
            low += 1
        else:
            high += 1
            isum += high
    return ans

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    ans = solve(n)
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b558. 求數列第 n 項

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


ZeroJudge 題目連結：b558. 求數列第 n 項

解題想法

這題的測資不大，而且遞迴關係也很簡單，可以先用遞迴建表，把 $1 \leq n \leq 500$ 對應的函數值都算出來，再逐行讀取測資、查表、輸出答案。也可以找一般式，先列出前幾項找規律 $$ \begin{align*} f(1) &= 1\\ f(2) &= f(1) + 1\\ f(3) &= f(2) + 2 \\ f(4) &= f(3) + 3 \\ &\vdots \\ f(n) &= f(n-1) + (n-1) \\ \end{align*} $$ 以上的式子相加之後可得 $$ f(n) = 1 + [1 + 2 + 3 + \dots + (n-1)] = 1 + \frac{n(n-1)}{2} $$

Python 程式碼

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

import sys

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

for line in sys.stdin:
    print(table[int(line)])

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

table = [0]*501
table[1] = 1
for i in range(2, 501): table[i] = table[i-1] + i - 1
while True:
    try:
        print(table[int(input())])
    except:
        break

ZeroJudge 解題筆記：b557. 直角三角形

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


ZeroJudge 題目連結：b557. 直角三角形

解題想法

比較直接的作法是用三層迴圈掃過所有的邊長，找出可以組成直角三角形的邊長組合，這個作法在 C++ 很快，在 Python 會超時。另一種作法是先計算所有的邊長平方各有幾個，再由小到大取出邊長平方，如果兩者相加的值有在邊長平方的計數器之中，再用計數器中的數量相乘、計算直角三角形的數量。

Python 程式碼

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

t = int(input())  # t 組測資
for _ in range(t):
    n = int(input())  # n 個邊長
    edges = sorted(list(map(int, input().split())))
    cnt = dict()  # 邊長平方的計數器
    cand = []  # 邊長平方
    for edge in edges:  # 計算各種邊長平方的數量
        x = edge * edge
        if x not in cnt:
            cnt[x] = 1
            cand.append(x)
        else:
            cnt[x] += 1
    m = len(cnt)  # 邊長平方的數量
    ans = 0  # 答案
    for i in range(m-1):  # 依序讀取由小到大的邊長平方
        for j in range(i+1, m):
            a, b = cand[i], cand[j]  # 邊長平方 a, b
            if a+b in cnt:  # 如果 cnt 之中有 a+b 才會更新 ans
                ans += cnt[a+b]* cnt[a] * cnt[b]
    print(ans)

ZeroJudge 解題筆記：b538. 分數運算-2

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


ZeroJudge 題目連結：b538. 分數運算-2

解題想法

這題比b537. 分數運算-1簡單很多，只要按照分數運算的規則，分別寫出加、減、乘、除的計算方式，再用 gcd 將分子、分母約分。輸出時分別三種：0、整除、分數，如果分母是負的，負號要加在分子的前面。

Python 程式碼

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

import sys, math

def fac_cal(a, b, c, d, op):
    num, den = 1, 1  # 計算結果的分子、分母
    if op == "+":  # a/b + c/d = (a*d + c*b) / (b*d)
        num = a*d + c*b 
        den = b*d
    elif op == "-":  # a/b - c/d = (a*d - c*b) / (b*d)
        num = a*d - c*b
        den = b*d
    elif op == "*":  # a/b * c/d = (a*c) / (b*d)
        num = a*c
        den = b*d
    else:  # a/b / c/d = a/b * d/c = (a*d) / (b*c)
        num = a*d
        den = b*c
    if den < 0:  # 如果分母小於 0，將分子、分母的正負號都反過來
       num = -num; den = -den
    g = math.gcd(num, den)  # 取分子、分母最大公因數約分
    num //= g; den //= g
    if num == 0: return "0\n"  # 分子為 0，回傳 0
    elif num%den == 0: return f"{num:d}\n"  # 可以整除，回傳分子
    else: return f"{num:d}/{den:d}\n"  # 不能整除

result = []
lines = sys.stdin.readlines()
for line in lines:
    arr = line.split()
    a, b, c, d = map(int, arr[:4])  # 分割出前 4 個數字
    op = arr[-1]  # 運算符號
    result.append(fac_cal(a, b, c, d, op))
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b512. 高維度稀疏向量

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


ZeroJudge 題目連結：b512. 高維度稀疏向量

解題想法

這題的維度不連續而且範圍很大，用字典儲存維度及對應的值比較方便，如果用陣列儲存值會有很多浪費掉、沒有儲存資料的空間。

Python 程式碼

先儲存兩個向量的資料，再計算相乘的結果。使用時間約為 43 ms，記憶體約為 6.1 MB，通過測試。

A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    B[k] = v
ans = 0
for k, v in A.items():
    ans += v * B.get(k, 0)
    if a in B: ans += n*B[a]  # 也可以這樣寫
print(ans)

只儲存第一個向量的資料，讀取第二個向量資料同時計算相乘的結果。使用時間約為 45 ms，記憶體約為 4.5 MB，通過測試。

A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
ans = 0
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    ans += v*A.get(k, 0)
print(ans)

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!")