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

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] = matrix[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;
}