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())))

ZeroJudge 解題筆記：e698. OREOREO!

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


ZeroJudge 題目連結：e698. OREOREO!

解題想法

我先計算 O 的部分較寬及 RE 的部分較寬兩種狀況下，分別要印出的 O 及 RE 的字串。接下來讀取 n 塊餅乾的組成方式，依序輸出每一塊餅乾對應的形狀。

Python 程式碼

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

import sys

for line in sys.stdin:
    w1, h1 = map(int, line.split())
    w2, h2 = map(int, sys.stdin.readline().split())
    c1, c2 = sys.stdin.readline().split()
    if w1 > w2:  # O 的部分較寬
        O = c1*w1
        RE = " "*((w1-w2)//2) + c2*w2
    else:  # RE 的部分較寬
        O = " "*((w2-w1)//2) + c1*w1
        RE = c2*w2
    n = int(sys.stdin.readline())  # 接下來有 n 塊餅乾
    for _ in range(n):  # 執行 n 次
        cookie = sys.stdin.readline().strip()  # 餅乾的組成
        i = 0  # 從 cookie 讀取資料用的索引值
        while i < len(cookie):  # 如果 i 還沒有出界時繼續執行
            if cookie[i] == "O":  # 如果是 O
                for _ in range(h1): print(O)  # 印出 h1 行的 O
                i += 1  # i 加 1
            elif cookie[i] == "R":  # 如果是 RE
                for _ in range(h2): print(RE)  # 印出 h2 行的 RE
                i += 2  # i 加 2
        print()  # 跑完一塊餅乾要換行

ZeroJudge 解題筆記：e623. 2. PPAP

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


ZeroJudge 題目連結：e623. 2. PPAP

解題想法

先用一個 while 迴圈，計算序號 n 是第 m 輪領到東西，計算時每一輪會將 n 減去這一輪的數量。跑完 while 迴圈之後，如果 n 等於 0，代表是第 m 輪的最後一個人，印出 Pineapple pen； 反之進到下一輪，先將 m 加 1，計算 n 對 m 取整數除法的結果，輸出對應的物品名稱。

Python 程式碼

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

n = int(input())  # 編號
m = 0  # 第 m 輪
s = 0  # 第 m 輪的數量，每次加 4
while n >= s+4:  # 如果 n 的數量大於等於 s+4，還有下一輸，繼續執行
    m += 1; s += 4  # m 加 1；s 加 4
    n -= s  # n 減去 s

if n == 0:  # 剛好是第 m 輪的最後一個人
    print("Pineapple pen")  # 印出 Pineapple pen
else:  # 要再到下一輪
    m += 1  # m 加 1
    if n%m == 0: n -= 1
    item = n // m
    if item == 0: print("Pen")
    elif item == 1: print("Pineapple")
    elif item == 2: print("Apple")
    else: print("Pineapple pen")

ZeroJudge 解題筆記：e622. 3. 虛擬寵物大師 (Master)

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


ZeroJudge 題目連結：e622. 3. 虛擬寵物大師 (Master)

解題想法

我另外寫兩個函式，函式 ivcp 輸入 iv 值，回傳升級時增加的 cp 值；函式 upgrade 輸入原有的星塵沙子數量 star，iv 值、原來的 cp 值，計算升級後的 cp 值。

Python 程式碼

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

# 輸入 iv 值，回傳升級時增加的 cp 值
def ivcp(iv):
    if 0 <= iv <= 29: return 10
    elif 30 <= iv <=39: return 50
    elif 40 <= iv <= 45: return 100

# 輸入原有的星塵沙子數量 star，iv 值、原來的 cp 值，計算升級後的 cp 值
def upgrade(star, iv, cp):
    while star >= 1000:
        star -= 1000
        cp += ivcp(iv)
    return cp

# 解題過程
n, s = map(int, input().split())  # 寵物數量 n，原有的星塵沙子數量 s
imax, idx = 0, 0  # 升級後最高的 cp 值及寵物編號
for i in range(1, n+1):  # 讀取 n 行資料
    c, v = map(int, input().split())  # 讀取原來的 cp 值、iv 值
    re = upgrade(s, v, c)  # 呼叫 upgrade，代入 s, v, c，計算升級後的 cp 值
    if re > imax:  # 如果 re 大於 imax
        imax = re  # 更新 imax
        idx = i  # 更新 idx
print(f"{idx:d} {imax:d}")  # 印出答案

ZeroJudge 解題筆記：e621. 1. 免費停車 (Free Parking)

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


ZeroJudge 題目連結：e621. 1. 免費停車 (Free Parking)

解題想法

這題應該是多行測資，但是題目沒有說清楚。讀取測資中的 A、B、C 三個數字之後，用 for 迴圈跑 i = A-1 到 i = B-1，當 i 不能被 C 整除就加入答案之中。

Python 程式碼

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

import sys

for line in sys.stdin:
    N = int(line)
    for _ in range(N):
        A, B, C = map(int, input().split())
        ans = []
        for i in range(A+1, B):
            if i%C != 0: ans.append(i)
        if ans: print(*ans)
        else: print("No free parking spaces.")

ZeroJudge 解題筆記：e494. 無窮級數之和(二)

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


ZeroJudge 題目連結：e494. 無窮級數之和(二)

解題想法

這題考數學及大數運算，所以我只有寫 Python 版本。公式解 $$ \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots + \frac{1}{p} = \ln(\ln p) + M = \ln(\ln p) + 0.2614972128476427837554268386 $$ 由於輸出的小數位數很多，甚至要用到 decimal 函式庫的浮點數物件 Decimal 才行。

Python 程式碼

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

import sys, decimal

def solve(n):
    decimal.getcontext().prec = 1000  # 設定小數位數
    p = decimal.Decimal(n)  # 用 Decimal 格式的浮點數
    if p == decimal.Decimal(2):  # 特例，n 等於 2，回傳 0.5
        return decimal.Decimal('0.5')
    # 公式解，ln(ln(n)) + M
    ln_ln_p = p.ln().ln()
    M = decimal.Decimal('0.2614972128476427837554268386')
    return round(ln_ln_p + M, 3)

for line in sys.stdin:
    print(f"{solve(decimal.Decimal(line)):.3f}")

ZeroJudge 解題筆記：e484. 我是優質學生

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


ZeroJudge 題目連結：e484. 我是優質學生

解題想法

這題要判斷輸入的數字是否為 2 到 10000 之間的質數，由於輸入只有一行，不要建質數表，直接判斷這個數是否為質數就好。

Python 程式碼

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

def is_prime(n):  # 判斷是否為質數
    if n <= 1: return False  # 特例，小於等於1，回傳 False
    if n == 2 or n == 3: return True  # 特例，等於 2 或 3，回傳 True
    if n%2 == 0 or n%3 == 0: return False  # 特例，可以被 2 或 3 整除，回傳 False
    for i in range(5, int(n**0.5)+1, 6):  # 依序檢查 5 ~ sqrt(n)，每次加 6
        if n%i == 0 or n%(i+2) == 0:  # 如果可以被 i 或 i+2 整除，回傳 Fasle
            return False
    return True  # 最後回傳 True

print("yes" if is_prime(int(input())) else "no")

ZeroJudge 解題筆記：e470. 無窮級數之和(一)

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


ZeroJudge 題目連結：e470. 無窮級數之和(一)

解題想法

這題考數學，當 $n$ 很大時，有近似公式 $$ \sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + \frac{1}{2n} $$ 其中 $\gamma = 5772156649$。

Python 程式碼

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

import sys, math

def harmonic_number(n):
    if n <= 20:  # 如果 n 小於等於 20，直接用迴圈計算
        isum = 0
        for i in range(1, n+1): isum += 1/i
        return isum
    gamma = 0.5772156649  # 反之，代近似公式
    return math.log(n) + gamma + 1.0 / (2 * n)

for line in sys.stdin:
    print(f"{harmonic_number(int(line)):.3f}")

ZeroJudge 解題筆記：e447. queue 練習

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


ZeroJudge 題目連結：e447. queue 練習

解題想法

這題就是考 queue 的操作，在 Python 要引入 collections 函式庫的 deque，在 C++ 要引入 queue 或是 deque 都可以。

Python 程式碼

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

from collections import deque

n = int(input())
arr = deque()
for _ in range(n):
    line = list(map(int, input().split()))
    if len(line) == 1:
        if line[0] == 2:
            if arr: print(arr[0])
            else: print(-1)
        elif line[0] == 3 and arr: arr.popleft()
    else:
        arr.append(line[1])

ZeroJudge 解題筆記：e446. 排列生成

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


ZeroJudge 題目連結：e446. 排列生成

解題想法

這題不論用 Python 還是 C++ 都可以用遞迴窮舉所有的排列方式。在 Python 也可以用 itertools.permutaions，在 C++ 也可以用 next_permutation。但主要的困難之處是輸出速度，要加速才能過關。

Python 程式碼

窮舉，用 print 輸出，超時。

def solve(arr, n, used):
    if len(arr) == n:
        print(*arr)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(input()), set())

窮舉，用 sys.stdout.write 輸出，超時。

import sys

def solve(arr, n, used):
    if len(arr) == n:
        s = " ".join(map(str, arr)) + "\n"
        sys.stdout.write(s)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(sys.stdin.readline()), set())

