ZeroJudge 解題筆記：f935. 消失的二十年 - 續

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


ZeroJudge 題目連結：f935. 消失的二十年 - 續

解題想法

最低價 min_price 預設為第 0 天的價格，最大獲利 max_proift 預設為 0。依序讀取第 1 天到最後一天的價格 price，如果當天賣出的獲利大於目前的 max_profit，更新 max_profit、最低買價 buy、最高賣價 sell； 如果 price 小於 min_price，更新 min_price。最後如果找不到低於 min_price 的𧶠價，max_profit 等於 0，輸出 0 -1 -1； 反之，輸出 max_profit buy sell。

Python 程式碼

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

prices = list(map(int, input().split()))  # 每天的價格
min_price = prices[0]  # 最低價格，預設為第 0 天的價格
max_profit = 0  # 最大獲利，預設為 0
buy = sell = -1  # 最大獲利對應的最低買價、最高賣價，預設為 -1
for price in prices[1:]:  # 依序讀取讀取第 1 天到最後一天的價格
    if price - min_price > max_profit:  # 更高的獲利
        max_profit = price - min_price  # 更新最大獲利
        buy = min_price  # 更新最低買價
        sell = price  # 更新最高賣價
    elif price < min_price:  # 更低的價格
        min_price = price  # 更新最低價格
if max_profit == 0: print("0 -1 -1")
else: print(f"{max_profit:d} {buy:d} {sell:d}")

ZeroJudge 解題筆記：f929. 程式老師的作業

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


ZeroJudge 題目連結：f929. 程式老師的作業

解題想法

這題如果直接用 index 或是 find 找陣列中第一個 0 的索引值，速度會太慢，無法通過最後一筆測資。用一個最小優先佇列儲存陣列中所有 0 的索引值，如果需要將第一個 0 改成指定的值時，從最小優先佇列取出開頭的資料就能找到要修改的索引值，速度快很多。

Python 程式碼

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

import sys, heapq

n = int(sys.stdin.readline())  # 陣列長度
arr = list(map(int, sys.stdin.readline().split()))  # 陣列內容
pq = [i for i, a in enumerate(arr) if a == 0]  # 所有 0 的索引值
m = int(sys.stdin.readline())  # m 次操作
lines = sys.stdin.readlines()  # 讀取所有剩下的資料
ans = []  # 答案
for line in lines:  # 依序讀取事先存在 lines 的資料
    cmd = list(map(int, line.split()))  # 指令
    if cmd[0] == 1:  # 如果指令開頭是 1
        if pq:  # 如果 pq 有資料
            idx = heapq.heappop(pq)  # 取出 pq 開頭的資料
            arr[idx] = cmd[1]  # 修改 arr[idx]
    elif cmd[0] == 2 and arr[cmd[1]] != 0:  # 如果指令開頭是 2 而且指定的位置不是 0
        arr[cmd[1]] = 0  # 將指定的位置改成 0
        heapq.heappush(pq, cmd[1])  # 將這個位置加入 pq
    elif cmd[0] == 3:  # 如果指令開頭是 3
        if pq: ans.append(str(pq[0]) + "\n")  # 如果 pq 有資料，將 pq 開頭的資料轉成字串加上 \n 存入 ans 
        else: ans.append("-1\n")  # 反之，將 -1\n 存入 ans
sys.stdout.write("".join(ans))  # 將 ans 的資料接成很長的字串再輸出

ZeroJudge 解題筆記：f928. 連環炸彈.................Boom！

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


ZeroJudge 題目連結：f928. 連環炸彈.................Boom！

解題想法

這題的標籤是「遞迴」，不過我是用 BFS 解題。先讀取這格的炸彈種類 k，如果 k 等於 1 只會炸掉自己，如果 k 等於 2 再檢查左右兩格，如果 k 等於 3 則檢查左、右兩側距離 k 及 2k 的格子。檢查過的格子如果有炸彈，將炸彈加入待走訪佇列 que，再將檢查過的格子改成 0。

Python 程式碼

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

from collections import deque

n = int(input())
bombs = list(map(int, input().split()))
que = deque([int(input())])
while que:
    x = que.popleft()
    k = bombs[x]  # 暫存這格的值
    bombs[x] = 0  # 將這格歸零
    if k == 2:  # 如果 k 等於 2，檢查左、右兩格是否出界、是否有炸彈
        if x-1 >= 0 and bombs[x-1] != 0: que.append(x-1)
        if x+1 < n and bombs[x+1] != 0: que.append(x+1)
    elif k >= 3:  # 如果 k 大於等於 3，檢查左、右四格是否出界、是否有炸彈
        if x-k >= 0 and bombs[x-k] != 0: que.append(x-k)
        if x-k-k >= 0 and bombs[x-k-k] != 0: que.append(x-k-k)
        if x+k < n and bombs[x+k] != 0: que.append(x+k)
        if x+k+k < n and bombs[x+k+k] != 0: que.append(x+k+k)
print(*bombs)

ZeroJudge 解題筆記：f885. 加總

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


ZeroJudge 題目連結：f885. 加總

解題想法

這題考數學，要先推導公式。首先用等差級數公式 $$ \frac{(n+a)(n-a+1)}{2} \geq x ~\Rightarrow~ n^2 + n - a^2 + a - 2x \geq 0 $$ 用公式解 $$ n = \frac{-1 \pm \sqrt{1^2 - 4 \times (-a^2 + a - 2x)}}{2} = \frac{-1 \pm \sqrt{4a^2 - 4a + 8x + 1}}{2} $$ 從範例測資來看，答案應該是正整數，因此上式的解要取正值，如果計算結果不是正整數，則用 math.ceil 向上取最接近的正整數。

