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 dfs(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  # 設定這個面額的數量
            dfs(curr+1, nums, total + coins[curr]*i)  # 遞迴
    ### End of dfs ###
    dfs(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")