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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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

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

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


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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

C++ 程式碼

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

#include <cstdio>
using namespace std;

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

import sys

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

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

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

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



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

解題想法

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

Python 程式碼

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

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

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

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

ZeroJudge 解題筆記：l919. P.2 珠寶交易 (Jewel)

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



ZeroJudge 題目連結：l919. P.2 珠寶交易 (Jewel)

解題想法

這題理論上用貪心法就能解，有通過範例測資，但是無法送出解答。

Python 程式碼

無法送出解答。

import sys

for line in sys.stdin:
    n = int(line)  # n 天
    buy = float('inf')  # 最低買價，預設為正無窮大
    profit = 0  # 最大利潤，預設為 0
    best_buy_dat, best_sell_day = 0, 0  # 最佳買入、𧶠出時機
    buy_day = 0  # 買入時機
    for i, p in enumerate(map(int, input().split()), start=1):  # 第 i 天，價格 p
        if p < buy:  # 如果當天的價格小於 buy，更新 buy 及 buy_day
            buy = p; buy_day = i
        elif p - buy > profit:  # 價差大於 profit
            profit = p - buy  # 更新 profit
            best_sell_day = i  # 更新 sell_day
            best_buy_day = buy_day  # 更新 best_buy_day
    if profit > 0: print(best_buy_day, best_sell_day)
    else: print(-1)

ZeroJudge 解題筆記：l918. P1. 彈珠汽水 (Soda)

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



ZeroJudge 題目連結：l918. P1. 彈珠汽水 (Soda)

解題想法

這題有一個陷阱，如果 $N = 1$，每喝一瓶汽水就可以再換一瓶新的汽水，如果寫 while 迴圈的條件時只考慮是否還有沒喝的汽水，這樣會變成無窮迴圈。

Python 程式碼

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

m, n, k = map(int, input().split())  # m 瓶彈珠汽水，n 個瓶子再換一瓶汽水，想要喝到 k 瓶
t, b = 0, 0  # 總瓶數，空瓶數
while m > 0 and t < k:  # 如果還有沒喝的汽水而且還沒有喝到想要的瓶數
    t += m; b += m  # 更新 t, b，加上 m
    m = b//n  # 用空瓶換汽水
    b %= n  # 剩下的空瓶
print("YES" if t >= k else "NO")  # 依照 t 是否大於等於 k 印出答案

ZeroJudge 解題筆記：k931. P8. 切割蜂蜜 (Honey)

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



ZeroJudge 題目連結：k931. P8. 切割蜂蜜 (Honey)

解題想法

這題有 3 個重點：

1. 要設計儲存六角形蜂巢資料的方式，我是用二維串列，偶數列的欄位為 1, 3, 5, ...，奇數列的欄位為 0, 2, 4, ...，這個寫法的優點是讀取資料時索引值比較好寫，缺點是會浪費接近一半的二維串列空間。
2. 用動態規畫計算從左到右切割到每一格時最小的累積損失量，取這一格的左上、左側、左下之中的最小值，再加上這格原來的值。
3. 為了避免檢查邊界值要寫一堆 if，我選擇在四周 (C++) 或是最右側、最下方 (Python) 加上正無窮大的值當作哨兵，缺點是要多花一點記憶體。

經過測試，這個寫法在目前通過測試的人當中，C++ 及 Python 使用的時間都最短，可能其他人都很認真地檢查是否出界吧！

Python 程式碼

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

import sys