Python 程式碼

這題有卡 I/O，如果每次計算完之後就用 print 印出答案，在最後一筆測資會超時。改用 sys.stdion.readlines() 一次讀取所有測資，再將所有的計算結果全部存進串列之中，最後再用 sys.stdout.write 及 join 合併要輸出的答案，盡量縮短運算時間。使用時間約為 0.3 s，記憶體約為 15.7 MB，通過測試。

import sys, math

lines = sys.stdin.readlines()
t = int(lines[0])
ans = []
for line in lines[1:]:
    a, x = map(int, line.split())
    ans.append(str(math.ceil((-1 + math.sqrt(4*(a**2) - 4*a + 8*x + 1))/2)) + "\n")
sys.stdout.write("".join(ans))

ZeroJudge 解題筆記：f884. 柏恩的奶茶

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


ZeroJudge 題目連結：f884. 柏恩的奶茶

解題想法

這題考數學，要先推導公式。依照題意，給定某個正整數 $n$，要找到另一個正整數 $x$，使 $x(x+1)(x+2)(x+3) + 1 = x$。先化簡算式 $$ x(x+1)(x+2)(x+3) + 1 = x^4 + 6x^3 + 11x^2 + 6x + 1 = (x^2 + 3x + 1)^2 $$ 因此題目可以改為求 $$ (x^2 + 3x + 1)^2 = n $$ 因為題目要求 $n, x \in N$，所以 $n$ 一定是平方數，假設 $x^2 + 3x + 1 \equiv k$，則 $k = \sqrt{n}$。在程式碼之中，可以先檢查

k = math.isqrt(n)  # Python 3.11 之後的寫法，舊版可用 k = int(math.sqrt(n))
if k*k != n:
    print(-1); return

將題目由解一元四次方程化簡為解一元二次方程式 $$ x^2 + 3x + 1 - k = 0 $$ 判別式 $$ D = 3^2 - 4\times(1-k) = 5 + 4k $$ 因為 $x$ 要有正整數解，$D = 5 + 4k$ 為平方數，$\sqrt{D} = \sqrt{5 + 4k}$ 為奇數且大於 3。由公式解可得 $$ x = \frac{-3 + \sqrt{5 + 4k}}{2} = \frac{-3 + \sqrt{5 + 4 \sqrt{n}}}{2} $$ 在程式碼之中，可以先檢查

d = math.isqrt(5+4k)  # Python 3.11 之後的寫法，舊版可用 d = int(math.sqrt(5+4k))
if d*d != k:
    print(-1); return
if (5+4*k)%2 == 0 or 5+4*k <= 3:
    print(-1); return

最後將題目給的 $n$ 值代入公式求解。題目看起來保證測資一定有解，以上三個檢查是否有解的部分可以跳過，直接代公式求解。

Python 程式碼

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

import sys, math

for line in sys.stdin:
    n = int(line)
    x = (-3+int(math.sqrt(5 + 4*int(math.sqrt(n)))))//2
    print(x, x+1, x+2, x+3)

ZeroJudge 解題筆記：f822. 紅林愛下棋

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


ZeroJudge 題目連結：f822. 紅林愛下棋

解題想法

這題分成兩個部分。首先依序掃過每一格，如果這格是 .，用 list 儲存待走訪佇列，假設目前區塊的顏色 color 為 X，用四方位檢查找周圍的格子 (nr, nc)，如果 (nr, nc) 是 B 或 W，設定 color 的值； 如果 color 已經是 B 或 W，但是 (nr, nc) 的顔色與 color 不同，錯誤，無法計算領地大小。找到連通區塊之後，將 que 裡的格子改成 color 的值。第二部分，再用二層 for 迴圈，計算黑、白棋數量。最後按照題目的要求輸出答案。

Python 程式碼

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

def solve():
    grid = [list(input()) + ["#"] for _ in range(9)]  # 地圖，在最右側、最下方加 # 作為哨兵
    grid.append(["#"]*10)
    for i in range(9):  # 依序掃過每一格
        for j in range(9):
            if grid[i][j] == ".":  # 如果此格是 .
                que = [(i, j)]  # 將 (i, j) 加到待走訪佇列 que
                head = 0  # 從 que 讀取資料的索引值
                color = "X"  # 目前區塊的顏色，預設為 X
                ### BFS ###
                while head < len(que):  # 如果 head 還沒有出界繼續執行
                    r, c = que[head]; head += 1  # 從 que 讀取待走訪位置，head 加 1
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                        if grid[nr][nc] == "#": continue  # 如果此格是邊界，找下一格
                        if (color == "B" and grid[nr][nc] == "W") or \  # 區塊顏色 B、此格顏色 W
                           (color == "W" and grid[nr][nc] == "B"):      # 區塊顏色 W、此格顏色 B
                                print("Wrong"); return  # 錯誤，離開函式
                        elif (color == "B" or color == "W") and grid[nr][nc] == ".":  # 區塊為 B 或 W，此格為 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                        elif color == "X":  # 如果區塊還沒有決定顏色
                            if grid[nr][nc] == ".":  # 如果此格是 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                            elif grid[nr][nc] == "B" or grid[nr][nc] == "W":  # 如果此格是 B 或 W
                                color = grid[nr][nc]  # 更新區塊顏色
                ### End of BFS ###
                for r, c in que: grid[r][c] = color  # 將 que 之中的位置填入對應的顏色
    ### 已掃過所有格子，計算黑、白棋數量 ###
    B, W = 0, 0  # 黑、白棋數量
    for i in range(9):
        for j in range(9):
            if grid[i][j] == "B": B += 1
            elif grid[i][j] == "W": W += 1
    ### 印出題目要求的答案 ###
    print("Black wins!!" if B > W else "White wins!!")
    print(f"{B:d}:{W:d}")
    for row in grid[:9]: print("".join(row[:9]))