用 itertools.permutations，用 sys.stdout.write 最後再一次輸出所有結果，最後一筆測資超出記憶體上限。

import sys, itertools

result = []
n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm))
    result.append(f"{s}\n")
sys.stdout.write("".join(result))

用 itertools.permutations，用 sys.stdout.write 逐行輸出結果。使用時間約為 12.3 s，記憶體約為 3.4 MB，通過測試。

import sys, itertools

n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm)) + "\n"
    sys.stdout.write(s)

ZeroJudge 解題筆記：e420. 灰姑娘的新衣

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


ZeroJudge 題目連結：e420. 灰姑娘的新衣

解題想法

我用字典 color_idx 儲存各種顏色對應的衣服編號，另一個字典 idx_color 儲存各種衣服編號有的顏色，顔色不重複。最後再計算所有的組合數，輸出最多顔色的衣服，輸出完美搭配的顔色。

Python 程式碼

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

import sys
from collections import defaultdict

color_idx = defaultdict(list)  # 各種顏色對應的衣服編號，可重複
idx_color = defaultdict(set)  # 各種衣服編號有的顏色，不重複
cnt = 0  # 衣服編號
for line in sys.stdin:
    line = line.strip()  # 刪除最後的 \n
    cnt += 1  # 衣服編號加 1
    color_idx[line].append(cnt)  # 顏色 line 有的編號加上 cnt
    idx_color[cnt].add(line)  # 編號 cnt 有的顏色加上 line
    for s in sys.stdin:
        s = s.strip()  # 讀取一行字串，刪除最後的 \n
        if s == "@" or s == "#": break  # 讀到 # 或 @，中止迴圈
        color_idx[s].append(cnt)  # 顏色 s 有的編號加上 cnt
        idx_color[cnt].add(s)  # 編號 cnt 有的顏色加上 s，不重複
comb = 1  # 組合數
for v in idx_color.values(): comb *= len(v)
print(comb)
most_color = []
n = len(idx_color)  # 編號數量
perfect = []
imax = max([len(v) for v in color_idx.values()])
for k, v in color_idx.items():
    if len(v) == imax:
        most_color.append(k)
    if len(set(v)) == n:
        perfect.append(k)
print(",".join(sorted(most_color)))
print(",".join(sorted(perfect)))

ZeroJudge 解題筆記：e293. 花開花落，雨初臨

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


ZeroJudge 題目連結：e293. 花開花落，雨初臨

解題想法