oo = float('inf')
for line in sys.stdin:
    H, W = map(int, line.split())  # 晶格的高與寬
    grid = [[-1]*(2*W+2) for _ in range(H)]  # 晶格 (H+1)*(2*W+2)
    grid.append([oo]*(2*W+2))  # 最下方補一列 oo
    for r in range(H):  # 讀取 H 行資料
        row = list(map(int, input().split()))
        if r%2 == 0:  # 如果是偶數列，欄位為 1, 3, 5, ..., 2*W - 1
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i+1] = v
            grid[r][2*W] = grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
        else:  # 如果是奇數列，欄位為 0, 2, 4, ..., 2*W
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i] = v
            grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
    # 動態規畫，grid[r][c] 改成到這格損失的值，加上左上、左側、左下最小值
    for c in range(2, 2*W+1):  # 依序掃過第 2 ~ 2*W 欄
        if c%2 == 0:  # 如果是偶數欄，列為 1, 3, 5, ...
            for r in range(1, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
        else:  # 如果是奇數欄，列為 0, 2, 4, ...
            for r in range(0, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
    # 找出答案，在每一列的最後一格，不含 oo
    ans = oo  # 答案預設為最大值
    for r in range(H):  # 依序掃過每一列
        if r%2 == 0: ans = min(ans, grid[r][2*W-1])  # 如果是偶數列
        else: ans = min(ans, grid[r][2*W])   # 如果是奇數列
    print(ans)

ZeroJudge 解題筆記：k930. P7. 興建圍籬 (Fence)

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



ZeroJudge 題目連結：k930. P7. 興建圍籬 (Fence)

解題想法

這題我用 BFS，但是在 Python 不論是用 deque 或 list 都太慢，在 C++ 用 queue 或 vector 都要跑 0.1 s。

Python 程式碼

寫法1，用 deque 儲存待走訪的佇列，但是速度不夠快，只能通過 60% 的測資。

import sys
from collections import deque

for line in sys.stdin:
    H, W = map(int, line.split())  # 地圖 H*W
    grid = [list(map(int, input().split())) for _ in range(H)]  # 讀取地圖
    num = 1  # 花地編號
    ans = []  # 答案
    for i in range(H):  # 依序掃過每一格
        for j in range(W):
            if grid[i][j] == 1:  # 如果此格是花地
                tot = 0  # 這區的圍籬數量
                que = deque([(i, j)])  # 待走訪的佇列
                num += 1  # 編號加 1
                while que:  # 如果 que 還有資料繼續執行
                    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
                    grid[r][c] = num  # 設定 grid[r][c] 的編號
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                        nr, nc = r+dr, c+dc  # 要檢查的格子 (nr, nc)
                        if 0 <= nr < H and 0 <= nc < W:  # 如果 nr, nc 沒有出界
                            if grid[nr][nc] == 1:  # 如果是還沒有編號的花地
                                grid[nr][nc] = num  # 設定編號
                                que.append((nr, nc))  # (nr, nc) 加入 que
                            elif grid[nr][nc] == 0:  # 如果是空地
                                tot += 1  # (r, c) 需要加一片圍籬
                ans.append(tot)  # 將 tot 加入 ans
    print(*sorted(ans))  # 將 ans 排序後印出

ZeroJudge 解題筆記：k926. P3. 錯字校正 (Correction)

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



ZeroJudge 題目連結：k926. P3. 錯字校正 (Correction)

解題想法

這題測資不大，按照題目的要求模擬替換字母的過程，最後再計算原來的字串與替換後的字串不同的字母數量即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = list(line.strip())  # 輸入的字串
    t = list(input().strip())  # 正確的字串
    n = int(input())  # 修正次數
    for _ in range(n):  # 讀取 n 行修正資料
        x, y = list(input().split())  # x 替換成 y
        for i in range(len(s)):  # 依序由 s 讀取字元
            if s[i] == x: s[i] = y  # 如果 s[i] 是 x 則換成 y
    diff = sum([a != b for a, b in zip(s, t)])  # 計算 s, t 之中對應位置不相同的字母數量
    print(diff)

ZeroJudge 解題筆記：k925. P2. 海底探險 (Adventure)

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



ZeroJudge 題目連結：k925. P2. 海底探險 (Adventure)

解題想法

這題我沒有想到比較簡潔的寫法，只能按照題目的敘述模擬烏龜的運動過程，程式碼寫起來很長。

Python 程式碼

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

import sys

def solve(L, T, hs):
    rem = T-1  # 剩下的探索時間，先減 1
    hmax = max(hs)  # 最高區塊高度
    imax = hs.index(hmax)  # 最高區塊位置
    t1 = hmax - hs[0]  # 上升到最高區塊高度需要的時間
    rem -= t1  # 更新 rem
    if rem <= 0: return 1  # 已經用完探索時間，還在起點區塊，回傳 1
    t2 = imax  # 向右游到最高區塊需要的時間
    rem -= t2  # 更新 rem
    if rem <= 0: return T-t1  # 向右游到的區塊 T-1-t1+1
    if imax == L-1:  # 如果游到最右邊
        hmin = min(hs[1:L-1])  # hs[1] ~ hs[L-2] 最低點
        imin = L-2 - hs[1:L-1][::-1].index(hmin)  # hs[1] ~ hs[L-2] 最低點位置
        t3 = L-1-imin  # 向左游到 imin 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return L-(rem+t3)  # 游到區塊 2 前時間就到了
        return imin + 1  # 可以游到區塊 imin + 1
    else:  # 不是游到最右邊
        hmax2 = max(hs[imax+1:])  # imax 右側最高的區塊高度
        imax2 = hs[imax+1:].index(hmax2) + imax + 1  # hmax2 的位置
        t3 = imax2-imax  # 向右游到 imin2 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return imax+rem+t3+1  # 游到 imax2 + 1 前時間就到了
        return imax2 + 1  # 可以游到 imax2 + 1

for line in sys.stdin:
    L = int(line)  # L 個區塊
    hs = list(map(int, input().split()))  # 各區塊高度
    T = int(input())  # 探索時間
    print(solve(L, T, hs))

ZeroJudge 解題筆記：k924. P1. 數字結合 (Combination)

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



ZeroJudge 題目連結：k924. P1. 數字結合 (Combination)

解題想法

先將兩個字串合併，再計算奇數位數和、偶數位數和，如果兩者的差是 11 的倍數印出 Yes，反之印出 No。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = "".join(line.split())  # 兩個整數合併
    odd, even = 0, 0  # 奇數位數和，偶數位數和
    for i, c in enumerate(s):  # 計算奇數位數和、偶數位數和
        if i%2 == 1: odd += int(c)
        else: even += int(c)
    dif = abs(odd - even)
    print("Yes" if dif%11 == 0 else "No")

ZeroJudge 解題筆記：k866. 8.運送隕石 (Delivery)

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



ZeroJudge 題目連結：k866. 8.運送隕石 (Delivery)

解題想法

我用 priority queue 儲存隕石重量，每次處理最重的隕石，將重量除以 2 之後再放回 priority queue 之中，處理 m 次之後，priority queue 最上面的資料就是答案。

Python 程式碼

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

import sys, math, heapq

for line in sys.stdin:
    n, m = map(int, line.split())  # n 顆隕石，m 顆炸彈
    ws = []  # 每顆隕石的重量，為了將最大值放上面，要加負號
    for w in map(int, input().split()): heapq.heappush(ws, -w)
    for _ in range(m):  # 執行 m 次
        w = -heapq.heappop(ws)  # 取出最大值
        h = w/2  # 除以2
        heapq.heappush(ws, -h)  # 加入兩個 -h
        heapq.heappush(ws, -h)
    print(math.ceil(-ws[0]))

ZeroJudge 解題筆記：k865. 7.幼稚園 (Kindergarten)

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



ZeroJudge 題目連結：k865. 7.幼稚園 (Kindergarten)

解題想法

我是用兩層的 for 迴圈，先讀取第 i 個人的身高 h，裡面再用兩個 for 迴圈，分別向左、向右找較高的人，取向左、向右交換次數較少者。這樣的寫法效率不夠高，Python 過不了，C++ 可以通過測試。

Python 程式碼

速度太慢，只能通過 40% 的測資，需要再找到更有效率的寫法。

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    hs = list(map(int, input().split()))  # 身高
    ans = 0  # 交換次數
    for i, h in enumerate(hs):  # 讀取第 i 個人的身高 h
        toleft = 0  # 向左找較高的人數
        for j in range(i-1, -1, -1):
            if hs[j] > h: toleft += 1
        toright = 0  # 向右找較高的人數
        for j in range(i+1, n):
            if hs[j] > h: toright += 1
        if toleft <= toright: ans += toleft  # 取向左、向右交換次數較少者
        else: ans += toright
    print(ans)

ZeroJudge 解題筆記：k854. P8.簡易數織 (Nonogram)

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



ZeroJudge 題目連結：k854. P8.簡易數織 (Nonogram)

解題想法

這題我試著用 dp 計算可能的組合，但是最後一筆測資極大，用 Python 最後一筆測資超時。後來我把題目丢到 Gemini 2.0 Flash，它提供了一個數學化的解法，才能在時限內順利解出來。

Python 程式碼

最後一筆測資超時。

import sys

def solve(w, n, arr):
    mod = 10**9 + 7  # 要取餘數用的整數
    imin = sum(arr) + n - 1  # 黑色區塊總和 + 至少需要的空格數量
    if imin > w:  # 需要的格子數大於 w
        print(0); return  # 印出 0，跳出函式
    dp = [[0]*(n+1) for _ in range(w+1)]  # dp[i][j] 填到第 i 格時放入第 j 段黑色區塊
    for i in range(w+1): dp[i][0] = 1  # 初始化，填滿 0 ~ w 格、沒有黑色區塊，只有一種方式
    for i in range(1, w+1):  # 填滿 1 ~ w 格
        for j in range(1, n+1):  # 放入第 j 段黑色區塊
            block = arr[j-1]  # 黑色區塊長度
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod  # 不放這個黑色區塊
            if i >= block:  # 可以放入這個黑色區塊
                if j == 1:  # 第 1 個黑色區塊，前面可以不需要是空格
                    dp[i][j] = (dp[i][j] + dp[i-block][j-1]) % mod
                elif i >= block+1:  # 不是第 1 個黑色區塊，前面必須是空格
                    dp[i][j] = (dp[i][j] + dp[i-block-1][j-1]) % mod
    print(dp[w][n]); return

for line in sys.stdin:
    w, n = map(int, line.split())  # w 個格子，n 段連續的黑色區塊
    arr = list(map(int, input().split()))  # 各段連續黑色區塊的長度
    solve(w, n, arr)

ZeroJudge 解題筆記：l919. P.2 珠寶交易 (Jewel)

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



ZeroJudge 題目連結：l919. P.2 珠寶交易 (Jewel)

解題想法

這題理論上用貪心法就能解，有通過範例測資，但是無法送出解答。

Python 程式碼

無法送出解答。

import sys

for line in sys.stdin:
    n = int(line)  # n 天
    buy = float('inf')  # 最低買價，預設為正無窮大
    profit = 0  # 最大利潤，預設為 0
    best_buy_dat, best_sell_day = 0, 0  # 最佳買入、𧶠出時機
    buy_day = 0  # 買入時機
    for i, p in enumerate(map(int, input().split()), start=1):  # 第 i 天，價格 p
        if p < buy:  # 如果當天的價格小於 buy，更新 buy 及 buy_day
            buy = p; buy_day = i
        elif p - buy > profit:  # 價差大於 profit
            profit = p - buy  # 更新 profit
            best_sell_day = i  # 更新 sell_day
            best_buy_day = buy_day  # 更新 best_buy_day
    if profit > 0: print(best_buy_day, best_sell_day)
    else: print(-1)

ZeroJudge 解題筆記：k853. P7.直播趕場 (Live)

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



ZeroJudge 題目連結：k853. P7.直播趕場 (Live)

解題想法

採用類似〈APCS實作題2016年3月第3題：線段覆蓋長度〉計算重疊線段厚度的寫法，讀到開始直播時刻厚度加 1，讀到直播結束時刻厚度減 1；假設目前檢查的時間端點為 [start, end+1]，若厚度小於等於螢幕數量，可以觀看的時數加上厚度乘以端點距離，若厚度大於螢幕數量，可以觀看的時數加上螢幕數量乘以端點距離。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, s = map(int, line.split())  # n 個螢幕，s 個直播
    cast = []  # 直播開始、結束時刻，開始厚度加 1，結束厚度減 1
    for _ in range(s):  # 讀取 s 行資料
        start, end = map(int, input().split())
        cast += [(start, 1), (end+1, -1)]  # 結束時刻要加 1
    cast.sort()  # 排序
    last = 0  # 正在檢查的範圍開始時刻
    thick = 0  # 厚度，正在直播的頻道數量
    ans = 0  # 答案，可以觀看的直播總時數
    for p, t in cast:  # 依序讀取時刻及厚度變化
        if thick > 0:  # 如果目前直播頻道數量大於 0
            ans += min(thick, n)*(p-last)  # 更新 ans，加上 thick, n 較小值乘以 p-last
        thick += t  # 更新厚度
        last = p  # 更新 last
    print(ans)

ZeroJudge 解題筆記：k851. P5.辨識碼 (Identification)

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



ZeroJudge 題目連結：k851. P5.辨識碼 (Identification)

解題想法

我是用字串分割的方式，按照題目要求的長度分割字串，將每個子字串的數字加總存入集合 isum 之中，如果 isum 之中已經有同樣的值就是國民，不需要再檢查後面的子字串。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)  # 分組數字 x 個
    n = sys.stdin.readline().strip()  # 身分證號
    m = len(n)  # 長度
    isum = set()  # 各組的加總
    flag = False  # 是否為國民，預設為 False
    for i in range(m-x, -1, -x):  # 從最後往前取長度為 x 的子字串
        s = n[i:i+x]  # 子字串
        tot = sum([int(c) for c in s])  # 加總
        if tot in isum:  # 如果 isum 之中已經有 tot
            flag = True; break  # 是國民，中止迴圈
        isum.add(tot)  # tot 加入 isum
    print("Yes" if flag else "No")  # 印出答案

ZeroJudge 解題筆記：k849. P3.骨牌 (Domino)

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



ZeroJudge 題目連結：k849. P3.骨牌 (Domino)

解題想法

這題是有向圖，我用集合 child 儲存子節點編號，用字典 nxt 儲存每個節點的子節點編號，讀取 n 行資料存入 child 及 nxt，再掃瞄一輪找出根節點（第一張牌），最後用一個 while 迴圈第根節點開始掃過所有的節點並將節點編號存入串列 ans。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 組資料，n 張牌
    child = set()  # 不是第一張牌的編號
    nxt = dict()  # 下一張牌的編號
    for _ in range(n):  # 讀取 n 行資料，u 的下一張是 v
        u, v = map(int, input().split())
        child.add(v)
        nxt[u] = v
    start = 0  # 第一張牌
    for u in nxt.keys():  # 從 nxt 的 keys 之中找第一張牌
        if u not in child:  # 只有一個 u 不在 child 之中
            start = u; break  # 找到就可以中止迴圈
    ans = [start]  # 先將 start 加入 ans
    while nxt[ans[-1]] != -1:  # 如果 ans 最後一項的下一張不是 -1 繼續執行
        ans.append(nxt[ans[-1]])  # 將找到的牌加入 ans
    print(*ans)

ZeroJudge 解題筆記：k848. P2.卡牌評分 (Card)

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



ZeroJudge 題目連結：k848. P2.卡牌評分 (Card)

解題想法

分成兩個部分，先掃過全部的卡牌資料並找最大值，再掃一輪計算每張牌的積分。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 張卡牌
    S, A, D, H = [0]*n, [0]*n, [0]*n, [0]*n  # 積分，攻擊力，防禦力，生命力
    amax, dmax, hmax = 0, 0, 0  # 最高攻擊力，最高防禦力，最高生命力
    for i in range(n):  # 讀取 n 張牌的資料並找最大值
        a, d, h = map(int, input().split())
        A[i] = a; amax = max(amax, a)
        D[i] = d; dmax = max(dmax, d)
        H[i] = h; hmax = max(hmax, h)
    for i in range(n):  # 計算每張牌的積分
        if A[i] == amax: S[i] += 1
        if D[i] == dmax: S[i] += 1
        if H[i] == hmax: S[i] += 1
    print(S.index(max(S)) + 1)  # 印出最高積分卡牌編號

ZeroJudge 解題筆記：k847. P1.租車費用 (Rent)

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



ZeroJudge 題目連結：k847. P1.租車費用 (Rent)

解題想法

按照題目的計費規則寫就行了，先算租車天數，分成每租滿 10 天以及未滿 10 天兩個部分計費。

Python 程式碼

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

import sys

month = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = sum(month[m1: m2]) - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)