### 主程式 ###
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：f821. nAnB ( 正常版 )

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


ZeroJudge 題目連結：f821. nAnB ( 正常版 )

解題想法

這題的數字不會重複，寫起來簡單很多。假設數字、位置皆相同的數量為 a，數字相同、位置不同的數量為 b，依序讀取猜測字串中的每個字元，先比較這個字元與答案中同樣位置的字元是否相同，如果相同則 a 加 1；如果前一個條件不成立，再檢查這個數字是否在答案當中，如果有則 b 加 1。

Python 程式碼

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

ans, m = input().split()  # 正確答案，詢問筆數
n = len(ans)  # 答案的字數
for _ in range(int(m)):  # 執行 m 次
    guess = input()  # 猜測的數字
    a, b = 0, 0  # 數字、位置皆正確的數量，數字正確、位置錯誤的數量
    for i, c in enumerate(guess):  # 依序取出 guess 的數字
        if ans[i] == c: a += 1  # 數字、位置皆正確
        elif c in ans: b += 1  # 數字正確、位置錯誤
    print(f"{a:d}A{b:d}B")

ZeroJudge 解題筆記：f803. 質數篩法練習

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


ZeroJudge 題目連結：f803. 質數篩法練習

解題想法

這題可以用埃拉托斯特尼篩法建質數表，再用二分搜尋找指定的質數在表中的索引值。

Python 程式碼

原來測試時，使用時間約為 2.5 s，記憶體約為 323.6 MB，通過測試。但是在2025年10月23日測試時，最後一筆測資超時，好像沒有為 Python 使用者放寬時間限制，仍然為 1 s。

from bisect import bisect_left

n, m = map(int, input().split())
states = [True]*n
states[0] = states[1] = False
for i in range(2, int(n**0.5) + 1):
    if states[i]:
        states[i+i::i] = [False]*len(states[i+i::i])
primes = [i for i, is_prime in enumerate(states) if is_prime]
for _ in range(m):
    print(bisect_left(primes, int(input())) + 1)

改用 sys 加速並修改內層 for 迴圈的寫法仍然超時。

import sys
from bisect import bisect_left