這題的題目敘述根本就是在寫小說，重點只有「要找出給定的數字在 100 以內的質因數」。解題時要先建表 primes，列出 0 到 100 之間的質數，只有 25 個，直接打進程式碼就好。接下來計算這些質數相乘的結果 pq，假設要檢查的數字為 $m$，如果 $s = gcd(m, pq)$ 等於 1，則 $m$ 在 0 到 100 之間沒有質因數；反之，從 primes 之中依序取出質數 prime，檢查 prime 是否為 s 的因數即可。不過這題的輸出最大會到 5000 位，要用大數運算，所以我只有用 Python 解題。

Python 程式碼

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

import sys, math

# 建表，2 ~ 100 之間的質數
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
          31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
          73, 79, 83, 89, 97}
# pq，2 ~ 100 所有的質數相乘
pq = 1
for prime in primes: pq *= prime
# 主要的解題過程
result = []  # 儲存結果用的空串列
lines = sys.stdin.readlines()
for line in lines[1:]:
    m = int(line)  # 轉成整數 m
    res = []  # 儲存 m 的答案用的空串列
    s = math.gcd(m, pq)
    if s == 1:  # m 在 0 到 100 之間沒有質因數
        result.append("Terrible Silence...\n")
    else:
        for prime in primes:  # 依序由 primes 中取出質數，檢查是否為 s 的因數
            if s%prime == 0:  # 如果 prime 是因數
                res.append(f"{prime:d}")  # prime 轉成字串加入 res
        result.append(" ".join(res) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e284. 放暑假了!!!!!

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


ZeroJudge 題目連結：e284. 放暑假了!!!!!

解題想法

這題主要考輸入、輸出優化，因為測資數量極大，如果沒有優化輸入、輸出會超時。在 Python 我習慣用 sys.stdin.readlines() 一次讀取所有的測資，並將所有的輸出存在串列 result 之中，最後再用 sys.stdout.write("".join(result)) 一次印出所有答案。在 C++ 如果要用 cin 及 cout，必須加上 ios::sync_with_stdio(0); cin.tie(0);，不然就是改用 scanf 及 printf。事先用字典或集合建表，儲存 $2^0$ 到 $2^31$ 對應的值，讀取測資之後再判斷這個數字是否在表格之中，這樣速度會比較快。但是經過實測之後發現，C++ 的 map 及 unordered_map 都很慢，要用 set 才能過關； Python 的 dict, defaultdict, set 都能過關。

Python 程式碼

用 dict 建表，使用時間約為 4.2 s，記憶體約為 413.6 MB，通過測試。

import sys

table = dict()
x = 1
for _ in range(32):
    table[x] = True
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

用 set 建表，使用時間約為 4.1 s，記憶體約為 418.2 MB，通過測試。

import sys

table = set()
x = 1
for _ in range(32):
    table.add(x)
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e272. gcd(Fm,Fn)

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


ZeroJudge 題目連結：e272. gcd(Fm,Fn)

解題想法

這題考數學，必須運用費氏數列的特性 $$ gcd(F_m, F_n) = F_{gcd(m, n)} $$ 如果直接計算 $F_m, F_n$ 的數值再取 $gcd$，在 $m, n$ 極大的狀況下會超時。

Python 程式碼

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

import sys, math

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

for line in sys.stdin:
    a, b = map(int, line.split())
    print(fib[math.gcd(a, b)])

ZeroJudge 解題筆記：e128. 新北100-1貪食蛇

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


ZeroJudge 題目連結：e128. 新北100-1貪食蛇

解題想法

這題要找位置的數學規律，如果模擬移動的過程一定會超時。

Python 程式碼

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

import math, sys

def find_position(t):  # 輸入目前的時刻計算位置
    if t == 1: return (1, 1)  # 特例，t 等於 1，回傳 (1, 1) 並結束函式
    
    ring = math.floor(math.sqrt(t))  # 已走完的圈數
    #ring = math.isqrt(t)    # 已走完的圈數，Python 3.8 之後才有 math.isqrt
    
    t -= ring * ring  # t 扣掉已走完的圈數平方，換成位移量
    if t == 0:  # 如果 t 等於 0，剛好在這圈結束的位置
        if ring%2: return (1, ring)  # 如果是奇數圈，回傳 (1, ring) 並結束函式
        else: return (ring, 1)  # 如果是偶數圈，回傳 (ring, 1) 並結束函式
    else: ring += 1  # 其它狀況，圈數加 1
    
    x, y = 0, 0  # 座標 (x, y)
    if ring%2:  # 奇數圈
        if t > ring:  # 在底部向左移動
            x = 2*ring - t  
            y = ring
        else:  # 在右側向下移動
            x = ring
            y = t
    else:  # 偶數圈
        if t > ring:  # 在右側向上移動
            x = ring
            y = 2*ring - t
        else:  # 在底部向右移動
            x = t
            y = ring
    
    return (x, y)

for line in sys.stdin:
    t = int(line)
    if t == 0: break
    print(*find_position(t))

ZeroJudge 解題筆記：d985. Gran Turismo 5

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


ZeroJudge 題目連結：d985. Gran Turismo 5

解題想法

依序讀取每一圈的時間，將單位換成 s，更新最短秒數、計算總秒數，最後輸出所有圈數的最短秒數及平均。

Python 程式碼

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

track = 0  # 圈數
N = int(input())  # N 組測資
for _ in range(N):  # 執行 N 次
    track += 1  # 圈數加 1
    print(f"Track {track:d}:")
    M = int(input())  # M 行資料
    best = float('inf')  # 最短秒數
    total = 0  # 總秒數
    for _ in range(M):  # 執行 M 次
        m, s = map(int, input().split())  # 單圈時間 m's"
        t = m*60 + s  # 換成秒數
        best = min(best, t)  # 新的最短秒數
        total += t  # 更新總秒數
    average = total // M  # 平均值
    print(f"Best Lap: {best//60:d} minute(s) {best%60:d} second(s).")
    print(f"Average: {average//60:d} minute(s) {average%60:d} second(s).")
    print()

ZeroJudge 解題筆記：d984. 棄保效應

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


ZeroJudge 題目連結：d984. 棄保效應

解題想法

我用三層 if 解題，討論 A、B、C 三個人分別為最高票的狀況下，第一名票數減去第三名的票數之後是否仍大於第二名的票數。

Python 程式碼

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

import sys

for line in sys.stdin:
    a, b, c = map(int, line.split())  # 三個人的票數
    if a > b and a > c:  # A 最高票
        if b > c:  # B 第二名
            if a-c > b: print("A")  # A 減 C 的票數還贏
            else: print("B")  # 反之 B 贏
        else:  # C 第二名
            if a-b > c: print("A")  # A 減 B 的票數還贏
            else: print("C")  # 反之 C 贏
    elif b > a and b > c:  # B 最高票
        if a > c:  # A 第二名
            if b-c > a: print("B")  # B 減 C 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # C 第二名
            if b-a > c: print("B")  # B 減 A 的票數還贏
            else: print("C")  # 反之 C 贏
    else:  # C 最高票
        if a > b:  # A 第二名
            if c-b > a: print("C")  # C 減 B 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # B 第二名
            if c-a > b: print("C")  # C 減 A 的票數還贏
            else: print("B")  # 反之 B 贏

ZeroJudge 解題筆記：d881. 作業苦多

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


ZeroJudge 題目連結：d881. 作業苦多

解題想法

這題可以寫迴圈直接跑，也可以先推導數學公式之後再代公式求解。

Python 程式碼

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

import sys

for line in sys.stdin:
    d = int(line)  # 公差的增量
    dp = [0]*51  # 儲存第 0 ~ 50 項的串列
    dp[1] = 1  # 第 1 項為 1
    b = 1  # 公差，預設為 1
    isum = 1  # 加總，先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        dp[i] = dp[i-1] + b  # 第 i 項為第 i-1 項加上 b
        isum += dp[i]  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

只要用到前一項，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    d = int(line)  # 公差的增量
    last = 1  # 第 1 項為 1
    b = 1  # 公差，預設為 1
    isum = 1  # 加總，先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        last += b  # 第 i 項為第 i-1 項加上 b
        isum += last  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

直接代公式，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    print(1275 + int(line)*19600)

ZeroJudge 解題筆記：d732. 二分搜尋法

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


ZeroJudge 題目連結：d732. 二分搜尋法

解題想法

可以自訂二分搜尋法的函式，也可以用 Python 的 bisect.bisect_left 或是 C++ algorithm 函式庫的 lower_bound 解題。注意，這題的位數是從 1 開始計算，搜尋到的索引值要加 1 才是答案。

Python 程式碼

自己寫二分搜尋法，使用時間約為 1.1 s，記憶體約為 20.9 MB，通過測試。

def binary_search(arr, target):  # 自己寫二分搜尋法，代入串列 arr 及目標 target
    low, high = 0, len(arr)-1  # 索引值的下限、上限
    while low <= high:  # 如果 low 小於等於 high 繼續執行
        mid = (high - low) // 2 + low  # 計算中間值 mid
        if arr[mid] == target: return mid+1  # 找到目標，回傳 mid，離開函式
        if arr[mid] > target:  # 目標在左半邊，降低 high
            high = mid - 1
        else:  # 目標在右半邊，提升 low
            low = mid + 1
    if arr[low] != target: return 0  # 如果沒有找到目標，回傳 0

if __name__ == "__main__":
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    for t in map(int, input().split()):
        print(binary_search(arr, t))

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

from bisect import bisect_left

n, k = map(int, input().split())
arr = list(map(int, input().split()))
for x in map(int, input().split()):
    idx = bisect_left(arr, x)
    if arr[idx] == x: print(idx+1)
    else: print(0)

ZeroJudge 解題筆記：d710. parking lot

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


ZeroJudge 題目連結：d710. parking lot

解題想法

這題用字典儲存資料很方便，一個儲存廠牌對應的顏色，另一個儲存顏色對應的廠牌，最後再依照測資從字典中讀取資料並輸出。

Python 程式碼

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

import sys
from collections import defaultdict

for line in sys.stdin:
    if not line.strip(): continue  # 跳過空行
    n, m = map(int, line.split())  # n 輛車， m 個指示
    brands = defaultdict(list)  # 廠牌對應的顏色
    colors = defaultdict(list)  # 顏色對應的廠牌
    for _ in range(n):  # 讀取 n 行資料
        b, c = input().split()  # 廠牌 b，顏色 c
        brands[b].append(c)
        colors[c].append(b)
    for _ in range(m):  # 讀取 m 個指示
        x, y = input().split()
        if x == "brand":  # 如果 x 等於 brand
            for c in brands[y]:  # 依序取出 brands[y] 的顏色
                print(f"{y:s} {c:s}")
        elif x == "color":  # 如果 x 等於 color
            for b in colors[y]:  # 依序取出 colors[y] 的廠牌
                print(f"{b:s} {y:s}")
    print()  # 空一行

ZeroJudge 解題筆記：d681. BinaryCount

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


ZeroJudge 題目連結：d681. BinaryCount

解題想法

每次讀取一行字串，直到 EOF 為止。將字串用空格分割，如果分割後的字串為 s，在 Python 可以用 int(s, 2) 轉換成 int，在 C++ 可以用 bitset。先儲存首項的數值，接下來一次讀取一個運算符號及整數，依照運算符號計算數值，同時組合要輸出的運算式。

Python 程式碼

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

import sys

for line in sys.stdin:
    arr = list(line.split())  # 分割讀到的字串
    equ = [arr[0]]  # 要輸出的算式，先放入 arr[0]
    last = int(arr[0], 2)  # 前一個計算結果，先放入 arr[0] 用 2 進位換算的整數
    n = len(arr)  # arr 的長度
    for i in range(1, n, 2):  # 依序處理 arr[1], arr[2] ~ arr[n-2], arr[n-1]
        op = arr[i]  # 運算符號
        if op == "and":  # 如果是 and
            equ.append("&&")  # 將 && 加入 equ
            last = last & int(arr[i+1], 2)  # 將 last 與 arr[i+1] 用 2 進位換算的整數取 &
        elif op == "or":  # 如果是 or
            equ.append("||")  # 將 || 加入 equ
            last = last | int(arr[i+1], 2)  # 將 last 與 arr[i+1] 用 2 進位換算的整數取 |
        equ.append(arr[i+1])  # 將 arr[i+1] 加入 equ
    print("".join(equ) + " = " + bin(last)[2:].zfill(5))  # 拼成要輸出的算式，計算結果要補 0

ZeroJudge 解題筆記：d643. 勞動的符咒

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


ZeroJudge 題目連結：d643. 勞動的符咒

解題想法

如果輸入的字串 s 長度為 n，先找 n 的所有因數，再用字串切片，將 s 切成因數長度的子字串，將子字串排序後連接成新的字串 t。用集合 spells 儲存新的咒語，如果 t 不在 spells 之中才輸出。

Python 程式碼

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

s = input().strip()  # 讀取字串
n = len(s)  # 字串長度
factors = {1}  # n 的因數，先放入 1
for i in range(2, int(n**0.5)+1):  # 找 2 ~ sqrt(n)+1 之間的因數
    if n%i == 0:
        factors.add(i)
        factors.add(n//i)
spells = {s}  # 可能的咒語，先放入 s
for factor in sorted(factors):  # 測試由小到大的所有因數
    # 取因數長度的子字串，排序後接成新的字串 t
    t = "".join(sorted([s[i:i+factor] for i in range(0, n, factor)]))
    if t not in spells:  # 如果 t 不在 spells 之中
        spells.add(t)  # t 加入 spells
        print(t)  # 印出 t
if len(spells) == 1: print("bomb!")  # 如果 spells 只有一項，印出 bomb!

ZeroJudge 解題筆記：d637. 路過的鴨duck

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


ZeroJudge 題目連結：d637. 路過的鴨duck

解題想法

這題考 0/1 背包問題，我習慣的寫法是先建立一個一維陣列 dp，分別對應食量為 0 ~ 上限 imax 對應的最大飽足感總和。依序讀取每個食物的體積 a 及飽足感 b，從 dp[imax] 往回更新總和至 dp[a] 為止，取 dp[i] 與 dp[i-a] + b 較大者，最後答案在 dp[imax] 。

Python 程式碼

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

n = int(input())  # n 顆飼料
imax = 100  # 食量上限
dp = [0]*(imax + 1)  # 吃 0 ~ 100 分別對應的最大飽足感
for _ in range(n):  # 依序讀取 n 行資料
    a, b = map(int, input().split())  # 飼料的體積 a、飽足感 b
    for i in range(imax, a-1, -1):  # 倒序檢查飽足感 imax ~ a
        dp[i] = max(dp[i], dp[i-a] + b)  # dp[i-a] + b 可能更大
print(dp[imax])  # 印出最大值

ZeroJudge 解題筆記：d636. 大爆炸bomb

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


ZeroJudge 題目連結：d636. 大爆炸bomb

解題想法

這題考快速冪、平方求冪 (exponentiating by squaring)。

Python 程式碼

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

def exp(x, y, p):  # x 的 y 次方，取除以 p 的餘數
    t = 1  # 儲存結果用的變數
    while y:  # 如果 y 不等於 0 繼續執行
        if y&1: t = t*x%p  # 若 y 與 1 取 and 為 1，更新 t，乘上 x 再取 mod p
        y >>= 1  # y 除以 2
        x = x*x%p  # 更新 x，乘上 x 再取 mod p
    return t  # 回傳 t

print(exp(*map(int, input().split()), 10007))  # 印出 exp(a, b, p)

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

print(pow(*map(int, input().split()), 10007))

ZeroJudge 解題筆記：d626. 小畫家真好用

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


ZeroJudge 題目連結：d626. 小畫家真好用

解題想法

用 BFS 及四方位檢查解題，由於我比較懶得檢查邊界值，我會在周圍加上 + 當作哨兵避免出界。

Python 程式碼

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

n = int(input())  # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)]  # 讀取地圖資料，最右側加上 + 作為哨兵
grid.append(list("+"*(n+1)))  # 最下方加 n+1 個 + 作為哨兵
que = [tuple(map(int, input().split()))]  # 待走訪佇列，先放入起點
head = 0  # 從 que 讀取資料用的索引值
while head < len(que):  # BFS，當 head 還沒有出界繼續執行
    r, c = que[head]; head += 1  # 從 que 讀取要走訪的點 (r, c)，head 加 1
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
        nr, nc = r+dr, c+dc  # 要檢查的點 (nr, nc)
        if grid[nr][nc] == "+": continue  # 如果 grid[nr][nc] 是 +，找下一個點
        grid[nr][nc] = "+"  # grid[nr][nc] 改成 +
        que.append((nr, nc))  # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n]))  # 依序讀取 grid[:n][:n]，接成字串再輸出

改用 deque 儲存待走訪節點，使用時間約為 25 ms，記憶體約為 3.7 MB，通過測試。

from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)]  # 讀取地圖資料，最右側加上 + 作為哨兵
grid.append(list("+"*(n+1)))  # 最下方加 n+1 個 + 作為哨兵
que = deque([tuple(map(int, input().split()))])  # 待走訪佇列，先放入起點
while que:  # BFS，當 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除要走訪的點 (r, c)
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
        nr, nc = r+dr, c+dc  # 要檢查的點 (nr, nc)
        if grid[nr][nc] == "+": continue  # 如果 grid[nr][nc] 是 +，找下一個點
        grid[nr][nc] = "+"  # grid[nr][nc] 改成 +
        que.append((nr, nc))  # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n]))  # 依序讀取 grid[:n][:n]，接成字串再輸出