月份的天數改成前綴和，如果輸入的月份是 $m1, m2$，要算計算 $m2-1$ 到 $m1$ 月份的天數 $psum[m2-1] - psum[m1-1]$。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

import sys

psum = (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = psum[m2-1] - psum[m1-1] - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)

ZeroJudge 解題筆記：k520. P8.幸運基數 (Base)

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



ZeroJudge 題目連結：k520. P8.幸運基數 (Base)

解題想法

我在這題卡了很久，一直想不出比較有效率的寫法。由題目的敘述可知，如果要把10進位制的數字 $n$ 換成 $k$ 進位制表示，而且轉換後每個位數都是 $1$，一定會有的解是 $k = n-1$，轉換後為 $11$，如果 $k$ 越小，轉換後的位數越多。我有試著把 $3 \leq n \leq 1000$ 之中 $k \neq n-1$ 的數字列出來，但看不出規律。

(7, 2), (13, 3), (15, 2), (21, 4), (31, 2), (31, 5), (40, 3), (43, 6), (57, 7), (63, 2),
(73, 8), (85, 4), (91, 9), (111, 10), (121, 3), (127, 2), (133, 11), (156, 5), (157, 12), (183, 13), 
(211, 14), (241, 15), (255, 2), (259, 6), (273, 16), (307, 17), (341, 4), (343, 18), (364, 3), (381, 19),
(400, 7), (421, 20), (463, 21), (507, 22), (511, 2), (553, 23), (585, 8), (601, 24), (651, 25), (703, 26),
(757, 27), (781, 5), (813, 28), (820, 9), (871, 29), (931, 30), (993, 31)

後來想到，如果 $k$ 越小，轉換後的位數越多，那就先算出 2 進位制的位數，然後位置依序遞減到 2 為止，每次再用二分搜尋法，在 $low = 2, high = n-1$ 之間找解，雖然有很多次不必要的計算，但至少能正確地找到答案。

Python 程式碼

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

import sys, math

# 檢查以 base 為底，在指定位數 digit 的值與 num 的大小關係
def check(num, base, digit):
    power, total = 1, 0  # 目前的次方，加總
    for i in range(digit):  # 從個位數開始往左計算 
        total += power  # 更新 total
        power *= base  # 更新 power 為 base**(i+1)
        if total > num: return 1  # 如果 total 大於 num，回傳 1，跳出函式
    if total == num: return 0  # 如果最後 total 等於 num，回傳 0
    return -1  # 否則回傳 -1

for line in sys.stdin:
    n = int(line)  # 要找基底的數字 n
    ans = n-1  # 答案預設為 n-1
    digitmax = math.ceil(math.log(n, 2))  # 最多的位數
    for digit in range(digitmax, 1, -1):  # 依序檢查最多位數到 2 位數
        low, high = 2, n-1  # 下限 2，上限 n-1
        while low <= high:  # 當 low 小於等於 high，繼續執行
            mid = (high - low)//2 + low  # 取中間值
            state = check(n, mid, digit)  # 呼叫 check 檢查大小關係
            if state == 0:  # 找到解，更新 ans 為較小的值，降低 high
                ans = min(ans, mid); high = mid-1
            elif state == 1: high = mid-1 # mid 太大，降低 hight
            else: low = mid+1  # mid 太小，提高 low
    print(ans)  # 印出答案

ZeroJudge 解題筆記：k519. P7.機票 (Ticket)

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



ZeroJudge 題目連結：k519. P7.機票 (Ticket)

解題想法

這題考 Floyd-Warshall 演算法。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個城市
    graph = [list(map(int, input().split())) for _ in range(n)]  # 讀取城市之前移動費用
    start, end = map(int, input().split())  # 起點、終點
    start -=1; end -= 1  # 配合索引值減 1
    for k in range(n):  # 以 k 為轉機地點
        for i in range(n):  # 以 i 為起點
            for j in range(n):  # 以 j 為終點
                if graph[i][k] == -1 or graph[k][j] == -1: continue  # k 等於 i 或 j，找下一組
                if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j] - 50:  # 如果 i 等於 j 或 i->j 成本大於 i->k->j -50
                    graph[i][j] = graph[i][k] + graph[k][j] - 50
    print(graph[start][end])  # 印出答案

ZeroJudge 解題筆記：k518. P6.蛋糕切塊 (Cake)

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



ZeroJudge 題目連結：k518. P6.蛋糕切塊 (Cake)

解題想法

這題考動態規畫，我同時利用 set 儲存可用的子字串，這樣程式運作速度會比較快。

Python 程式碼

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

import sys

def can_cut_cake(s, cuts):
    n = len(s)  # 字串長度
    dp = [False]*(n+1)  # 是否能走到 i，如果能走到 i+1 代表有解
    dp[0] = True  # 一定能走到開頭
    # 動態規劃遍歷
    for i in range(1, n+1):  # 依序找終點 i = 1 ~ n
        for j in range(i):  # 依序找起點 j = 0 ~ i-1
            if dp[j] and s[j:i] in cuts:  # 如果能走到 j 而且 s[j:i] 在 cuts 之中
                dp[i] = True  # 可以走到 i
                break  # 只要找到一個可行切割後就可以停止
    print("yes" if dp[n] else "no")  # 如果 dp[n] 為 True 印出 yes，反之印出 no

for s in sys.stdin:
    s = s.strip()  # 要檢查的字串
    m = int(input())  # 可用的子字串數量
    cuts = set()  # 可用的子字串
    for _ in range(m): cuts.add(input())  
    can_cut_cake(s, cuts)  # 計算並輸出結果

ZeroJudge 解題筆記：k517. P5.波動 (Wave)

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



ZeroJudge 題目連結：k517. P5.波動 (Wave)

解題想法

因為這題需要將所有的波依照傳播的時間由小到大排序，如果時間相同再依照方向 W、S、E、N 排序。如果將時間、方向組成 Python 的 tuple 或是 C++ 的 pair 再排序，但由於 W、S、E、N 不是依照字典順序，不能這樣處理。所以我先將 W、S、E、N 換成對應的數字 0、1、2、3，與時間組成 tuple 再排序，輸出結果時再將數字換回 W、S、E、N。在 C++ 則是自訂結構體，再用 lambda function 自訂排序規則。

Python 程式碼

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

import sys

c2n = {'W': 0, 'S': 1, 'E': 2, 'N': 3}
n2c = ('W', 'S', 'E', 'N')
for line in sys.stdin:
    p = int(line)  # p 道波動
    wave = []  # 傳播時間，波源方位
    for _ in range(p):  # 執行 p 次
        c, d, v = input().split()  # 波源方位，距離，波速
        d = int(d); v = int(v)  # 轉成 int
        wave.append((d/v, c2n[c]))  # (d/v, c2n[c]) 加入 wave
    wave.sort()  # 依照 (t, 方向) 由小到大排序
    print("".join([n2c[n] for _, n in wave]))  # 由 wave 取出 n，換成對應的字母，接成字串，印出