result = []
lines = sys.stdin.readlines()
n, m = map(int, lines[0].split())
sieve = [True]*n
sieve[0] = sieve[1] = False
for i in range(2, int(n**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, n, i):
            sieve[j] = False
primes = [int(i) for i in range(n) if sieve[i]]
idx = 1
while idx < len(lines):
    x = int(lines[idx])
    idx += 1
    pos = bisect_left(primes, x) + 1
    result.append(f"{pos:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：f787. 宇辰的閃電

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


ZeroJudge 題目連結：f787. 宇辰的閃電

解題想法

這題想要考 C 及 C++ 的結構體 (struct)，自訂結構體 Player，用來儲存玩家的姓名、血量、被電時的傷害、下個目標玩家編號、道具清單。由於 Python 的 list 可以儲存不同格式的資料，而且 Python 沒有 struct，所以我直接用 list 儲存玩家資料。

Python 程式碼

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

n, s = map(int, input().split())  # n 位玩家，一開始的目標為 s
players = [[]]  # 玩家資料，開頭放一個空的，資料依序為
                # [名字, 血量, 被電時的傷害, [道具清單], 下個目標玩家編號]
for i in range(1, n+1): # 讀取 1 ~ n 號玩家資料
    line = input().split()
    players.append([line[0], int(line[1]), int(line[2]),
                   line[3:-1], int(line[-1])])
visited = [False]*(1+n)  # 1 ~ n 號玩家是否已被攻擊過
while not visited[s]:  # 如果 s 號玩家還沒有被攻擊過則繼續執行
    visited[s] = True  # s 號玩家已經被攻擊過
    if players[s][2] >= players[s][1]:  # 傷害大於等於血量
        print(f"{players[s][0]:s} dead.")  # 已陣亡
    else:  # 反之
        players[s][1] -= players[s][2]  # 扣血
        for _ in range(players[s][2]):  # 從最後面開始掉道具
            if players[s][3]: players[s][3].pop()
        print(f"{players[s][0]:s} {players[s][1]:d} ", end="")
        print(*players[s][3])
    s = players[s][4]  # 更新目標

因為玩家持有的道具數量等於血量，所以不需要考慮還沒有陣亡但是已經沒有道具的狀況，可以刪掉第15、16行，第18行改成以下這樣。使用時間約為 83 ms，記憶體約為 9.6 MB，通過測試。

print(*players[s][3][:-players[s][2]])

ZeroJudge 解題筆記：f731. 老鼠的直播間

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


ZeroJudge 題目連結：f731. 老鼠的直播間

解題想法

這題與 APCS實作題2016年3月第3題：線段覆蓋長度 解題觀念相同，將所有時段的開始時間 start 與 1 組合成數組，結束時間 end 與 -1 組合成數組，將數組加到串列之中，再依照時間排序。接下來依序讀取時間，更新目前線上的人數及最大值。

Python 程式碼

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

n = int(input())  # n 個時段
segs = []  # 時刻與人數變化，(start, 1) 或 (end, -1)
for _ in range(n):  # 讀取 n 行資料
    start, end = map(int, input().split())
    segs += [(start, 1), (end, -1)]
segs.sort()  # 依照時刻排序
cnt, imax = 0, 0  # 目前的人數，最多人數
for t, c in segs:  # 依序讀取時刻與人數變化
    cnt += c  # 更新人數
    imax = max(imax, cnt)  # 更新 imax
print(imax) 

ZeroJudge 解題筆記：f716. 計算學期成績

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


ZeroJudge 題目連結：f716. 計算學期成績

解題想法

換算的公式為 $$ y = 45 \times \frac{x-a}{b} + 55 $$ 假設原始成績最高分為 $imax$、最低分為 $imin$，換算後成績最高分為 $100$、最低分為 $55$，代入上式可得 $$ 100 = 45 \times \frac{imax-a}{b} + 55 ~~~~~ 55 = 45 \times \frac{imin-a}{b} + 55 $$ 由以上2式可得 $$ b = imax - a ~~~~~ a = imin $$

Python 程式碼

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

scores = tuple(map(int, input().split()))
a = min(scores)
b = max(scores) - a
print(a, b)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 92 kB，通過測試。2025年10月15日重測，使用時間約為 0 ms，記憶體約為 48 kB，通過測試。

#include <cstdio>

int main() {
    int imin = 1E9, imax = 0, score;
    while(scanf("%d", &score) != EOF) {
        if (score < imin) imin = score;
        if (score > imax) imax = score;
    }
    printf("%d %d\n", imin, imax - imin);
    return 0;
}

ZeroJudge 解題筆記：f701. 連接字詞

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


ZeroJudge 題目連結：f701. 連接字詞

解題想法

這題沒有說明要讀取的單字數量，用 C++ 寫起來會比較麻煩，用 getline 搭配 stringstream 及 vector 會比較方便。

Python 程式碼

以前測試時使用時間約為 19 ms，記憶體約為 3.3 MB。ZeroJudge 網站好像在 2025年10月更新過，同樣的程式碼使用時間約為 6 ms，記憶體約為 3 MB。

words = list(input().split())
conjuction = input()
n = len(words)
for i in range(n-1):
    print(f"{words[i]:s} {conjuction:s} ", end="")
print(words[-1])

可以用 join 將 " 連接詞 " 與串列 words 的內容接成一個字串再輸出，使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

words = list(input().split())
conjuction = input()
print(f" {conjuction} ".join(words))

ZeroJudge 解題筆記：f699. 品嘉的茶葉蛋

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


ZeroJudge 題目連結：f699. 品嘉的茶葉蛋

解題想法

標準的 BFS 題目。因為不想檢查是否出界，我在地圖周圍加上 2 作為哨兵。另外開一個陣列儲存步數。

Python 程式碼

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

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m，最右側、最下方加上 2 作為哨兵
grid = [list(map(int, input().split())) + [2] for _ in range(n)]
grid.append([2]*(m+1))  # 最下方加 m+1 個 2
steps = [[0]*m for _ in range(n)]  # 記錄步數用的二維串列
ans = []  # 答案
que = deque([(0, 0)])  # 待走訪佇列
grid[0][0] = 2  # (0, 0) 設定為 2
while que:  # 如果 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
        if grid[nr][nc] == 2: continue  # 如果此格是 2 找下一格
        steps[nr][nc] = steps[r][c] + 1  # (nr, nc) 的步數為 (r, c) 的步數加 1
        if grid[nr][nc] == 1: ans.append(steps[nr][nc])  # 如果此格是 1，將 (nr, nc) 的步數加入 ans
        grid[nr][nc] = 2  # 此格設定為 2
        que.append((nr, nc))  # (nr, nc) 加入 que
if not ans: print("嘉油！")  # 沒有找到茶葉蛋
else:  # 有找到茶葉蛋，印出 ans 的內容
    for a in ans: print(a)

ZeroJudge 解題筆記：f680. 色塊數量

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


ZeroJudge 題目連結：f680. 色塊數量

解題想法

標準的 BFS 題目。

Python 程式碼

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

from collections import deque

n = int(input())  # 地圖 n*n，最右側、最下方加上 0 作為哨兵
grid = [list(map(int, input().split())) + [0] for _ in range(n)]
grid.append([0]*(n+1))
### BFS ###
cnt = 0  # 色塊數量
for i in range(n):  # 依序掃過每一格
    for j in range(n):
        if grid[i][j] == 0: continue  # 如果此格是 0 找下一格
        color = grid[i][j]  # 此格的顏色
        grid[i][j] = 0  # 此格設定為 0
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列
        cnt += 1  # 色塊數量加 1
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭讀取並移除資料
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] != color: continue  # 如果此格顏色不一樣，找下一格
                grid[nr][nc] = 0  # 此格設定為 0
                que.append((nr, nc))  # (nr, nr) 加入待走訪佇列
### End of BFS ###
print(cnt)  # 印出答案

ZeroJudge 解題筆記：f647. 撲克牌

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


ZeroJudge 題目連結：f647. 撲克牌

解題想法

我用串列儲存牌組，先用 for 迴圈産生按照花色、數字排列好的 52 張牌，接下來依照指令用串列切片修改內容。

Python 程式碼

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

deck = [""]*52
suits = ('S', 'H', 'D', 'F')
akqj = {1: 'A', 13: 'K', 12: 'Q', 11: 'J'}
for i in range(4):
    for j in range(1, 14):
        if 2 <= j <= 10: deck[i*13 +j-1] = suits[i] + str(j)
        else: deck[i*13 + j-1] = suits[i] + akqj[j]
n = int(input())
for _ in range(n):
    line = input().split()
    if line[0] == '1':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[a:b+1] + deck[:a] + deck[b+1:]
    elif line[0] == '2':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[:a] + deck[b+1:] + deck[a:b+1]
    elif line[0] == '3':
        k = int(line[1])
        deck = deck[52-k:] + deck[:52-k]
    else:
        k = int(line[1])
        deck = deck[k:] + deck[:k]
print(*deck[:5])

ZeroJudge 解題筆記：f634. 士兵歸來

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


ZeroJudge 題目連結：f634. 士兵歸來

解題想法

我用集合 uni 儲存存活者的姓名、軍種、階級，再用另外兩個陣列 services、ranks 儲存各軍種、階級存活者的數量，用 cnt 儲存存活者總數。讀取 m 行資料之後，再依照題目要求的格式輸出答案。

Python 程式碼

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

n, m = map(int, input().split())  # 共派出 n 人，有 m 行資料
uni = set()  # (姓名 name, 軍種 service, 階級 rank)
services = [0]*4  # 海、陸、空軍存活人數，開頭有用不到的 0
ranks = [0]*4  # 軍官、士官、士兵存活人數，開頭有用不到的 0
cnt = 0  # 存活人數
for _ in range(m):  # 執行 m 次
    data = tuple(input().split())
    if data not in uni:  # 這筆資料組合不在 uni 之中，新的存活者
        uni.add(data)  # data 加入 uni
        cnt += 1  # 存活人數加 1
        services[int(data[1])] += 1  # 對應的軍種人數加 1
        ranks[int(data[2])] += 1  # 對應的階級人數加 1
print(f"navy:{services[1]:d} army:{services[2]:d} air:{services[3]:d}")
print(f"officer:{ranks[1]:d} sergeant:{ranks[2]:d} soldier:{ranks[3]:d}")
print(f"survival rate: {100.0*cnt/n:.1f}%")

ZeroJudge 解題筆記：f632. 渡船頭

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


ZeroJudge 題目連結：f632. 渡船頭

解題想法

先讀取所有的乘客資料，在結束營業之前到的人才加入串列 passenger 之中，接下來依照時間由小到大排序。另外開一個最大優先佇列，儲存目前乘客會給的小費。再用一個 for 迴圈依序産生出發時刻，讀取當時已到站的乘客資料，將乘客會給的小費存入 pq 之中；再從 pq 取出資料加到利潤 profit 之中，直到 pq 沒有資料或是這趟人數到達上限為止。

Python 程式碼

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

import sys, heapq

t1, t2, k, p = map(int, sys.stdin.readline().split())  # 營業時間，間距，每趟人數
passenger = []  # 乘客到站時間、小費
for line in sys.stdin:  # 讀取資料直到 EOF 為止
    if line.strip() == "": continue  # 如果讀到空行，找下一行
    t, m = map(int, line.split())  # 這個乘客的到站時間、小費
    if t <= t2: passenger.append((t, m))  # 在結束營業之前到的人才加入
passenger.sort()  # 依照時間排序
tot, profit, idx, n = 0, 0, 0, len(passenger)  # 總載客人數，總收入，從 passenger 讀資料的索引值，人數
pq = []  # 存入目前乘客小費的優先佇列
for dep in range(t1, t2+1, k):  # 依序産生出發時刻
    while idx < n:  # 如果 idx 還沒有出界繼續執行
        t, m = passenger[idx]  # 到站時間、小費
        if t <= dep: heapq.heappush(pq, -m)  # 如果 t 小於等於發車時刻，m 加負號再加入 pq
        else: break  # 否則中止迴圈
        idx += 1  # idx 加 1
    cnt = 0  # 這趟已載人數
    while pq and cnt < p:  # 如果 pq 還有資料而且還沒有載滿
        profit += -heapq.heappop(pq)  # 從 pq 讀取並移除首項，轉為正值加到 profit
        cnt += 1; tot += 1  # 更新人數
print(tot, profit)  # 印出答案

ZeroJudge 解題筆記：f631. 同學會

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


ZeroJudge 題目連結：f631. 同學會

解題想法

這題要用最大優先佇列儲存每個人目前有的錢，由於 Python 的 heapq 是最小優先佇列，要將每一筆資料都加上負號。

Python 程式碼

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

import sys, heapq

for line in sys.stdin:  # 繼續執行直到 EOF 為止
    if line.strip() == "": continue  # 遇到空行，找下一行
    n, m = map(int, line.split())  # n 個人，m 道菜
    money = list(map(int, sys.stdin.readline().split()))  # 每個人原來的錢
    dishes = list(map(int, sys.stdin.readline().split()))  # 每道菜的價格
    if sum(money) < sum(dishes):  # 所有人帶的錢小於所有菜的總價
        print("Oh My God")  # 印出 Oh My God
        continue  # 讀下一筆資料
    pq = [-m for m in money]  # 將 money 每一筆資料加負號存入 pq
    heapq.heapify(pq)  # pq 轉成最小優先佇列
    imax = -pq[0]  # 初始金額最大值
    for dish in dishes:  # 依序讀取每道菜的價格
        while pq and dish > 0:  # 當 pq 還有資料而且 dish 大於 0 時繼續執行
            m = -heapq.heappop(pq)  # 取出 pq 第一項加負號，變回正值
            if m > dish:  # 如果付完這道菜還有錢
                heapq.heappush(pq, -(m-dish))  # 剩下的錢加負號，存入 pq
                dish = 0  # 待付金額為 0
            elif m == dish: dish = 0  # 如果這個人的錢剛好夠用，待付金額為 0
            else: dish -= m  # 如果這個人的錢不夠，更新待付金額
    print(imax, -pq[0] if pq else 0)  # 印出 imax，如果 pq 有資料印出 -pq[0]，反之印出 0

ZeroJudge 解題筆記：f493. 水窪問題

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


ZeroJudge 題目連結：f493. 水窪問題

解題想法

這類型的題目我習慣用 BFS 解題，已走訪的位置改成題目給的陸地符號 #，不需要另外開一個陣列儲存已走訪的位置，可以節省一些記憶體。

Python 程式碼

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

from collections import deque

n, m = map(int, input().split())  # 地圖 n*m
grid = [list(input() + "#") for _ in range(n)]  # 讀取地圖資料，右側加上 #
grid.append(["#"]*(n+1))  # 最下方加上 n+1 個 #
cnt, imin, imax = 0, float('inf'), 0  # 數量，最小面積、最大面積
### BFS ###
for i in range(n):  # 依序掃過每一格
    for j in range(m):
        if grid[i][j] == "#": continue  # 如果是 #，找下一格
        grid[i][j] = "#"  # 此格改成 #
        cnt += 1  # 數量加 1
        area = 0  # 這個水漥的面積
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列 que
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭取出座標 (r, c)
            area += 1  # 面積加 1
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] == "#": continue  # 如果是 #，找下一格
                grid[nr][nc] = "#"  # 此格改成 #
                que.append((nr, nc))  # (nr, nc) 加入 que
        imin = min(imin, area)  # 更新 imin
        imax = max(imax, area)  # 更新 imax
