熱門文章

2025年10月25日 星期六

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


2025年10月24日 星期五

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


2025年10月23日 星期四

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


2025年10月22日 星期三

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) 


2025年10月21日 星期二

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


2025年10月20日 星期一

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


2025年10月19日 星期日

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)


2025年10月18日 星期六

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)  # 印出答案


2025年10月17日 星期五

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


2025年10月16日 星期四

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}%")


2025年10月15日 星期三

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)  # 印出答案


2025年10月14日 星期二

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


2025年10月13日 星期一

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)


2025年10月12日 星期日

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)  # 印出最高時薪的工作名稱


2025年10月11日 星期六

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


2025年10月10日 星期五

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)


2025年10月9日 星期四

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)


2025年10月8日 星期三

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


2025年10月7日 星期二

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


2025年10月6日 星期一

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


2025年10月5日 星期日

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)  # 答案是列、欄相乘


2025年10月4日 星期六

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)


2025年10月3日 星期五

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


2025年10月2日 星期四

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


2025年10月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())))


2025年9月30日 星期二

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()  # 跑完一塊餅乾要換行


2025年9月29日 星期一

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


2025年9月28日 星期日

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}")  # 印出答案


2025年9月27日 星期六

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


2025年9月26日 星期五

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


2025年9月25日 星期四

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


2025年9月24日 星期三

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


2025年9月23日 星期二

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


2025年9月22日 星期一

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)


2025年9月21日 星期日

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


2025年9月20日 星期六

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


2025年9月19日 星期五

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


2025年9月18日 星期四

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


2025年9月17日 星期三

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


2025年9月16日 星期二

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


2025年9月15日 星期一

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 贏


2025年9月14日 星期日

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)


2025年9月13日 星期六

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)


2025年9月12日 星期五

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()  # 空一行


2025年9月11日 星期四

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


2025年9月10日 星期三

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!


2025年9月9日 星期二

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])  # 印出最大值


2025年9月8日 星期一

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


2025年9月7日 星期日

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],接成字串再輸出


2025年9月6日 星期六

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


2025年9月5日 星期五

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] 代入表中找字母組成字串


2025年9月4日 星期四

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


2025年9月3日 星期三

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 合併成一個很長的字串再一次輸出


2025年9月2日 星期二

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


2025年9月1日 星期一

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}%")


2025年8月31日 星期日

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


2025年8月30日 星期六

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)


2025年8月29日 星期五

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

2025年8月28日 星期四

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()  # 前序走訪

2025年8月27日 星期三

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


2025年8月26日 星期二

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 只剩一個值,就是答案


2025年8月25日 星期一

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 找答案


2025年8月24日 星期日

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


2025年8月23日 星期六

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 種組合


2025年8月22日 星期五

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("")  # 最後要換行

2025年8月21日 星期四

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)


2025年8月20日 星期三

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


2025年8月19日 星期二

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]


2025年8月18日 星期一

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)  # 印出答案


2025年8月17日 星期日

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)


2025年8月16日 星期六

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)  # 印出答案


2025年8月15日 星期五

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)  # 印出答案


2025年8月14日 星期四

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])  # 印出答案


2025年8月13日 星期三

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


2025年8月12日 星期二

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


2025年8月11日 星期一

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


2025年8月10日 星期日

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")  # 印出答案


2025年8月9日 星期六

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


2025年8月8日 星期五

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


2025年8月7日 星期四

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


2025年8月6日 星期三

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


2025年8月5日 星期二

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)


2025年8月4日 星期一

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)  # 印出答案


2025年8月3日 星期日

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