ZeroJudge 解題筆記：k516. P4.根號 (Sqrt)

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



ZeroJudge 題目連結：k516. P4.根號 (Sqrt)

解題想法

畫圖形的題目，關鍵在於找到各部位畫圖的規則。

Python 程式碼

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

import sys

for line in sys.stdin:
    k = int(line.strip())  # 短邊長度
    a, b = (k-1)//2 - 1, 2*k-1  # 左斜線、長邊長度
    n, h = k+a+k+b, k//2  # 全長，短邊於第 h 列
    grid = [[" "]*n for _ in range(k)]  # 圖形，預設為空白
    for i in range(k): grid[h][i] = "*"  # 短邊
    for i in range(a): grid[h+1+i][k+i] = "*"  # 左斜線
    for i in range(k): grid[k-1-i][k+a+i] = "*"  # 右斜線
    for i in range(2*k-1): grid[0][k+a+k+i] = "*"  # 長邊
    for i in range(k): print("".join(grid[i]))  # 印出圖形

ZeroJudge 解題筆記：k515. P3.標題 (Title)

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



ZeroJudge 題目連結：k515. P3.標題 (Title)

解題想法

我先將所有要小寫的冠詞、介系詞、連接詞存入一個陣列或集合中，並將讀進來的字串全部轉成小寫字母存入陣列，由陣列依序讀取每個單字，如果是整行的開頭或結束則將開頭字母大寫；如果是中間的單字，再檢查這個單字是否為冠詞、介系詞、連接詞，如果不是，則將開頭字母改成大寫。

Python 程式碼

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

import sys

article = ("the", "a", "an", "in", "on",
           "at", "of", "for", "by", "to",
           "and", "or", "but")  # 冠詞、介系詞、連接詞
for line in sys.stdin:
    word = line.lower().split()  # 全部轉成小寫，用空格分隔，存成串列
    n = len(word)  # 單字數量
    for i in range(n):  # 依序讀取單字
        if i == 0 or i == n-1:  # 開頭或結尾
            word[i] = word[i][0].upper() + word[i][1:]
        elif word[i] not in article:  # 如果不是開頭或結尾，且 word[i] 不在 article 之中
                word[i] = word[i][0].upper() + word[i][1:]
    print(*word)

ZeroJudge 解題筆記：k514. P2.解藥 (Medicine)

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



ZeroJudge 題目連結：k514. P2.解藥 (Medicine)

解題想法

每組測資只有單筆。先找最小的比例數值，以這種材料的量為基準，檢查外三項材料的比例。

Python 程式碼

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

import sys

for line in sys.stdin:
    ratio = list(map(int, line.split()))  # 4 㮔材料的比例
    imin = min(ratio)  # 最小的比例數值
    pmin = ratio.index(imin)  # 最小的比例索引值
    n = int(input())  # 每種材料各有 n 小包
    abcd = [list(map(int, input().split())) for _ in range(4)]  # 每小包的份量
    solve = False  # 是否有解
    if pmin == 0:  # 以第 0 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 0 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[1] in abcd[1] and v*ratio[2] in abcd[2] and v*ratio[3] in abcd[3]:
                print(f"{v:d} {v*ratio[1]:d} {v*ratio[2]:d} {v*ratio[3]:d}")
                solve = True; break
    elif pmin == 1:  # 以第 1 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 1 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[0] in abcd[0] and v*ratio[2] in abcd[2] and v*ratio[3] in abcd[3]:
                print(f"{v*ratio[0]:d} {v:d} {v*ratio[2]:d} {v*ratio[3]:d}")
                solve = True; break
    elif pmin == 2:  # 以第 2 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 2 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[0] in abcd[0] and v*ratio[1] in abcd[1] and v*ratio[3] in abcd[3]:
                print(f"{v*ratio[0]:d} {v*ratio[1]:d} {v:d} {v*ratio[3]:d}")
                solve = True; break
    else:  # 以第 3 種材料為基準
        for v in abcd[pmin]:  # 依序讀取第 3 種材料每小包的分量，檢查另外 3 項材料的比例
            if v*ratio[0] in abcd[0] and v*ratio[1] in abcd[1] and v*ratio[2] in abcd[2]:
                print(f"{v*ratio[0]:d} {v*ratio[1]:d} {v*ratio[2]:d} {v:d}")
                solve = True; break
    if not solve: print(-1)  # 無解，印出 -1

ZeroJudge 解題筆記：k513. P1.停車場 (Parking)

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



ZeroJudge 題目連結：k513. P1.停車場 (Parking)

解題想法

寫比較式的時候，從比較嚴格的條件開始寫，依序檢查是否能停在小停車格，如果不行才再檢查是否能停在中停車格，如果還是不行才再檢查是否能停在大停車格。

Python 程式碼

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

S, M, L = map(int, input().split())  # 小、中、大停車格數量
N = int(input())  # N 輛車
cars = sorted(list(map(int, input().split())))  # 車的大小，由小到大排序
tot = 0  # 可停的車子數量
for car in cars:  # 依序讀取車的大小
    if 1 <= car <= 199:  # 可以停在小停車格
        if S > 0:  # 如果小停車格有剩
            S -= 1; tot += 1
        elif M > 0:  # 如果沒有小停車格，改停中停車格
            M -= 1; tot += 1
        elif L > 0:  # 如果也沒有中停車格，改停大停車格
            L -= 1; tot += 1
    elif 200 <= car <= 499:  # 可以停在中停車格
        if M > 0:  # 如果中停車格有剩
            M -= 1; tot += 1
        elif L > 0:  # 如果沒有中停車格，改停大停車格
            L -= 1; tot += 1
    elif car >= 500 and L > 0:  # 可以停在大停車格
        L -= 1; tot += 1
    else: break  # 其它狀況，沒有停車格了，中止迴圈
print(tot)

ZeroJudge 解題筆記：k468. 打靶 (Target)

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



ZeroJudge 題目連結：k468. 打靶 (Target)

解題想法

我是用字典及 deque 儲存各類型的靶的位置，如果已經打掉就移除資料。

Python 程式碼

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

import sys
from collections import defaultdict, deque

for line in sys.stdin:
    n, s, f = map(int, line.split())  # n 個靶，要打第 s 個 f 類型標靶
    target = list(map(int, input().split()))  # 各位置標靶類型
    state = [True]*n  # 標靶是否還在
    pos = defaultdict(deque)  # 各類型標靶的位置
    for i, t in enumerate(target): pos[t].append(i)
    idx, cnt, hit = 0, 0, 0  # 目前要打的靶位置，射擊次數，打到目標類型標靶數量
    while idx < n:  # 當 idx 還沒有出界
        while not state[idx]: idx += 1  # 如果這個靶已經打掉，找下一個靶
        cnt += 1  # 射擊次數加 1
        now = target[idx]  # 目前打的標靶類型
        state[idx] = False  # 已打掉
        if now == f: hit += 1  # 打到 f 類型標靶，hit 加 1
        pos[now].popleft()  # 移除 now 對應的左側標靶位置
        if pos[now]:  # 如果 now 類型還有標靶
            state[pos[now].popleft()] = False  # 再移除最左側標靶位置，已打掉
            if now == f: hit += 1  # 打到 f 類型標靶，hit 加 1
        if hit >= s:  # 如果已打掉至少 s 個 f 類型標靶
            print(cnt); break  # 印出 cnt，中止迴圈

ZeroJudge 解題筆記：k467. 分班 (Class)

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



ZeroJudge 題目連結：k467. 分班 (Class)

解題想法

這題要同時比較同一個人的語文及數理成績，在 Python 可以用 zip 將兩行資料合併再一起輸出，在 C++ 則可以先儲存語文成績在一個陣列之中，再依序讀取每個人的數理成績，不需要儲存，可以少用一點記憶體。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    lan, sci = [], []  # 語文班、數理班座號
    # 讀取兩行資料，用 zip 綁在一起輸出，兩個分數 a, b，編號從 1 開始，
    for i, (a, b) in enumerate(zip(map(int, input().split()), map(int, input().split())), start=1):
        if a > b: lan.append(i)  # a 大，i 加入 lan
        else: sci.append(i)  # b 大，i 加入 sci
    if lan: print(*lan)
    else: print(-1)
    if sci: print(*sci)
    else: print(-1)

ZeroJudge 解題筆記：k466. 成績分析 (Analysis)

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



ZeroJudge 題目連結：k466. 成績分析 (Analysis)

解題想法

依序比較每個人的分數變化即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 個人，m 個分數
    improve, drop = 0, 0  # 進步、退步名單
    imax, dmax = 0, 0  # 進步、退步分數最大值
    for i in range(1, n+1):  # 讀取座號 1 ~ n
        score = list(map(int, input().split()))  # 分數
        im, dm = 0, 0  # 這個人進步（正值）、退步的分數（負值）
        for j in range(1, m):  # 比較 score[j] - score[j-1]
            im += max(score[j] - score[j-1], 0)  # 取分差及 0 較大者加到 im
            dm += min(score[j] - score[j-1], 0)  # 取分差及 0 較小者加到 im
        if im > imax: improve = i; imax = im  # im 較大，更新 improve, imax
        if -dm > dmax: drop = i; dmax = -dm  # -dm 較大，更新 drop, dmax
    print(improve); print(drop)  # 印出答案