### 結束 BFS ###
if cnt == 0:  # 如果 cnt 等於 0，印出 0 0 0
    print("0 0 0")
else:  # 反之印出 imax, imin, cnt
    print(imax, imin, cnt)

ZeroJudge 解題筆記：f455. 詠竣的哀鳳12

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


ZeroJudge 題目連結：f455. 詠竣的哀鳳12

解題想法

這題是背包問題，用動態規畫處理，但是用 Python 好像沒辦法通過。

Python 程式碼

只能通過 60% 的測資。

t, n = map(int, input().split())  # 總時數 t，工作數量 n
dp = [0]*(t+1)  # 總時數 0 ~ t 對應的最大收入
work = ""  # 最高時薪的工作名稱
imax = 0.0  # 最高時薪
for _ in range(n):  # 執行 n 次
    s, m, h = input().split()  # 工作名稱，收入，需要的時間
    m = int(m); h = int(h)  # m, h 轉為 int
    mph = 1.0*m/h  # 時薪
    if mph > imax:  # 如果時薪較高，更新 imax, work
        imax = mph; work = s
    if h > t: continue  # 如時需要的時間大於 t，不能接工作，找下一筆
    for i in range(t, h-1, -1):  # 倒著更新 dp[t] ~ dp[h]
        dp[i] = max(dp[i], dp[i-h] + m)  # 如果接這個工作總收入變高則更新 dp[i]