ZeroJudge 解題筆記：d623. 反方陣

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


ZeroJudge 題目連結：d623. 反方陣

解題想法

假設矩陣 $$ M = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} $$ 其行列式值 $det(M) = ad - bc$。如果 $det(M) \neq 0$，$M$ 是可逆的，其反矩陣 $$ M^{-1} = \frac{1}{det(M)} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix} $$ 另外要注意，題目的說明是4個0表示結束，實際測資以一個零表示結束。

Python 程式碼

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

while True:
    line = list(map(int, input().split()))
    if len(line) == 1 and line[0] == 0: break  # 只有一個 0，中止迴圈
    a, b = line  # 方陣 [[a, b], [c, d]]
    c, d = map(int, input().split())
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        print("cheat!")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        print(f"{d/det:.5f} {-b/det:.5f}")
        print(f"{-c/det:.5f} {a/det:.5f}")

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

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    if lines[idx].strip() == "0": break  # 只有一個 0，中止迴圈
    a, b = map(int, lines[idx].split())  # 方陣 [[a, b], [c, d]]
    idx += 1
    c, d = map(int, lines[idx].split())
    idx += 1
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        result.append("cheat!\n")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        result.append(f"{d/det:.5f} {-b/det:.5f}\n")
        result.append(f"{-c/det:.5f} {a/det:.5f}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d586. 哈密瓜美語

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


ZeroJudge 題目連結：d586. 哈密瓜美語

解題想法

這題用兩個字典建立數字轉英文、英文轉數字的對照表，再依照讀取到的測資開頭是數字或字母，判斷要從哪一個表格找答案。

Python 程式碼

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

s1 = "mjqhofawcpnsexdkvgtzblryui"  # 數字轉英文用的字串
s2 = "uzrmatifxopnhwvbslekycqjgd"  # 英文轉數字用的字串
ntoc, cton = dict(), dict()  # 數字轉英文、英文轉數字的對照表
for i, c in enumerate(s1, start=1): ntoc[str(i)] = c
for i, c in enumerate(s2, start=1): cton[c] = i
n = int(input())  # n 道謎題
for _ in range(n):  # 執行 n 次
    line = list(input().split())  # 讀取一行資料分割後存入串列
    m = int(line[0])  # 資料長度為 m
    if line[1].isalpha():  # 如果 line[1] 是字母
        print(sum(cton[c] for c in line[1:]))  # 依序讀取 line[1] ~ line[-1] 代入表中找數字求加總
    else:  # 如果 line[1] 是數字
        print("".join([ntoc[i] for i in line[1:]]))  # 依序讀取 line[1] ~ line[-1] 代入表中找字母組成字串

ZeroJudge 解題筆記：d584. 技能點數skill

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


ZeroJudge 題目連結：d584. 技能點數skill

解題想法

依照職業及當時的等級更新技能點數即可。

Python 程式碼

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

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    job, level = map(int, line.split())
    tot = 0
    if job == 2 and level >= 8:  # 如果是法師，8 級一轉
        tot += 1 + (level-8)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    elif (job == 1 or job == 3 or job == 4) and level >= 10:  # 如果是劍士、弓箭手、盜賊，10 級一轉
        tot += 1 + (level-10)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    if job != 0 and level >= 30: tot += 1  # 如果不是初心者，30 級二轉，點數加 1
    if job != 0 and level >= 70: tot += 1  # 如果不是初心者，70 級三轉，點數加 1
    if job != 0 and level >= 120: tot += 3  # 如果不是初心者，120 級四轉，點數加 3
    result.append(f"{tot:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d575. 末日審判

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


ZeroJudge 題目連結：d575. 末日審判

解題想法

這題看起來很簡單，只要計算兩個點之間的距離是否小於、等於半徑即可，但是用 Python 解題時需要用 sys.stdin.readlines() 及 sys.stdour.write() 加速，否則會超時；用 C++ 解題要使用 long long，否則會溢位。

Python 程式碼

第8筆測資超時。

import sys

for line in sys.stdin:
    x0, y0, x1, y1, r = map(int, line.split())
    if abs(x0-x1) + abs(y0-y1) <= r: print("die")
    else: print("alive")

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

import sys

lines = sys.stdin.read().splitlines()  # 一次讀取所有資料，減少讀取次數
results = []  # 儲存要輸出的結果
for line in lines:  # 從 lines 依序讀取資料 line
    x0, y0, x1, y1, r = map(int, line.split())  # 用 split 拆開 line，轉成 int，存入變數
    if abs(x0-x1) + abs(y0-y1) <= r: results.append("die\n")  # 先將要輸出的字串加到 results
    else: results.append("alive\n")
sys.stdout.write("".join(results))  # 將 results 合併成一個很長的字串再一次輸出

ZeroJudge 解題筆記：d574. 節約符咒

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


ZeroJudge 題目連結：d574. 節約符咒

解題想法

第4筆測資只有一行，用空格分隔數量與字串，用 Python 解題需要特別處理。依序讀取字串中每個字母，計算連續出現的相同字母數量，將數量與對應的字母組成字串。

Python 程式碼

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

line = list(input().split())  # 讀取一行資料並用空格分隔存成串列
n = int(line[0])  # 字串長度
if len(line) == 1: s = input().strip()  # 如果 line 只有一項，再讀取一行字串
else: s = line[1]  # 反之，字串在 line[1]
t = ""  # 儲存答案用的空字串
cnt = 1  # 連續相同字母的數量，預設為 1
last = s[0]  # 前一個字母，預設為 s[0]
for c in s[1:]:  # 依序讀取 s[1] ~ s[n-1]
    if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
    else:  # 反之，結算之的連續相同字母數量
        t += str(cnt) + last  # cnt 轉成字串加上 last，接到 t 之後
        cnt = 1  # cnt 重置為 1
        last = c  # last 重置為 c
t += str(cnt) + last  # 最後要再結算一次 cnt 與 last
if len(t) < n: print(t)  # 如果 t 較短，印出 t
else: print(s)  # 反之，印出 s

ZeroJudge 解題筆記：d566. 秒殺率

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


ZeroJudge 題目連結：d566. 秒殺率

解題想法

這題要注意：

1. 此處的解題紀錄排在前面的資料代表時間越晚
2. 第 4 筆測資格式有問題，全部塞在同一行，用 Python 解題需要特別處理這筆測資。

Python 程式碼

理論上這樣寫應該要過關，但是第 4 筆測資格式有問題，全部塞在同一行，要再修改程式碼。

cnt = dict()  # 計數器，是否 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # AC 人數
n = int(input())  # n 筆資料
data = [input().split() for _ in range(n)]  # 先讀完所有的資料
for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
    if name not in cnt:  # 如果 name 不在 cnt 之中
        if state == "AC":  # 如果第一次就 AC
            fir += 1  # fir 加 1
            ac += 1  # ac 加 1
            cnt[name] = True  # cnt[name] 為 True
        else:  # 第一次沒有 AC
            cnt[name] = False  # cnt[name] 為 False
    elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
        ac += 1  # ac 加 1
        cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

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

import sys

cnt = dict()  # 計數器，是否第一次就 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # 全部 AC 的人數
for line in sys.stdin:  # 讀資料直到 EOF 為止
    data = line.split()  # 先試著分割資料
    if len(data) == 1:  # 如果只有一筆，是 n
        n = int(data[0])
        data = [input().split() for _ in range(n)]  # 先讀完所有的資料
        for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
    else:  # 為了測資 4 全部塞在一行的狀況
        n = int(data[0])
        for i in range(2*n, 0, -2):  # 反向讀取資料，先讀取時間較早的資料
            name, state = data[i-1], data[i]
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

ZeroJudge 解題筆記：d563. 等值首尾和

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


ZeroJudge 題目連結：d563. 等值首尾和

解題想法

題目敘述有兩個問題：

1. 題目雖然說有兩行測資，第一行為一個數字 N，代表第二行有 N 個用空格分隔的數字，但實際上只有一行，如果用 Python 解題會出事。
2. 範例的寫法看起來好像從左、右加總的數量要一樣，但其實不需要，只要前綴和、後綴和相等就好，不看數量。

Python 程式碼

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

arr = list(map(int, input().split()))[1:]  # 讀取一行資料轉成串列，不取首項
psum = 0  # 前綴和
cand = set()  # 可能的加總
for a in arr:  # 依序讀取 arr 的資料
    psum += a  # 更新 psum
    cand.add(psum)  # psum 加入 cand
ssum = 0  # 後綴和
cnt = 0  # 答案
for a in arr[::-1]:  # 反向讀取 arr 的資料
    ssum += a  # 更新 ssum
    if ssum in cand: cnt +=1  # 如果 ssum 在 cand 之中，cnt 加 1
print(cnt)  # 印出 cnt

ZeroJudge 解題筆記：d561. 被秒殺的四捨五入

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


ZeroJudge 題目連結：d561. 被秒殺的四捨五入

解題想法

這題在 Python 可以用 decimal 函式庫作弊，將數值存成 Decimal 格式的浮點數再四捨五入即可。比較正常的作法，是用字串格式儲存數字，依序判斷數字的正負號、整數位、小數點後第一位、小數點後第二位，最後再依照小數點後第三位的值判斷是否要捨去或進位。

Python 程式碼

用 decimal 函式庫作弊，使用時間約為 24 ms，記憶體約為 3.9 MB，通過測試。

from decimal import Decimal, ROUND_HALF_UP
import sys

for line in sys.stdin:
    # 將 line 轉成 Decimal 格式的十進位數字，4捨5入到小數點後第2位
    n = Decimal(line.strip()).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)
    if str(n) == "-0.00":
        print("0.00")  # -0.00 要輸出為 0.00
    else:
        print(n)

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

import sys

for line in sys.stdin:
    s = line.strip()  # 字串格式的數字
    negative = False  # 是否為負值，預設為 False
    if s[0] == '-':  # 如果 s[0] 是負號
        negative = True  # negative 設定為 True
        s = s[1:]  # 刪除 s[0]
    num = int(s[0])  # 取整數位加到 num
    s = s[2:]  # 刪除整數位、小數點
    if s and s[0] != '0':  # 處理小數點後第 1 位
        num += int(s[0])*0.1
    s = s[1:]  # 刪除 s[0]
    if s and s[0] != '0':  # 處理小數點後第 2 位
        num += int(s[0])*0.01
    s = s[1:]  # 刪除 s[0]
    if negative: num = -num  # 如果是負值，乘以 -1
    if s and s[0] in '56789':  # 如果 s[0] 大於等於 5，要 4 捨 5 入
        if negative: num -= 0.01  # 如果是負值，減 0.01
        else: num += 0.01  # 如果是正值，加 0.01
    if str(num) == "-0.0": print("0.00")  # 如果轉成字串等於 -0.0，要印出 0.00
    else: print(f"{num:.2f}")

使用 Python 及 C++ 産生重複數字的所有排列方式

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

前言

由於最寫連續寫到好幾個題目，需要從測資讀取一列數字，再産生這列數字的所有排列方式，例如 d762. 10344 - 23 out of 5。我之前都是用 Python 的 itertools.permutations 偷懶，但是為了準備之後的課程，還是來研究一下如何用遞迴及回溯産生所有的排列方式。

Python itertools.permutations

這是一個效率很好的迭代器，官方說明書在此 itertools.permutations，通常會搭配 for 迴圈一起使用，語法為

for [産生的數組名稱] in itertools.permutations(可以迭代的物件):

例如要産生 [1, 2, 3, 2, 1] 的所有排列方式可以這樣寫

from itertools import permutations

nums = [1, 2, 3, 2, 1]
for perm in permutations(nums):
    print(*perm)

如果只考慮 5 個數字的排列方式，總共會有 $5! = 120$ 種，以上的程式碼會輸出 120 行。但是這裡面有不少重複的結果，如果只想輸出不重複的結果，可以再稍微修改一下程式碼，用集合記錄已經産生過的結果，這樣就只會輸出 30 行。

from itertools import permutations

nums = [1, 2, 3, 2, 1]
used = set()
for perm in permutations(nums):
    if perm in used: continue
    used.add(perm)
    print(*perm)

ZeroJudge 解題筆記：d555. 平面上的極大點

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


ZeroJudge 題目連結：d555. 平面上的極大點

解題想法

先讀取所有點的座標存入二維串列 points，由大到小排序。用變數 max_y 記錄目前最高的 y 座標，預設值為負無窮大。從 points 之中依序讀取點的座標 x, y，如果符合以下兩種狀況，將 (x, y) 加入答案 ans 之中：

1. y 大於 max_y
2. ans 之中沒有任何一個點可以支配 (x, y)

最後將 ans 排序再印出。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    ca += 1
    print(f"Case {ca:d}:")
    n = int(line)
    point = sorted([tuple(map(int, input().split())) for _ in range(n)], reverse=True)
    ans = []  # 答案
    max_y = -float('inf')  # 目前最高的 y 座標，預設為極小值
    for x, y in point:  # 從 point 依序讀取點的座標 (x, y)
        if y > max_y:  # y 大於 max_y
            ans.append((x, y))  # (x, y) 加入 ans
            max_y = y  # 更新 max_y
        # 另一種可能性，ans 之中沒有任何點可以支配 (x, y)
        elif not any(px >= x and py >= y for px, py in ans):
            ans.append((x, y))
    ans.sort()  # 由小到大排序
    print(f"Dominate Point: {len(ans):d}")
    for x, y in ans: print(f"({x:d},{y:d})")

ZeroJudge 解題筆記：d526. Binary Search Tree (BST)

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


ZeroJudge 題目連結：d526. Binary Search Tree (BST)

解題想法

這題要自訂二元樹類別，遞迴版比較簡潔。

Python 程式碼

遞迴版，使用時間約為 0.7 s，記憶體約為 4 MB，通過測試。

class Node:  # 自訂節點類別
    def __init__(self, data):
        self.data = data  # 資料
        self.left = None  # 左子樹
        self.right = None  # 右子樹

class BST:  # 自訂二元搜尋樹類別
    def __init__(self):
        self.root = None  # 根節點

    def insert(self, data):  # 插入節點
        if self.root is None:  # 如果沒有根節點
            self.root = Node(data)  # 設定根節點
        else:  # 如果有根節點
            self._insert(data, self.root)  # 遞迴，代入 data 及 self.root

    def _insert(self, data, current):  # 內部使用的插入方法
        if data < current.data:  # 如果要插入的資料小於目前節點的資料
            if current.left is None:  # 如果沒有左子樹
                current.left = Node(data)  # data 放在左子樹
            else:  # 如果有左子樹
                self._insert(data, current.left)  # 遞迴，代入 data 及左子樹
        elif data > current.data:  # 如果要插入的資料大於目前節點的資料
            if current.right is None:  # 如果沒有右子樹
                current.right = Node(data)  # data 放在右子樹
            else:  # 如果有右子樹
                self._insert(data, current.right)  # 遞迴，代入 data 及右子樹
    
    def delete(self, data):  # 刪除資料
        self.root = self._delete(self.root, data)
    
    def _delete(self, current, data):  # 內部使用的刪除資料方法
        if current is None:  # 如果 current 是空的
            return current  # 回傳 current 並離開函式
        # 找要刪除的節點
        if data < current.data:  # 如果要刪除的資料小於目前節點的資料
            current.left = self._delete(current.left, data)  # 遞迴，代入左子樹及 data
        elif data > current.data:  # 如果要刪除的資料大於目前節點的資料
            current.right = self._delete(current.right, data)  # 遞迴，代入右子樹及 data
        else:  # 找到要刪除的節點
            if current.left is None:  # 如果左子樹是空的
                return current.right  # 用右子樹取代 node
            elif current.right is None:  # 如果右子樹是空的
                return current.left  # 用左子樹取代 node
            # 有左、右子樹
            temp = self._findMin(current.right)  # 找右子樹中最小資料的節點
            current.data = temp.data  # current 的資料改成 temp 的資料
            current.right = self._delete(current.right, temp.data)  # 刪除右子樹中最小資料的節點
        return current
    
    def _findMin(self, current):  # 內部使用的找最小值方法
        while current.left is not None:  # 向下找左子樹直到空節點為止
            current = current.left
        return current
    
    def preorder(self):  # 前序走訪
        self._preorder(self.root)
        print()

    def _preorder(self, current):  # 內部使用的前序走訪
        if current:  # 如果 current 不是 None
            print(current.data, end=' ')  # 印出 current.data
            self._preorder(current.left)  # 遞迴，代入左子樹
            self._preorder(current.right)  # 遞迴，代入右子樹

import sys

for line in sys.stdin:
    n = int(line)  # 一行有 n 個數字
    tree = BST()  # 建立 BST 物件
    for data in map(int, input().split()):  # 依序讀取此行的數字
        tree.insert(data)  # 將資料插入 tree 之中
    tree.preorder()  # 前序走訪

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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


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

解題想法

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

Python 程式碼

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

from collections import Counter

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

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

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

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

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


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

解題想法

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

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

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

Python 程式碼

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

import sys

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

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

ZeroJudge 解題筆記：d166. 反轉表

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


ZeroJudge 題目連結：d166. 反轉表

解題想法

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

2 3 6 4 0 2 2 1 0

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

9

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

9 8

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

9 8 7

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

9 8 6 7

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

5 9 8 6 7

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

ZeroJudge 解題筆記：c669. missing and duplicate

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


ZeroJudge 題目連結：c669. missing and duplicate

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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

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

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


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

解題想法

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

Python 程式碼

超過記憶體上限。

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

C++ 程式碼

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

#include <iostream>
using namespace std;

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

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

#include <cstdio>
using namespace std;

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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


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

解題想法

先列出幾種可能性

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

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

from math import comb, log10, ceil
import sys

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

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

from math import log10, ceil
import sys

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

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

from math import log10, ceil
import sys

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys, math

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