ZeroJudge 解題筆記：k399. 取貨 (Pickup)

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



ZeroJudge 題目連結：k399. 取貨 (Pickup)

解題想法

這題用排序工具及 Python 的 tuple 或是 C++ 的 pair 會比較好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    cnt = dict()  # 記錄每個人最後一次登記的編號
    for i, c in enumerate(line.strip()): cnt[c] = i
    order = sorted([(v, k) for k, v in cnt.items()])  # 依照編號排序
    ans = sorted([(k, i) for i, (_, k) in enumerate(order, start=1)])  # 依照人的代號排序
    print("".join([str(i) for _, i in ans]))  # 將每個人對應的序號接成字串印出

ZeroJudge 解題筆記：k398. 密室逃脫 (Escape)

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



ZeroJudge 題目連結：k398. 密室逃脫 (Escape)

解題想法

這題用 BFS 並且在地圖邊緣加一圈不能通過的符號作為哨兵，省略檢查邊界值的判斷式，程式碼會比較好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 地圖 m*n
    step = input().strip()  # 移動步數
    grid = [list('.'*n) + ['#'] for _ in range(m)]  # 地圖，先填入 .，最後加入 # 當作哨兵
    grid.append(list('#'*(n+1)))  # 最後加上 n+1 個 # 當作哨兵
    d = 0  # 方向 0 ~ 3，依序為右、下、左、上
    dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)  # 移動格數
    r, c = 0, 0  # 起點在左上角
    grid[0][0] = '*'  # 起點改成 *
    for s in step:  # 依序讀取移動步數
        s = int(s)  # 轉成整數
        for _ in range(s):  # 走 s 格
            nr, nc = r+dr[d], c+dc[d]  # 要走的格子
            if grid[nr][nc] == '#': break  # 如果走到 #，出界，停在原地
            grid[nr][nc] = '*'  # 走過的格子改成 *
            r, c = nr, nc  # 更新 r, c
        d = (d+1)%4  # 修改方向
    for row in grid[:-1]:  # 印出地圖，不包含最後一列
        print("".join(row[:-1]))  # 不包含最後一格，組成字串再印出

ZeroJudge 解題筆記：k397. 會議安排 (Meeting)

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



ZeroJudge 題目連結：k397. 會議安排 (Meeting)

解題想法

解題時要注意，測資中某些時段會相連，例如輸入範例 4 的 [72, 147] 及 [147, 161]，要合併為 [72, 161]。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 兩個人有空的時段數量
    a, b = [], []  # 阿明、阿文有空的時段
    for _ in range(n):  # 讀取 n 行資料
        s, e = map(int, input().split())  # 開始、結束時間 [s, e]
        if a and s == a[-1][1]: a[-1][1] = e  # 如果 a 有資料而且 s 等於最後一個結束時間，更新為 e
        else: a.append([s, e])  # 否則將 [s, e] 加入 a
    for _ in range(m):  # 讀取 m 行資料
        s, e = map(int, input().split())  # 開始、結束時間 [s, e]
        if b and s == b[-1][1]: b[-1][1] = e  # 如果 b 有資料而且 s 等於最後一個結束時間，更新為 e
        else: b.append([s, e])  # 否則將 [s, e] 加入 b
    d = int(input())  # 需要的時間長度
    n, m = len(a), len(b)  # 更新 n, m
    i, j, can = 0, 0, False  # 從 a, b 讀取資料的索引值，是否有解
    while i < n and j < m:  # 當 i, j 都還沒有出界
        if a[i][1] < b[j][0]: i += 1  # a 的結束時間小於 b 的開始時間，i 加 1
        elif b[j][1] < a[i][0]: j += 1  # b 的結束時間小於 a 的開始時間，j 加 1
        elif a[i][0] <= b[j][0] <= a[i][1] or b[j][0] <= a[i][0] <= b[j][1]:  # a, b 有交集
            s, e = max(a[i][0], b[j][0]), min(a[i][1], b[j][1])  # 開始時間取大的，結束時間取小的
            if e - s >= d:  # 如果交集時間夠長，印出 s, s+d，有解，中止迴圈
                print(s, s+d); can = True; break
            if a[i][1] <= b[j][1]: i += 1  # 如果 a 的結束時間較早，i 加 1
            else: j += 1  # 反之，j 加 1
    if not can: print(-1)  # 如果無解，印出 -1

ZeroJudge 解題筆記：k255. 鑿井取水 (Water)

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



ZeroJudge 題目連結：k255. 鑿井取水 (Water)

解題想法

解題時要注意，水量為 0 不算枯竭。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, w = map(int, line.split())  # n 天，每天産生 w 單位的水
    tot = 0  # 水量
    dry = False  # 是否已經枯竭
    for i in range(1, n+1):  # 檢查第 1 ~ n 天
        used = sum(list(map(int, input().split()))[1:])  # 用水量
        tot = tot + w - used  # 更新水量
        if not dry and tot < 0:
            print(i); dry = True
    if not dry: print(-1)

ZeroJudge 解題筆記：k254. 拍七 (Seven)

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



ZeroJudge 題目連結：k254. 拍七 (Seven)

解題想法

將整數轉成字串，在檢查字串中是否有指定的數字時會比較方便。

Python 程式碼

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

import sys

for line in sys.stdin:
    s, e, b, k = map(int, line.split())
    cnt = 0  # 拍手次數
    for i in range(s, e+1):  # 依序檢測 s ~ e
        if i%b == 0 or str(b) in str(i): cnt += 1  # i 轉成字串檢查之中是否有 b
        if cnt == k:
            print(i); break
    if cnt < k: print(-1)

ZeroJudge 解題筆記：k253. 庫存清理 (Stock)

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



ZeroJudge 題目連結：k253. 庫存清理 (Stock)

解題想法

有比較簡單、直接但行數很多的寫法，也可以用 for 迴圈合併重複的部分。

Python 程式碼