print(dp[-1])  # 最高總收入在 dp[t-1], dp[-1]
print(work)  # 印出最高時薪的工作名稱

ZeroJudge 解題筆記：f418. Word Search Puzzle

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


ZeroJudge 題目連結：f418. Word Search Puzzle

解題想法

這題我用二維陣列儲存英文字謎資料，再依照測資給的 r1, c1 及 r2, c2 判斷要向右、向下或是向右下方找答案。

Python 程式碼

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

h, w, r1, c1, r2, c2 = map(int, input().split())
r1 -= 1; c1 -= 1; r2 -=1; c2 -= 1  # 題目的座標從 1 開始
grid = [list(input()) for _ in range(h)]
if r1 == r2:  # 同一列，向右找
    print("".join(grid[r1][c1:c2+1]))
elif c1 == c2:  # 同一欄，向下找
    print("".join([grid[i][c1] for i in range(r1, r2+1)]))
else:  # 向右下方找
    print("".join([grid[r1+i][c1+i] for i in range(r2-r1+1)]))

ZeroJudge 解題筆記：f410. 芝麻街的郵件投遞

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


ZeroJudge 題目連結：f410. 芝麻街的郵件投遞

解題想法

這題考排序，自訂比較式，先排單、雙號，雙號放前面、單號放後面，雙號門牌再由小到大排序，單號門牌再由大到小排序。

Python 程式碼

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

from functools import cmp_to_key

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

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = cmp_to_key(mycmp))
print(*arr)

ZeroJudge 解題筆記：f408. 迷你蘋菓鎮

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


ZeroJudge 題目連結：f408. 迷你蘋菓鎮

解題想法

將所有的門牌依照絕對值排序，再依序掃過每一個門牌，如果跟相鄰的門牌相乘小於 0 則答案加 1。

Python 程式碼

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

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = lambda x : abs(x))
cnt = 0
for i in range(1, n):
    if arr[i-1] * arr[i] < 0:
        cnt += 1
