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

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;
}

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

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


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

解題想法

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

Python 程式碼

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

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


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

解題想法

要檢查 4 個部分：

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

import math

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

最後一筆測資超時。

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

C++ 程式碼

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

#include <cstdio>
using namespace std;

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

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

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

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