簡單直接但是行數很多的寫法，使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    t, s, p = map(int, line.split())  # 商品初始數量、來店顧客數、商品單價
    d = t//5  # 1/5 的商品數量
    tot = 0  # 總金額
    while t >= d and s > 0:  # 還有可販售商品，還有顧客
        if t >= 4*d:  # 商品數量大於等於 4*d
            if s <= d+1:  # 人數小於等於 d+1
                tot += s*(p*5//10); s = 0; t -= s
            else:  # 人數大於 d+1
                tot += (d+1)*(p*5//10); s -= d+1; t -= d+1
        elif t >= 3*d:  # 商品數量大於等於 3*d
            if s <= d:  # 人數小於等於 d
                tot += s*(p*6//10); s = 0; t -= s
            else:  # 人數大於 d
                tot += d*(p*6//10); s -= d; t -= d
        elif t >= 2*d:  # 商品數量大於等於 2*d
            if s <= d:  # 人數小於等於 d
                tot += s*(p*8//10); s = 0; t -= s
            else:  # 人數大於 d
                tot += d*(p*8//10); s -= d; t -= d
        elif t >= d:  # 商品數量大於等於 d
            if s <= d:  # 人數小於等於 d
                tot += s*(p*9//10); s = 0; t -= s
            else:  # 人數大於 d
                tot += d*(p*9//10); s -= d; t -= d
    print(tot)

因為以上的程式碼有許多重複的地方，可以簡化成以下的樣子，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

dis = (5, 6, 8, 9)  # 折扣
for line in sys.stdin:
    t, s, p = map(int, line.split())  # 商品初始數量、來店顧客數、商品單價
    d, tot, i = t//5, 0, 0  # 1/5 的商品數量，總金額，索引值
    while i < 4 and s > 0:  # i 小於 4，還有顧客
        n = d + (i==0)  # 這次最多可以販賣的數量，若 i 等於 0 時 n = d+1，否則 n = d
        tot += min(s, n)*(p*dis[i]//10); s -= min(s, n); t -= n; i += 1  # 數量取 s, n 較小值
    print(tot)

ZeroJudge 解題筆記：j538. 賣場設置 (Market)

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



ZeroJudge 題目連結：j538. 賣場設置 (Market)

解題想法

我是用字典儲存商品位置及數量，寫起來比較簡單。

Python 程式碼

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

import sys
from collections import defaultdict

for s in sys.stdin:
    s = s.strip().lower()  # 商品種類，去掉結尾的 \n 再轉成小寫
    t = input().strip()  # 商品數量，去掉結尾的 \n
    pos = defaultdict(list)  # 各商品種類所在的位置
    val = defaultdict(int)  # 各商品種類的數量
    for i, (k, v) in enumerate(zip(s, t)):  # 將 s, t 綁在一起輸出
        pos[k].append(i)  # 商品 k 的位置新增 i
        val[k] += int(v)  # 商品 k 的數量加 v
    ans = [0]*len(s)  # 記錄答案用的串列
    for k, p in pos.items():  # 依序讀取 pos 的 key, value
        a = val[k]//len(p)  # 平均數量
        r = val[k]%len(p)  # 餘數
        for i, x in enumerate(p[::-1]):  # 從 p 尾端往回讀取位置
            if i < r: ans[x] = a+1  # 後面 r 個位置數量為 a+1
            else: ans[x] = a  # 其它位置數量為 a
    print(*ans, sep="")  # 將 ans 拆開、印出，不加分隔符號

ZeroJudge 解題筆記：j537. 工廠派遣 (Factory)

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



ZeroJudge 題目連結：j537. 工廠派遣 (Factory)

解題想法

這題將每間工廠的産值 a、需要的人數 p，綁在一起放入陣列，依照 v 由大到小排序會比較方便。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 間工廠
    # 讀取每間工廠的産值 a、需要的人數 p，組成 tuple、放入 list，依照 v 由大到小排序
    ap = sorted([tuple(map(int, input().split())) for _ in range(n)], reverse=True)
    h = int(input())  # 總人數
    cnt = 0  # 有分配到人的工廠數量
    idx = 0  # 從 ap 讀取資料的索引值
    while idx < n and h > 0:  # 如果 idx 還沒有出界而且還有人，繼續執行
        cnt += 1; h -= ap[idx][1]; idx += 1  # cnt 加 1，h 減去此工廠的人數，idx 加 1
    print(cnt)

ZeroJudge 解題筆記：j536. 不穩定的礦石 (Ore)

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



ZeroJudge 題目連結：j536. 不穩定的礦石 (Ore)

解題想法

分成兩次檢查吸收能量的狀況比較好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, a = map(int, line.split())  # n 個礦石，吸收力 a
    stone = list(map(int, input().split()))  # 礦石原來的能量
    p = stone.index(max(stone))  # 最多能量的礦石位置
    isum = sum(stone)  # 總能量
    cnt, imax = 0, stone[p]  # 已吸收的數量，吸收後的能量
    le = p - 1  # 向左吸收的位置
    # 向左吸收，最多吸收到位置 0 或是 p-a//2 為止，cnt 一定小於 a
    while le >= 0 and le >= p-a//2:
        cnt += 1; imax += stone[le]; le -= 1
    ri = p + 1  # 向右吸收的位置
    # 向右吸收，最多吸收到位置 n-1 或是 p+a//2 為止，cnt 一定小於 a
    while ri < n and ri <= p+a//2:
        cnt += 1; imax += stone[ri]; ri += 1
    # 第二次向左吸收，最多吸收到 cnt 等於 a 或是位置 0 
    while cnt < a and le >= 0:
        cnt += 1; imax += stone[le]; le -= 1
    # 第二次向右吸收，最多吸收到 cnt 等於 a 或是位置 n-1
    while cnt < a and ri < n:
        cnt += 1; imax += stone[ri]; ri += 1
    print(imax, isum-imax)  # 印出答案

ZeroJudge 解題筆記：j354. 積木對接 (Blocks)

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



ZeroJudge 題目連結：j354. 積木對接 (Blocks)

解題想法

這題將判斷兩個積木是否有解的函式另外寫會比較方便。

Python 程式碼

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

import sys

def solve(bot, top):  # 輸入兩個積木測試是否有解
    n, m = len(bot), len(top)
    if m > n:  # 特例，上方的積木較長，無解
        print("NO"); return
    d = n - m  # 長度差
    for i in range(d+1):  # 短積木的左側位置可能是 0 ~ d
        if all([t&b == 0 for t, b in zip(top, bot[i:i+m])]):
            print("YES"); return
    print("NO"); return

for line in sys.stdin:
    n = int(line)  # 長積木的卡榫數量
    bot = []  # 下方的長積木每格的高度，0 代表低，1 代表高
    h = 0  # 高度，長積木由 0 開始
    for b in map(int, input().split()):  # 依序設定長積木每格的高度
        for _ in range(b): bot.append(h)  # 放入 b 個 h
        h = 1 - h  # 0 變 1 或 1 變 0
    m = int(input())  # 短積木的卡榫數量
    top = []  # 上方的短積木每格的高度，0 代表低，1 代表高
    h = 1  # 高度，短積木由 1 開始
    for t in map(int, input().split()):  # 依序設定短積木每格的高度
        for _ in range(t): top.append(h)  # 放入 t 個 h
        h = 1 - h  # 0 變 1 或 1 變 0
    solve(bot, top)

ZeroJudge 解題筆記：j352. 開心農場 (Farm)

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



ZeroJudge 題目連結：j352. 開心農場 (Farm)

解題想法

依序讀取資料並判斷是否能開花即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 週數
    rain = list(map(int, input().split()))  # 雨量
    sun = list(map(int, input().split()))  # 日照
    R, S = map(int, input().split())  # 所需總雨量、日照
    tr, ts, state = 0, 0, False  # 累積的雨量、日照、是否開花
    for i, (r, s) in enumerate(zip(rain, sun), start=1):
        tr += r; ts += s  # 更新累積的雨量、日照
        if tr >= R and ts >= S:  # 達到開花條件，印出 i+1，中止迴圈
            print(i+1); state = True; break
    if not state: print(-1)  # 不能開花，印出 -1

ZeroJudge 解題筆記：j180. 戰備存糧 (Food)

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



ZeroJudge 題目連結：j180. 戰備存糧 (Food)

解題想法

這題如果按照題目的敘述，先將每個倉庫的存糧減 1，再將後方倉庫的存糧往前塞，這樣會跑很慢，一定無法通過測試。既然題目要將存糧盡量往前塞，那就乾脆計算存糧的數量，如果能用更少的倉庫裝下存糧，那就減一個倉庫。

Python 程式碼

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

while True:
    line = input().strip()
    if line == "-1": break
    n, e = map(int, line.split())
    tot = n*e  # 存糧總量
    day = 0  # 天數
    while tot > 0:  # 還有存糧
        day += 1  # 天數加 1
        tot -= n  # 存糧減 n
        while tot <= (n-1)*e:  # 如果剩下的存糧可以用 (n-1) 個倉庫裝下
            n -= 1  # 減 1 個倉庫
    print(day)

ZeroJudge 解題筆記：j179. 資料分類 (Classification)

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



ZeroJudge 題目連結：j179. 資料分類 (Classification)

解題想法

注意：n 的位數在運算時不一定會遞減。

Python 程式碼

利用 int 將字串轉成整數，刪除前面的 0，再用 str 轉回字串。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

import sys

for n in sys.stdin:
    n = n.strip()
    while len(n) > 1:  # 如果 n 長度大於 1 繼續執行
        if len(n) == 4:  # 4 位數
            le, ri = n[:2], n[2:]  # 左、右半邊
            if int(le) >= 10:  # 轉成 int，如果大於等於 10 才要相乘
                le = str(int(le[0])*int(le[1]))  # 兩位轉成 int 相乘再轉回 str
            if int(ri) >= 10:  # 轉成 int，如果大於等於 10 才要相乘
                ri = str(int(ri[0])*int(ri[1]))  # 兩位轉成 int 相乘再轉回 str
            else: ri = str(int(ri))  # 去掉前面的 0
            n = str(int(le + ri))  # 先將 le + ri 轉成 int 再轉回 str，去掉前面的 0
        elif len(n) == 3:  # 3 位數
            le, ri = n[:2], n[1:]  # 左、右半邊
            le = str(int(le[0])*int(le[1]))  # 兩位轉成 int 相乘再轉回 str
            ri = str(int(ri[0])*int(ri[1]))  # 兩位轉成 int 相乘再轉回 str
            n = str(int(le + ri))  # 先將 le + ri 轉成 int 再轉回 str，去掉前面的 0
        elif len(n) == 2:  # 2 位數
            n = str(int(n[0])*int(n[1]))  # 兩位轉成 int 相乘再轉回 str
    print(n)

ZeroJudge 解題筆記：i378. 垂直對稱 (Symmetry)

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



ZeroJudge 題目連結：i378. 垂直對稱 (Symmetry)

解題想法

相同的 x 座標上如果有奇數個點，則 y 座標正中央的點必須在水平對稱線上，而且只能有 1 個值。接著再檢查一次，相同的 x 座標上所有的點 y 座標和，必須等於水平對稱線的 y 座標乘以點的數量。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個點
    ps = dict()  # x 座標: [y1, y2, ...]
    for _ in range(n):  # 讀取 n 個點
        x, y = map(int, input().split())
        if x not in ps: ps[x] = [y]
        else: ps[x].append(y)
    cand = 10000  # 水平對稱線可能的 y 座標，預設為超出題目範圍的值
    found = True  # 是否有解
    for _, ys in ps.items():  # 找相同的 x 座標中所有點的 y 座標
        ys.sort()  # 要排序
        if len(ys)%2 == 1:  # 如果有奇數個點的項目
            if cand == 10000: cand = ys[len(ys)//2]  # 如果 cand 是預設值，更新
            elif cand != ys[len(ys)//2]:  # 不相同
                found = False; break  # 無解
    if found:  # 如果只有一個 cand
        for _, ys in ps.items():  # 找相同的 x 座標中所有點的 y 座標
            if cand*len(ys) != sum(ys):  # 如果不相等，cand 不在這些點的正中央
                found = False; break  # 無解
    print("success" if found else "failure")

ZeroJudge 解題筆記：i377. 單字找找看 (Word)

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



ZeroJudge 題目連結：i377. 單字找找看 (Word)

解題想法

這題寫起來很長，因為要找 8 個方向，依照題目對於答案的要求，搜尋的方向依序是左上、正上、右上、正左、正右、左下、正下、右下。

Python 程式碼

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

import sys

def solve(g, t):  # 輸入字串方格 g，找目標字串 t
    m, n = len(g) -1, len(g[0]) -1  # 列數減 1，每列長度減 1
    tl = len(t)  # t 的長度
    for r in range(m):  # 依序掃過每列
        for c in range(n):  # 依序掃過每欄
            found = True  # 是否找到答案，先找左上方
            for i in range(tl):
                if t[i] != grid[r-i][c-i]:  # 只要字元不相等就可以中止迴圈
                    found = False; break
            if found:  # 如果找到答案，印出起點、終點，記得加 1
                print(f"{r+1:d} {c+1:d}\n{r-tl+2:d} {c-tl+2:d}")
                return  # 中止函式
            found = True  # 是否找到答案，找正上方
            for i in range(tl):
                if t[i] != grid[r-i][c]:
                    found = False; break
            if found:
                print(f"{r+1:d} {c+1:d}\n{r-tl+2:d} {c+1:d}")
                return
            found = True  # 是否找到答案，找右上方
            for i in range(tl):
                if t[i] != grid[r-i][c+i]:
                    found = False; break
            if found:
                print(f"{r+1:d} {c+1:d}\n{r-tl+2:d} {c+tl:d}")
                return
            found = True  # 是否找到答案，找正左方
            for i in range(tl):
                if t[i] != grid[r][c-i]:
                    found = False; break
            if found:
                print(f"{r+1:d} {c+1:d}\n{r+1:d} {c-tl+2:d}")
                return
            found = True  # 是否找到答案，找正右方
            for i in range(tl):
                if t[i] != grid[r][c+i]:
                    found = False; break
            if found:
                print(f"{r+1:d} {c+1:d}\n{r+1:d} {c+tl:d}")
                return
            found = True  # 是否找到答案，找左下方
            for i in range(tl):
                if t[i] != grid[r+i][c-i]:
                    found = False; break
            if found:
                print(f"{r+1:d} {c+1:d}\n{r+tl:d} {c-tl+2:d}")
                return
            found = True  # 是否找到答案，找正下方
            for i in range(tl):
                if t[i] != grid[r+i][c]:
                    found = False; break
            if found:
                print(f"{r+1:d} {c+1:d}\n{r+tl:d} {c+1:d}")
                return
            found = True  # 是否找到答案，找右下方
            for i in range(tl):
                if t[i] != grid[r+i][c+i]:
                    found = False; break
            if found:
                print(f"{r+1:d} {c+1:d}\n{r+tl:d} {c+tl:d}")
                return
    print("NO"); return

for line in sys.stdin:
    m, n = map(int, line.split())  # 表格 m*n
    grid = [input().strip().lower()+"0" for _ in range(m)]  # 加 0 作為哨兵
    grid.append("0"*(n+1))
    solve(grid, input().strip().lower())

ZeroJudge 解題筆記：i376. 尋寶 (Treasure)

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



ZeroJudge 題目連結：i376. 尋寶 (Treasure)

解題想法

我是先掃過每一列找出最高處，將這些位置的座標加入一個集合 cand 之中；再掃過每一欄，找每欄的最低點，如果此處的座標在 cand 之中，表示已經找到答案。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 地圖 n*n
    grid = [list(map(int, input().split())) for _ in range(n)]  # 地圖資料
    cand = []  # 可能的地點
    for r in range(n):  # 先找每列最高處放入 cand，可能有多個最高處
        imax = max(grid[r])  # 第 r 列的最大值
        for c in range(n):  # 依序掃過每欄
            if grid[r][c] == imax:  # 如果此格等於 imax
                cand.append((r, c))  # (r, c) 加入 cand
    found = False  # 是否找到答案
    for c in range(n):  # 依序找每欄的最低處在第幾列
        imin = min([grid[i][c] for i in range(n)])  # 第 c 欄的最小值
        for r in range(n):  # 依序掃過每列
            if grid[r][c] == imin and (r, c) in cand:  # 如果此格等於 imin 而且在 cand 之中
                found = True  # 找到答案
                print(r, c)  # 印出 (r, c)
                break  # 中止迴圈
        if found: break  # 如果已經找到答案，中止迴圈    
    if not found: print("NO")  # 如果沒有找到答案印出 NO

ZeroJudge 解題筆記：i164. 比對卡片(進階版)

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



ZeroJudge 題目連結：i164. 比對卡片(進階版)

解題想法

題目的敘述是：對老師的每張卡片，孩童需找到自己的卡片中和老師卡片數字相同且位置差距最小的卡片。看起來應該是孩童依照自己手上的卡片，依序找每張卡片的數字是否有在老師手上的卡片之中，如果有則要找距離最近的卡片並記錄位置差；但如果以題目中範例的圖示來看則是反過來，老師依照自己手上的卡片，依序找每張卡片的數字是否有在孩童手上的卡片之中，如果有則要找距離最近的卡片並記錄位置差。 這題的基礎版為〈i070. 比對卡片 (Match)〉，測資小很多，用基本的寫法就能通過，但是這題不行。要從左向右、從右向左各掃過一次，記錄 a[i] 前一次出現的位置，如果 a[i] 已經出現過就更新距離。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 牌的數量
    a = list(map(int, input().split()))  # 老師的牌
    b = list(map(int, input().split()))  # 孩童的牌
    pre = [-1]*1000000  # 每張牌前一次出現的位置，-1 代表還沒有出現過，題目牌面編號最大值為 100000
    ans = [n]*n  # 答案，預設為過大的值 n，因為位置差為 0 ~ n-1
    for i in range(n):  # 依序檢查每張牌
        pre[b[i]] = i  # b[i] 的數字前一次出現為位為 i
        if pre[a[i]] != -1:  # 如果 a[i] 的數字之前已經出現過
            ans[i] = min(ans[i], abs(i - pre[a[i]]))  # 更新位置差
    for i in range(n-1, -1, -1):  # 反過來檢查每張牌
        pre[b[i]] = i  # b[i] 的數字前一次出現為位為 i
        if pre[a[i]] != -1:  # 如果 a[i] 的數字之前已經出現過
            ans[i] = min(ans[i], abs(i - pre[a[i]]))  # 更新位置差
    ans = list(map(lambda x : -1 if x == n else x, ans))  # ans 之中的 n 取代為 -1
    print(*ans)

ZeroJudge 解題筆記：i071. 風景 (Landscape)

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



ZeroJudge 題目連結：i071. 風景 (Landscape)

解題想法

從起點開始向左、向右線性搜尋各一次即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 棟建築，人在第 m 棟，編號從 1 開始
    hs = list(map(int, input().split()))  # 所有建築物的高度
    tot = 0  # 能看到的建築物數量
    m -= 1  # 建築物編號改成從 0 開始
    pre = hs[m]  # 前一棟最高建築物的高度，預設為自己所在的建築物高度
    for i in range(m, 0, -1):  # 從 m 開始向左找
        if hs[i-1] > pre:  # 如果左邊的建築物高度大於 pre
            tot += 1  # tot 加 1
            pre = hs[i-1]  # 更新 pre
    pre = hs[m]  # 重設 pre
    for i in range(m, n-1):  # 從 m 開始向右找
        if hs[i+1] > pre:  # 如果右邊的建築物高度大於 pre
            tot += 1  # tot 加 1
            pre = hs[i+1]  # 更新 pre
    print(tot)  # 印出答案

ZeroJudge 解題筆記：i070. 比對卡片 (Match)

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



ZeroJudge 題目連結：i070. 比對卡片 (Match)

解題想法

題目的敘述是：對老師的每張卡片，孩童需找到自己的卡片中和老師卡片數字相同且位置差距最小的卡片。看起來應該是孩童依照自己手上的卡片，依序找每張卡片的數字是否有在老師手上的卡片之中，如果有則要找距離最近的卡片並記錄位置差；但如果以題目中範例的圖示來看則是反過來，老師依照自己手上的卡片，依序找每張卡片的數字是否有在孩童手上的卡片之中，如果有則要找距離最近的卡片並記錄位置差。

另外有一題進階版〈i164. 比對卡片(進階版)〉，測資大很多。

Python 程式碼

寫法1，用串列切片及 index 找索引值。使用時間約為 21 ms，記憶體約為 3.5 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 牌的數量
    a = list(map(int, input().split()))  # 老師的牌
    b = list(map(int, input().split()))  # 孩童的牌
    for i in range(n):  # 依序檢查每張牌
        t = a[i]  # 目標
        if t not in b:  # 如果 t 不在 b 之中，印出 -1
            print(-1, end="\n" if i == n-1 else " ")
        elif i == 0:  # 編號 0，只要向右找，索引值等於位置差
            if t not in b: print(-1, end=" ")  # 如果 t 不在 b 之中，印出 -1
            else: print(b.index(t), end=" ")
        elif i == n-1:  # 編號 n-1，只要向左找
            if t not in b: print(-1)  # 如果 t 不在 b 之中，印出 -1
            else: print(b[::-1].index(t))  # 先將 b 反過來再找 t
        else:  # 編號在中間，向右、向左各找一次，取較小的值
            left = b[:i+1][::-1]  # 取 b[0] ~ b[i+1]，再反向
            right = b[i:]  # 取 b[i] ~ b[n-1]
            p, q = n, n  # 儲存位置差的變數，先預設為 n
            if t in right: p = right.index(t)  # 向右找
            if t in left: q = left.index(t)  # 向左找
            print(min(p, q), end=" ")  # 印出小的那個

ZeroJudge 解題筆記：i069. 岩石觀察 (Stones)

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



ZeroJudge 題目連結：i069. 岩石觀察 (Stones)

解題想法

因為 Python 會一次讀取整行的資料，存成串列後再找最大值、最小值。C++ 一次讀取一筆資料，可以在讀取所有盒子的資料時一邊找最大值、最小值。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個盒子
    box = list(map(int, input().split()))  # 原來的數量
    avg = sum(box)//n  # 平均數量
    pmax = box.index(max(box))  # 數量最多的盒子編號
    pmin = box.index(min(box))  # 數量最少的盒子編號
    d = box[pmax] - avg  # 移動的數量
    box[pmax] -= d  # 減少 d
    box[pmin] += d  # 增加 d
    print(*box)  # 印出答案

ZeroJudge 解題筆記：h660. 躲避球 (DodgeBall)

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



ZeroJudge 題目連結：h660. 躲避球 (DodgeBall)

解題想法

按照題目敘述計算位置即可，不需要複雜的寫法。

Python 程式碼

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

import sys

for line in sys.stdin:
    x, r, v = map(int, line.split())  # 阿茂的位置、接球的左右延伸長度、可接球的球速上限
    for _ in range(int(input())):  # 執行 n 次
        p, s = map(int, input().split())  # 球的落點、速度
        if x-r <= p <= x+r:  # 球在可以接到的範圍內
            if s <= v: x = p  # 球速夠慢，可以接球，移動到 p
            else:  # 球速太快，不能接球
                if p >= x: x -= 15  # 球在右邊或朝人過去，向左移 15
                else: x += 15  # 球在左邊，向右移 15
    print(x)  # 印出最後的位置

ZeroJudge 解題筆記：k518. P6.蛋糕切塊 (Cake)

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



ZeroJudge 題目連結：k518. P6.蛋糕切塊 (Cake)

解題想法

這題考動態規畫，我同時利用 set 儲存可用的子字串，這樣程式運作速度會比較快。

Python 程式碼

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

import sys

def can_cut_cake(s, cuts):
    n = len(s)  # 字串長度
    dp = [False]*(n+1)  # 是否能走到 i，如果能走到 i+1 代表有解
    dp[0] = True  # 一定能走到開頭
    # 動態規劃遍歷
    for i in range(1, n+1):  # 依序找終點 i = 1 ~ n
        for j in range(i):  # 依序找起點 j = 0 ~ i-1
            if dp[j] and s[j:i] in cuts:  # 如果能走到 j 而且 s[j:i] 在 cuts 之中
                dp[i] = True  # 可以走到 i
                break  # 只要找到一個可行切割後就可以停止
    print("yes" if dp[n] else "no")  # 如果 dp[n] 為 True 印出 yes，反之印出 no

for s in sys.stdin:
    s = s.strip()  # 要檢查的字串
    m = int(input())  # 可用的子字串數量
    cuts = set()  # 可用的子字串
    for _ in range(m): cuts.add(input())  
    can_cut_cake(s, cuts)  # 計算並輸出結果

ZeroJudge 解題筆記：h659. 計程車 (Taxi)

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



ZeroJudge 題目連結：h659. 計程車 (Taxi)

解題想法

按照題目敘述的標準計算費用即可，不需要複雜的寫法。

Python 程式碼

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

import sys

for line in sys.stdin:
    # 行駛總公里數、車輛延滯時間 (min)、上車及下車的時刻 (hr)
    k, w, s, e = map(int, line.split())
    fee = 0  # 費用
    # 計算行駛總公里數産生的費用
    if k <= 2: fee += 20  # 2 km 以內 20 元
    else: fee += 20 + (k-2)*5  # 超過 2 km 加錢 5 元/km
    # 計算車輛延滯時間産生的費用
    fee += w//2*5  # 每滿 2 min 加 5 元
    # 計算夜間加成産生的費用
    if s <= 18 and e >= 19: fee += 185  # 橫跨 18 ~ 19 時，加 185 元
    if s <= 19 and e >= 20: fee += 195  # 橫跨 19 ~ 20 時，加 195 元
    if s <= 20 and e >= 21: fee += 205  # 橫跨 20 ~ 21 時，加 205 元
    if s <= 21 and e >= 22: fee += 215  # 橫跨 21 ~ 22 時，加 215 元
    if s <= 22 and e >= 23: fee += 225  # 橫跨 22 ~ 23 時，加 225 元
    print(fee)  # 印出答案

ZeroJudge 解題筆記：h658. 捕魚 (Fishing)

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



ZeroJudge 題目連結：h658. 捕魚 (Fishing)

解題想法

用距離平方判斷是否在範圍內即可，不需要開根號。

Python 程式碼

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

import sys

for line in sys.stdin:
    x, y = map(int, line.split())  # 漁夫的座標
    n = int(input())  # n 筆資料
    ax, ay, d = 0, 0, float('inf')  # 最接近的魚群座標、距離的平方
    for _ in range(n):  # 執行 n 次
        xi, yi = map(int, input().split())  # 魚群座標
        di = (x - xi)**2 + (y - yi)**2  # 距離的平方
        if di < d:  # 如果距離較近，更新 ax, ay, d
            ax, ay, d = xi, yi, di
    print(ax, ay)

ZeroJudge 解題筆記：h035. 夜市 (Night Market)

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



ZeroJudge 題目連結：h035. 夜市 (Night Market)

解題想法

注意題目中的這句「但一塊板子只會採計一次得分」，不能重複計分。測資應該只有單筆輸入。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 投球 n 次
    down = [-1]*10  # 各編號的格子被打落的時刻，-1 代表沒有被打落
    hit = [False]*10  # 各編號的格子是否被打落過
    cnt, score, perfect = 0, 0, False  # 目前打落的板子數量，總分，是否全清
    for i, x in enumerate(list(map(int, input().split())), start=1):  # 依序讀取投球命中的格子
        for j in range(1, 10):  # 檢查每塊板子是否能升起
            if down[j] != -1 and i == down[j] + 12:  # 如果第 j 塊板子已被打落而且 i 等於第 j 塊板子被打落的時刻加 12
                down[j] = -1; cnt -= 1  # 升起第 j 塊板子，cnt 減 1
        if x != -1 and down[x] == -1:  # 如果 x 不等於 -1 而且 x 號板子目前沒有被打落
            cnt += 1; down[x] = i  # cnt 加 1，設定 x 被打落的時刻為 i
            if not hit[x]:  # 如果 x 號板子沒有被打落過
                score += x; hit[x] = True  # 分數加 x，x 號板子被打落過
        if cnt == 9:  # 如果 cnt 等於 9，全清，中止迴圈
            perfect = True; break
    print("perfect" if perfect else score)

ZeroJudge 解題筆記：h034. 宴會 (Banquet)

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



ZeroJudge 題目連結：h034. 宴會 (Banquet)

解題想法

這題在 Python 可以 itertools.zip_longest 會比較方便。

Python 程式碼

只使用預設工具的寫法，使用時間約為 53 ms，記憶體約為 5.9 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 餐廳總數
    food = [input().strip() for _ in range(n)]  # 儲存各餐廳的菜單
    m = max([len(f) for f in food])  # 最長的菜單數量
    for i in range(m):  # 處理 m 次
        for j in range(n):  # 印出各家餐廳的菜名
            if i < len(food[j]) and food[j][i].isupper():  # 如果 i 還沒有出界而且 food[j][i] 是大寫字母
                print(food[j][i], end="")  # 印出這個字母
    print()  # 全部跑完再換行

Python 中有一個 zip 工具，用來將數個可以迭代的物件綁在一起輸出，但是 zip 會以這些物件中最短的一個作為輸出的上限，其它較長的部分會被捨去。如果要以最長的物件作為輸出的上限，要用 itertools.zip_longest，長度不夠的部分會補 None。使用時間約為 55 ms，記憶體約為 6 MB，通過測試。

import sys
from itertools import zip_longest

for line in sys.stdin:
    n = int(line)  # 餐廳總數
    food = [input().strip() for _ in range(n)]  # 儲存各餐廳的菜單
    for f in zip_longest(*food):  # 先將 food 拆開成多個一維串列，用 zip_longest 綁在一起依序輸出
        for c in f:  # 依序由 f 讀取各家餐廳的菜名
            if c != None and c.isupper():  # 如果 c 不等於 None 而且是大寫字母
                print(c, end="")  # 印出這個字母
    print()  # 全部跑完再換行