print(cnt)

ZeroJudge 解題筆記：f376. 芝麻街的團購

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


ZeroJudge 題目連結：f376. 芝麻街的團購

解題想法

這題的測資不大，可以真的計算以每個點為中心的總距離，再找其中的最小值。實際上答案就是取中位數。

Python 程式碼

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

n = int(input())
psum = [0] + list(map(int, input().split()))
psum.sort()
for i in range(1, n+1): psum[i] += psum[i-1]
imin = float('inf')
ans = 0
for i in range(1, n+1):
    dis = (2*i-n-1)*(psum[i] - psum[i-1]) - psum[i-1] + psum[n] - psum[i]
    if dis < imin:
        imin = dis
        ans = psum[i] - psum[i-1]
print(ans)

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

n = int(input())
arr = sorted(list(map(int, input().split())))
print(arr[n//2] if n%2 else arr[n//2 - 1])

ZeroJudge 解題筆記：f348. 完全偶數

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


ZeroJudge 題目連結：f348. 完全偶數

解題想法

我先寫一個函式 check 判斷輸入的整數 n 是否每一位都是偶數；再寫另一個函式 solve，找最接近 n 的完全偶數距離。

Python 程式碼

簡單但較慢的寫法，循序搜尋，使用時間約為 30 ms，記憶體約為 3 MB，通過測試。

def check(n):  # 檢查輸入的整數是否每一位都是偶數
    while n:
        if n%10%2 == 1:
            return False
        n //= 10
    return True

def solve(n):  # 輸入整數，找最接近的完全偶數距離
    if check(n): return 0  # 特例，n 是完全偶數，回傳 0
    lower, upper, cnt = n-1, n+1, 0  # 往下找、往上找、次數
    while True:  # 找到答案為止
        cnt += 1  # 次數加 1
        if check(lower): return cnt  # 如果 lower 是完全偶數，回傳 cnt
        if check(upper): return cnt  # 如果 uper 是完全偶數，回傳 cnt
        lower -= 1; upper += 1  # lower 減 1，upper 加 1
    return -1  # 預設的回傳值，用不到

print(solve(int(input())))

ZeroJudge 解題筆記：f332. 貝瑞的鐵線體積

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


ZeroJudge 題目連結：f332. 貝瑞的鐵線體積

解題想法

如果函數為 $y = f(x)$，將此函數曲線以 $x$ 軸為轉軸旋轉，旋轉體體積為 $$ V = \pi \int_a^b y^2 dx $$

Python 程式碼

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

import math

t = int(input())  # 共 t 筆測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 多項式最高次方
    poly = list(map(int, input().split()))  # 多項式由高到低次方各項係數
    square = [0]*(2*n + 1)  # 多項式平方各項係數
    for i in range(n+1):
        for j in range(n+1):
            square[i+j] += poly[i]*poly[j]
    integral = [0]*(2*n + 1)  # 平方後積分結果，忽略常數項
    for i in range(2*n + 1):  # 計算積分式
        integral[i] = 1.0 * square[i] / (2*n + 1 - i)
    ans = 0.0  # 積分結果
    a, b = map(int, input().split())  # 積分下限、上限
    for i, c in enumerate(integral):  # 代入積分下限、上限
        ans += c * (b**(2*n + 1 - i) - a**(2*n + 1 - i))
    print(f"{math.pi*ans:.2f}")  # 印出答案時再乘以 pi

ZeroJudge 解題筆記：f291. 試算表大小

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


ZeroJudge 題目連結：f291. 試算表大小

解題想法

先將讀到的字串拆成左側字母、右側數字兩個部分，再從字母最後面往回讀取，計算是第幾欄，再將欄數乘以列數就是答案。

Python 程式碼

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

s = input()  # 輸入的儲存格編號
left = ""  # 左半邊的欄位
row = 0  # 列數
for i, c in enumerate(s):  # 依序讀取 s 的字元
    if c.isdigit():  # 如果 c 是數字，取出左半邊，中止迴圈
        left = s[:i]
        row = int(s[i:])
        break
b = 1  # 計算欄位的基底
col = 0  # 欄位編號
for c in left[::-1]:  # 從 left 最後面讀取字元
    col += b*(ord(c) - ord('A') + 1)  # 計算欄位
    b *= 26  # 基底乘以 26
print(row*col)  # 答案是列、欄相乘

ZeroJudge 解題筆記：f260. 愛八卦的同學

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


ZeroJudge 題目連結：f260. 愛八卦的同學

解題想法

我用 BFS 找連通區塊數量，不過用 Python 的速度太慢，用 C++ 解題也要 0.3 s。

Python 程式碼

速度太慢，只能通過一筆測資。

import sys
from collections import deque

for line in sys.stdin:
    n, k = map(int, line.split())  # n 個人，k 組關係
    adj = [[] for _ in range(n)]  # 每個人與其它人的關係
    for _ in range(k):  # 讀取 k 行資料
        u, v = map(int, sys.stdin.readline().split())  # u, v 是朋友
        adj[u].append(v)
        adj[v].append(u)
    cnt = 0  # 小團體數量
    visited = [False]*n  # 是否已經檢查過
    for i in range(n):  # 依序讀取每一個人
        if visited[i]: continue  # 如果 i 已經檢查過，找下一個人
        visited[i] = True  # 設定為 True
        cnt += 1
        que = deque([i])
        while que:
            v = que.popleft()
            for u in adj[v]:
                if visited[u]: continue
                que.append(u)
                visited[u] = True
    print(cnt)

ZeroJudge 解題筆記：f257. 君王的處刑遊戲

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


ZeroJudge 題目連結：f257. 君王的處刑遊戲

解題想法

我是用二維陣列儲存每一個人的驚恐值，預設值為 0，-1 代表已淘汰，Python 的最右側、最下方加上 -1 當作哨兵，C++ 周圍加上 -1 當作哨兵。每次檢查位置 (x, y) 的人，如果還沒有淘汰就設定成 -1，再檢查周圍 8 格，遇到還沒有被淘汰的人就將驚恐值加 1。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 二維陣列 n*n
    grid = [[0]*n + [-1] for _ in range(n)]  # 最右側、最下方加 -1 當作哨兵
    grid.append([-1]*(n+1))
    k = int(sys.stdin.readline())  # 要淘汰的人數
    for _ in range(k):  # 執行 k 次
        x, y = map(int, sys.stdin.readline().split())  # 要淘汰的人位置 (y, x)
        if grid[y][x] == -1: continue  # 已淘汰，找下一個
        grid[y][x] = -1  # 已淘汰，設定成 -1
        # 搜尋四周的 8 格
        for dy, dx in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
            ny, nx = y+dy, x+dx  # 檢查 grid[ny][nx]
            if grid[ny][nx] == -1: continue  # 已淘汰，找下一個
            grid[ny][nx] += 1  # 周圍的人驚恐值加 1
    # 執行完畢，要印出答案，不能印出最右側、最下方的哨兵，-1 要換成 x
    for row in grid[:n]:
        print("".join([str(i) if i != -1 else "x" for i in row[:n]]))

ZeroJudge 解題筆記：f164. 萬球同心移位之章

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


ZeroJudge 題目連結：f164. 萬球同心移位之章

解題想法

這題絕對不要真的用鏈結串列解題，因為要找到鏈結串列中指定的值只能從頭開始依序往下找，一定會超時。用兩個陣列儲存每一個節點的左、右節點編號，移動節點時只要修改對應的節點編號即可。

Python 程式碼

最後一筆測資記憶體爆掉。

n, m, q = map(int, input().split())  # n 顆球，m 次操作，q 次查詢
pre = [(i-1+n)%n for i in range(n)]  # 每顆球的前一顆球
nxt = [(i+1)%n for i in range(n)]  # 每顆球的後一顆球
for _ in range(m):  # 執行 m 次
    d, a, b = input().split()  # 方向 d，a 球移到 b 球旁邊
    if a == b: continue  # 如果 a 等於 b，不移動
    a = int(a); b = int(b)  # 轉成整數
    nxt[pre[a]] = nxt[a]  # a 原來左側的球接到 a 原來右側的球
    pre[nxt[a]] = pre[a]  # a 原來右側的球接到 a 原來左側的球
    if d == 'R':  # 逆向
        le = pre[b]  # 暫存 b 原來左側的球
        nxt[le] = a  # b 原來左側的球接到 a
        pre[b] = a  # b 的左側接到 a
        pre[a] = le  # a 左側接到 le
        nxt[a] = b  # a 右側接到 b
    else:  # 順向
        ri = nxt[b]  # 暫存 b 原來右側的球
        pre[ri] = a  # b 原來右側的球接到 a
        nxt[b] = a  # b 的右側接到 a
        pre[a] = b  # a 的左側接到 b
        nxt[a] = ri  # a 的右側接到 ri
arr = tuple(map(int, input().split()))
for a in arr[:-1]: print(pre[a], nxt[a], end=" ")
print(pre[arr[-1]], nxt[arr[-1]])

ZeroJudge 解題筆記：e984. 連假時在做什麼？有沒有空？可以來打code嗎？

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


ZeroJudge 題目連結：e984. 連假時在做什麼？有沒有空？可以來打code嗎？

解題想法

用一個自訂函式 find_lln 找第 k 項的 LunlunNumber。在函式中用一個 deque 儲存待處理的數字，先放入 1 ~ 9，再用一個 while 迴圈，當 que 還有資料繼續執行；在迴圈中每次取出 que 開頭的數字存入 num，計數器 cnt 數量加 1，如果 cnt 等於 k，已經找到答案，回傳 num；如果 cnt 小於 k，取出 num 的個位數 last_digit，計算 last_digit 加減 1、不變、加 1 的數值 next_digit，如果 next_digit 在 1 到 9 之中，將新的數值加入 que 之中。

Python 程式碼

單筆測資，使用時間約為 2 s，記憶體約為 93.2 MB，通過測試。

from collections import deque

def find_lln(k):  # 找第 k 位的 Lunlun Number
    que = deque([i for i in range(1, 10)])  # 待處理的數字，先放入 1 ~ 9
    cnt = 0  # 計數器
    while que:  # 當 que 還有資料繼續執行
        num = que.popleft()  # 取出 que 開頭的數字
        cnt += 1  # 計數器加 1
        if cnt == k:  # 如果是第 k 位
            return num  # 回傳 num 並離開函式
        last_digit = num%10  # 取出個位數
        for delta in (-1, 0, 1):  # 個位數的差值 -1, 0, 1
            next_digit = last_digit + delta  # 下一個個位數值
            if 0 <= next_digit <= 9:  # 如果在 0 ~ 9 之間
                que.append(num*10 + next_digit)  # 新的數值加入 que
    return 0  # 預設的回傳值，理論上不會用到

print(find_lln(int(input())))