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 解題筆記：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()  # 全部跑完再換行

ZeroJudge 解題筆記：h033. 雜訊移除 (Noise)

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



ZeroJudge 題目連結：h033. 雜訊移除 (Noise)

解題想法

這題在 Python 可以用 replace 將不要的字元取代成空字串。

Python 程式碼

用 replace 可以取代字串中指定的字元，取代為空字串就可以移除特定字元。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def is_palindrome(s):  # 檢查 s 是否為迴文字串
    n = len(s)  # s 的長度 n
    for i in range(n//2):  # 依序檢查從頭尾兩端往中間檢查
        if s[i] != s[n-i-1]: return False  # 如果字元不相同回傳 False
    return True  # 如果可以跑完 for loop，回傳 True

for line in sys.stdin:
    s, n = line.split()  # 要分析的字串 s，要移除的字元 n
    s = s.replace(n, "")  # 將 s 之中的 n 取代為空字串
    print("Yes" if is_palindrome(s) else "No")  # 印出答案

如果不使用 replace，也可以遍歷字串，將要留下來的字元存到另一個空字串裡。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def is_palindrome(s):  # 檢查 s 是否為迴文字串
    n = len(s)  # s 的長度 n
    for i in range(n//2):  # 依序檢查從頭尾兩端往中間檢查
        if s[i] != s[n-i-1]: return False  # 如果字元不相同回傳 False
    return True  # 如果可以跑完 for loop，回傳 True

for line in sys.stdin:
    s, n = line.split()  # 要分析的字串 s，要移除的字元 n
    t = ""  # 儲存 s 移除 n 之後的空字串
    for c in s:  # 依序由 s 讀取字元 c
        if c != n: t += c  # 如果 c 不等於 n，接到 t 之後
    print("Yes" if is_palindrome(t) else "No")  # 印出答案

ZeroJudge 解題筆記：g798. 帶動商機 (Business)

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



ZeroJudge 題目連結：g798. 帶動商機 (Business)

解題想法

這題按照題目敘述操作陣列即可，不需要用複雜的寫法。

Python 程式碼

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

import sys

for line in sys.stdin:
    arr = list(map(int, line.split()))[:-1]  # 讀取一開始的人數，刪掉最後的 0
    m = len(arr)  # 店家數量
    n = int(input())  # 更新 n 天
    for _ in range(n):  # 執行 n 次
        tmp = arr.copy()  # 暫存更新後的人數
        for i in range(m):  # 依序掃過 0 ~ m-1 家店
            if i == 0:  # 最左邊的店家
                if arr[i] > arr[i+1]:  # 如果人數大於右邊的店家
                    tmp[i+1] += arr[i]//10  # 右邊的店家人數增加量
            elif i == m-1:  # 最右邊的店家
                if arr[i] > arr[i-1]:  # 如果人數大於左邊的店家
                    tmp[i-1] += arr[i]//10  # 左邊的店家人數增加量
            else:  # 中間的店家
                if arr[i] > arr[i-1]:  # 如果人數大於左邊的店家
                    tmp[i-1] += arr[i]//20  # 左邊的店家人數增加量
                if arr[i] > arr[i+1]:  # 如果人數大於右邊的店家
                    tmp[i+1] += arr[i]//20  # 右邊的店家人數增加量
        arr, tmp = tmp, arr  # 交換 arr、tmp
    print(*arr)  # 印出答案

ZeroJudge 解題筆記：g797. 洗牌 (Cards)

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



ZeroJudge 題目連結：g797. 洗牌 (Cards)

解題想法

這題考陣列操作，可以將陣列先拆開成上、下兩半再合併，或是用另一個陣列儲存洗牌後的資料。

Python 程式碼

寫法1，用串列切片先找出上、下兩半的內容，再合併資料。使用時間約為 26 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    upp, bot = deck[:n//2], deck[n//2:]  # 分成上、下兩半
    for _ in range(m):  # 執行 m 次
        for i in range(n//2):  # 執行 n//2 次
            deck[2*i] = upp[i]  # 從 upp 及 bot 依序取值放入 deck
            deck[2*i+1] = bot[i]
        upp, bot = deck[:n//2], deck[n//2:]  # 更新 upp、bot
    print(*deck)  # 印出答案

寫法2，滾動串列，將洗牌後的資料先存入另一個串列。使用時間約為 28 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    for _ in range(m):  # 執行 m 次
        tmp = [0]*n  # 暫存洗牌後的資料
        for i in range(n//2):  # 執行 n//2 次
            tmp[2*i] = deck[i]  # 從 deck 前半取值放入 tmp
            tmp[2*i+1] = deck[n//2 + i]  # 從 deck 後半取值放入 tmp
        deck, tmp = tmp, deck  # 交換 deck、tmp
    print(*deck)  # 印出答案

ZeroJudge 解題筆記：g541. 類題:兔子跳躍(TOIP)

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



ZeroJudge 題目連結：g541. 類題:兔子跳躍(TOIP)

解題想法

雖然看起來是g498. 兔子跳躍 (Rabbit)的加強版，但其實用相同的寫法跑迴圈測試是否能走到 $d$ 一定會超時，即使用字典儲存已經跑過的值還是會超時，需要從數學上分析題目才行。如果兩種步數 $m$、$n$ 的最大公因數為 $G$、最小公倍數為 $L$，則所有 $L + kG, k = 0, 1, 2, 3, \dots$ 的數皆可以用大於等於 0 個 $m$、$n$ 組合而成，若以 $m = 9$、$n = 12$ 為例，$G = 3$、$L = 36$，則

1. $36 = 4 \times 9 = 3 \times 12$
2. $39 = 3 \times 9 + 1 \times 12$
3. $42 = 2 \times 9 + 2 \times 12$
4. $45 = 1 \times 9 + 3 \times 12$
5. $48 = 0 \times 9 + 4 \times 12$
6. $51 = 3 \times 9 + 2 \times 12$
7. $54 = 2 \times 9 + 3 \times 12$
8. $57 = 1 \times 9 + 4 \times 12$
9. $60 = 0 \times 9 + 5 \times 12 = 4 \times 9 + 2 \times 12$
10. $63 = 3 \times 9 + 3 \times 12$

Python 程式碼

寫法1，根據g498. 兔子跳躍 (Rabbit)的寫法改寫而成，第2筆測資開始超時。

import sys

def solve(m, n, d):  # 自訂函式，測是是否能走到 d
    for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
        if (d-i)%n == 0: return True  # 如果 d-i 可以被 n 整除，能走到 d
    return False  # 如果能跑完 for 迴圈，走不到 d

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(m, n, d) else "NO")  # 印出答案

寫法2，根據以上的寫法並改用 map 儲存已經測試過的值，第2筆測資開始超時。

import sys

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    memo = dict()  # 記憶已經算過的數據
    def solve(d):  # 自訂函式，測是是否能走到 d
        if d in memo: return memo[d]
        for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
            if (d-i)%n == 0:
                memo[d] = True
                return True  # 如果 d-i 可以被 n 整除，能走到 d
        memo[d] = False
        return False  # 如果能跑完 for 迴圈，走不到 d
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(d) else "NO")  # 印出答案

ZeroJudge 解題筆記：g498. 兔子跳躍 (Rabbit)

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



ZeroJudge 題目連結：g498. 兔子跳躍 (Rabbit)

解題想法

這題測資不大，用 for 迴圈依序檢測每一個值就能過關。

Python 程式碼

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

import sys

for line in sys.stdin:
    m, n, d = map(int, line.split())  # 可跳距離 m、n，目標距離 d
    def solve():  # 自訂函式，測是是否能走到 d
        for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
            if (d-i)%n == 0: return True  # 如果 d-i 可以被 n 整除，能走到 d
        return False  # 如果能跑完 for 迴圈，走不到 d
    print("YES" if solve() else "NO")  # 印出答案

C++ 程式碼

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

#include <cstdio>
using namespace std;

bool solve(int m, int n, int d) {  // 自訂函式，測是是否能走到 d
    for(int i=0; i<=d; i+=m) {  // 依序測試 0, m, 2m, 3m, ...
        if ((d-i)%n == 0) return true;  // 如果 d-i 可以被 n 整除，能走到 d
    }
    return false;  // 如果能跑完 for 迴圈，走不到 d
}

int main() {
    int m, n, d;  // 可跳距離 m、n，目標距離 d
    while(scanf("%d %d %d", &m, &n, &d) != EOF) {
        if (solve(m, n, d)) printf("YES\n");  // 印出答案
        else printf("NO\n");
    }
    return 0;
}

ZeroJudge 解題筆記：g497. 電梯 (Elevator)

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



ZeroJudge 題目連結：g497. 電梯 (Elevator)

解題想法

注意：電梯一開始在 1 樓。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 升降次數
    arr = [1] + list(map(int, input().split()))  # 停留的樓層，開頭加上 1
    tot = 0  # 耗電量
    for i in range(n):  # 依序掃過 0 ~ n-1
        d = arr[i+1] - arr[i]  # 樓層變化
        if d > 0: tot += 3*d  # 上升一層耗 3 度電
        else: tot -= 2*d  # 下降一層耗 2 度電
    print(tot)  # 印出答案

C++ 程式碼

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

#include <cstdio>
using namespace std;

int main() {
    int n;  // 升降次數
    while(scanf("%d", &n) != EOF) {
        int pre = 1, now, tot = 0;  // 原來的樓層，預設值為 1；現在的樓層；耗電量
        for(int i=0; i<n; i++) {  // 執行 n 次
            scanf("%d", &now);  // 讀取現在的樓層
            int d = now - pre;  // 樓層變化
            if (d > 0) tot += 3*d;  // 上升一層耗 3 度電
            else tot -= 2*d;  // 下降一層耗 2 度電
            pre = now;  // 更新 pre
        }
        printf("%d\n", tot);  // 印出答案
    }
    return 0;
}

ZeroJudge 解題筆記：g496. 彗星列車 (Comet)

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



ZeroJudge 題目連結：g496. 彗星列車 (Comet)

解題想法

注意：這題每組測資有多筆測試資料，而且每筆測試資料之間似乎有空行，如果用 Python 解題要忽略空行，否則會出錯。

Python 程式碼

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

import sys

for line in sys.stdin:
    if len(line.strip()) == 0: continue  # 忽略空行
    a, s = map(int, line.split())
    if s%a == 0: print(s//a)
    else: print(s//a + 1)

C++ 程式碼

用 cmath 函式庫的 ceil，先計算 s/a 的值再取 ceil，計算時及回傳值是浮點數，要再轉回整數，但是這樣無法通過第8筆測資。

#include <cstdio>
#include <cmath>  // for ceil
using namespace std;

int main() {
    int a, s;
    while(scanf("%d %d", &a, &s) != EOF) {
        printf("%d\n", int(ceil((float)s/(float)a)));
    }
    return 0;
}

還是回來用標準寫法，使用時間約為 6 ms，記憶體約為 96 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int a, s;
    while(scanf("%d %d", &a, &s) != EOF) {
        if (s%a == 0) printf("%d\n", s/a);
        else printf("%d\n", s/a + 1);
    }
    return 0;
}

ZeroJudge 解題筆記：g006. 密碼備忘錄 (Password)

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



ZeroJudge 題目連結：g006. 密碼備忘錄 (Password)

解題想法

這題我用字典計數，再用 cmp_to_key 或 lambda function 自訂比較式。

Python 程式碼

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

import sys
from collections import Counter
from functools import cmp_to_key

def mycmp(a, b):  # (key, val)
    if a[1] > b[1]: return -1  # 如果 a[1] > b[1]，a 往前放
    elif a[1] < b[1]: return 1  # 如果 a[1] < b[1]，a 往後放
    else:  # 如果 a[1] == b[1]
        if a[0] < b[0]: return -1  # 如果 a[0] < b[0]，a 往前放
        elif a[0] > b[0]: return 1  # 如果 a[0] > b[0]，a 往後放
        else: return 0

for s in sys.stdin:
    cnt = Counter(s.strip())  # 刪除 s 結尾的 \n，用 Counter 計算各字母數量
    ans = sorted([(k, v) for k, v in cnt.items()], key=cmp_to_key(mycmp))  # 排序
    print("".join([k for k, v in ans]))  # 將 k 取出組成字串再印出

ZeroJudge 解題筆記：g005. 倒置文章 (Inversion)

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



ZeroJudge 題目連結：g005. 倒置文章 (Inversion)

解題想法

這題考字串處理，從頭開始依序讀取字串的內容，先暫存內容到另一個字串，如果讀到 + 或 - 再結算之前暫存的內容，儲存到最後要輸出的字串之中。

Python 程式碼

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

import sys

for s in sys.stdin:
    s = s.strip()  # 刪除讀到的字串結尾的 \n
    rev = False  # 是否反轉，預設為否
    a, t = "", ""  # a 儲存答案，t 儲存反轉字串
    for c in s:  # 依序由 s 讀取字元 c
        if c == '+':  # 如果 c 是 +
            a += t; t = ""  # 結算之前儲存的 t，將 t 接到 a 之後再清空 t
            rev = False  # 順向
        elif c == '-':  # 如果 c 是 -
            a += t; t = ""  # 結算之前儲存的 t，將 t 接到 a 之後再清空 t
            rev = True  # 反向
        else:  # 如果 c 是其它字元
            if rev: t = c+t  # 如果目前是反向，將 c 接到 t 之前
            else: a += c  # 如果目前是順向，將 c 接到 a 之後
    a += t  # 最後再結算一次 t
    print(a)  # 印出答案

ZeroJudge 解題筆記：g004. 社區熱門度 (Popularity)

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



ZeroJudge 題目連結：g004. 社區熱門度 (Popularity)

解題想法

處理這種類型的題目時，我習慣在周圍或是最後面多加一些資料，可以避免在四方位檢查時出界。

Python 程式碼

可以先將答案存入另一個二維串列，使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 地圖 m*n
    grid = [list(map(int, input().split())) + [0] for _ in range(m)]  # 地圖資料，最後加上 0
    grid.append([0]*(n+1))  # 最後加上 n+1 個 0
    ans = [grid[r][:-1] for r in range(m)]  # 儲存答案用的二維串列
    for r in range(m):  # 依序掃過每一格
        for c in range(n):
            if grid[r][c] != 0: continue  # 如果 (r, c) 這個不等於 0，找下一格
            cnt, tot = 0, 0  # 右下左上 4 格非 0 的格子數量，熱門度加總
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 檢查周圍 4 格
                v = grid[r+dr][c+dc]
                if v != 0:
                    cnt += 1; tot += v
            if tot != 0: ans[r][c] = tot//cnt  # 如果 tot 不等於 0，更新 ans[r][c]
    for row in ans: print(*row)  # 印出答案

ZeroJudge 解題筆記：f820. 極限運動 (Sports)

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



ZeroJudge 題目連結：f820. 極限運動 (Sports)

解題想法

這題在左、右兩側各加上超出題目範圍的極大值，在向左、右找終點時可以避免出界。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 地圖上有 n 個位置
    hs = [1000] + list(map(int, input().split())) + [1000]  # 各位置高度，兩端加上 1000
    s = int(input())  # 起點 s
    e = s  # 終點 e 設定為 s
    if s == 1:  # 只能往右滑
        while hs[e] >= hs[e+1]: e += 1  # 向右滑直到右側高度大於左側為止
    elif s == n:  # 只能往左滑
        while hs[e] >= hs[e-1]: e -= 1  # 向左滑直到左側高度大於右側為止
    else:  # 可以向左或向右滑
        if hs[e-1] < hs[e+1]:  # 左側較低，向左滑
            while hs[e] >= hs[e-1]: e -= 1  # 向左滑直到左側高度大於右側為止
        else:  # 右側較低，向右滑
            while hs[e] >= hs[e+1]: e += 1  # 向右滑直到右側高度大於左側為止
    print(e)  # 印出終點

ZeroJudge 解題筆記：f819. 圖書館 (Library)

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



ZeroJudge 題目連結：f819. 圖書館 (Library)

解題想法

因為這題不確定要輸出的資料數量，在 C++ 用 vector 儲存資料會比較方便。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 本書
    books = []  # 逾期書的編號
    fine = 0  # 罰款金額
    for _ in range(n):  # 讀取 n 行資料
        b, d = map(int, input().split())  # 書的編號 b、天數 d
        if d > 100:  # 逾期
            books.append(b)  # b 加入 books
            fine += (d-100)*5  # 超過 100 天每天罰 5 元
    if not books: print(0)  # 如果 books 沒有資料，印出 0
    else:  # 反之，印出 books 排序後的內容及 fine
        print(*sorted(books)); print(fine)

ZeroJudge 解題筆記：f818. 物競天擇 (Survival)

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



ZeroJudge 題目連結：f818. 物競天擇 (Survival)

解題想法

這題考排序，需要自訂排序的比較式，因為比較式不像前一題那麼複雜，我是用 lambda function 寫比較式。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 小獅子數量 n
    hs = list(map(int, input().split()))  # 小獅子身高 h
    ws = list(map(int, input().split()))  # 小獅子體重 w
    hw = [(h, w) for h, w in zip(hs, ws)]  # 將 hs, ws 合併成二維串列，資料為 (h, w)
    hw.sort(key = lambda x : x[0]*x[1])  # 將 hw 依照 h*w 由小到大排序
    print(*hw[0])  # 最小值在首項

ZeroJudge 解題筆記：g796. 檔案分類 (Files)

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



ZeroJudge 題目連結：g796. 檔案分類 (Files)

解題想法

這題用字典計數比較方便，如果用 Python 可以用 defaultdict 就不需要檢查 key 值是否存在，但是在輸出答案時要先按照 key 值由小到大排序；如果用 C++ 的 map，本來就會按照 key 值由小到大排序，直接輸出就好。

Python 程式碼

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

import sys
from collections import defaultdict

for line in sys.stdin:
    n = int(line)  # 檔案數量
    cnt = defaultdict(int)  # 計數器
    for _ in range(n):  # 執行 n 次
        cnt[int(input().strip()[3:])//10] += 1  # 讀取字串，去掉 \n，取後 3 位轉成 int
    for k, v in sorted(cnt.items()): print(k, v)  # 印出答案

C++ 程式碼

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

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 檔案數量
    string s;  // 檔案編號
    while(cin >> n) {
        map<int, int> cnt;  // 計數器
        for(int i=0; i<n; i++) {  // 執行 n 次
            cin >> s;  // 讀取編號
            cnt[stoi(s.substr(3))/10]++;  // s 取後 3 位轉成 int
        }
        for(auto it : cnt) cout << it.first << " " << it.second << "\n";  // 印出答案
    }
    return 0;
}

ZeroJudge 解題筆記：f707. 幸運 7 (Lucky Seven)

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



ZeroJudge 題目連結：f707. 幸運 7 (Lucky Seven)

解題想法

這題考排序，需要自訂排序的比較式。

Python 程式碼

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

import sys
from functools import cmp_to_key

def mycmp(a, b):
    if a%7 == 0 and b%7 != 0: return -1  # a 可以被 7 整除但 b 不行，a 往前放
    elif a%7 != 0 and b%7 == 0: return 1  # a 不行被 7 整除但 b 可以，a 往後放
    elif a%7 == 0 and b%7 == 0:  # a、b 都可以被 7 整除
        if a%70 > b%70: return -1  # a 除以 70 的餘數比較大，a 往前放
        elif a%70 < b%70: return 1  # a 除以 70 的餘數比較小，a 往後放
        else: return 0
    else:  # a、b 都不行被 7 整除
        if a%77 < b%77: return -1  # a 除以 77 的餘數比較小，a 往前放
        elif a%77 > b%77: return 1  # a 除以 77 的餘數比較大，a 往後放
        else: return 0

for line in sys.stdin:
    arr = list(map(int, line.split()))[:-1]  # 轉成整數串列並去掉最後一項
    arr.sort(key = cmp_to_key(mycmp))  # 排序
    print(arr[0])  # 最大值在首項

ZeroJudge 解題筆記：f706. 時區 (Zone)

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



ZeroJudge 題目連結：f706. 時區 (Zone)

解題想法

這題需要注意輸出的格式，分、秒如果只有個位數，前面需要補0。

Python 程式碼

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

import sys

d = 5400  # 1h30' = 5400"
a = 129600  # 36h = 129600"
for line in sys.stdin:
    h, m, s, t = map(int, line.split())  # 時、分、秒、向東或西移動幾個時區
    if t == -24 or t == 24:  # 特例，向東或西繞一圈回到原時區
        print(f"{h:d}:{m:02d}:{s:02d}")  # 印出讀到的數值即可，分和秒要有2位數
        continue  # 繼續找下一組
    s += h*3600 + m*60  # 先全部換成秒
    s += t*d  # 依照移動的時區加或減秒數
    s = (s+a)%a  # 處理可能回到前一天或進到下一天的問題
    h = s//3600  # 計算小時
    s %= 3600  # 計算小時之後剩下的秒數
    m = s//60  # 計算分鐘
    s %= 60  # 計算分鐘之後剩下的秒數
    print(f"{h:d}:{m:02d}:{s:02d}")  # 印出答案，分和秒要有2位數

ZeroJudge 解題筆記：f515. 英文縮寫 (Abbreviation)

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



ZeroJudge 題目連結：f515. 英文縮寫 (Abbreviation)

解題想法

我會先將讀取的字串先全部轉換成大寫字母，這樣在檢查特例及組合答案時會比較方便。

Python 程式碼

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

import sys

for line in sys.stdin:
    # 刪除最後的 \n，轉成大寫，用空格分開，轉成串列
    line = list(line.strip().upper().split())
    a = ""  # 儲存答案用的空字串
    for s in line:  # 從 line 依序讀取字串 s
        if s == "FOR": a += "4"  # 先處理特例
        elif s == "TO": a += "2"
        elif s == "AND": a += "n"
        elif s == "YOU": a += "u"
        else: a += s[0]  # 如果不是特例，a 加上 s 開頭的字元
    print(a)  # 印出答案

ZeroJudge 解題筆記：f514. 拼字遊戲 (Spelling)

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



ZeroJudge 題目連結：f514. 拼字遊戲 (Spelling)

解題想法

因為 Python 的字串不能用索引值修改某個字元，轉成串列會比較方便。儲存答案的串列 ans，雖然有些資料是整數、有些是字元，但是串列的資料格式可以混搭，還是可以儲存。而 C++ 的 vector 只能儲存同一種格式的資料，要先將找到的字元位置轉成字串再存入 ans 之中。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = [""] + list(line.strip())  # 將 line 去掉結尾的 \n 轉成串列，開頭加上空格以配合題目的編號從 1 開始
    t = list(sys.stdin.readline().strip())  # 將讀取到的字串去掉結尾的 \n 轉成串列
    ans = []  # 答案
    for c in t:  # 由 t 依序讀取字元 c
        if c in s:  # 如果 c 在 s 之中
            p = s.index(c)  # 找出 c 在 s 中的位置
            ans.append(p)  # p 加入 ans
            s[p] = ""  # s[p] 改為空字串
        else:  # 如果 c 不在 s 之中
            ans.append("X")  # 字串 X 加入 ans
    print(*ans)  # 印出 ans

ZeroJudge 解題筆記：f513. 舉旗遊戲 (Flag)

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



ZeroJudge 題目連結：f513. 舉旗遊戲 (Flag)

解題想法

這題如果在周圍加上 0 作為哨兵，可以在檢查周圍 8 格時不需要考慮是否出界，程式碼會比較簡單。由於 Python 的串列索引值 -1 會對應到最後一項，不需要圍一整圈，只要圍最右側、最下方即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 地圖 m*n
    grid = [list(map(int, input().split())) + [0] for _ in range(m)]  # 地圖，最後加上 0 作為哨兵
    grid.append([0]*(n+1))  # 最後加上 n+1 個 0 作為哨兵
    tot = 0  # 淘汰人數
    for r in range(m):  # 依序檢查每個人
        for c in range(n):
            a = grid[r][c]  # 這個人的顏色 a
            out = True  # 是否淘汰
            for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):  # 檢查周圍 8 格
                nr, nc = r+dr, c+dc  # 要檢查的格子 (nr, nc)
                if grid[nr][nc] == a:  # 如果 (nr, nc) 的顏色與 a 相同
                    out = False; break  # 不會淘汰，中止迴圈
            if out: tot += 1  # 如果淘汰了，tot 加 1
    print(tot)

ZeroJudge 解題筆記：f443. 商品擺設 Merchandise

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



ZeroJudge 題目連結：f443. 商品擺設 Merchandise

解題想法

寫法1，先找到最左側隔板的位置 pre，設定最大值 imax 為 0、最小值 imin 為 1000，接著再繼續往右找，如果這格是商品就更新 imax、imin 及對應的位置 pmax、pmin；再次遇到隔板時，將 pmax、pmin 的商品對調，重置 imax、imin；重複以上的過程直到讀完貨架資料為止。

寫法2，先設定前一個隔板的位置 pre 為 -1，依序掃過每一格，如果在第 i 格遇到隔板而且 pre 不等於 -1，再用 index、max、min 及串列切片找區間最大值、最小值位置。效率會比寫法1差一點。

Python 程式碼

寫法1，使用時間約為 18 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 商品數量
    val = list(map(int, input().split()))  # 商品銷售量
    key = list(map(int, input().split()))  # 商品編號
    i, pre = 0, -1  # 目前正在檢查的位置，前一個隔板的位置
    while val[i] != -1 and i < n: i += 1  # 繼續執行直到遇到第一個隔板或出界為止
    if i < n: pre = i  # 如果還沒有出界，pre 設定為 i
    imax, imin = 0, 1000  # 商品銷售量最大值、最小值
    pmax, pmin = 0, 0  # 商品銷售量最大值、最小值對應的編號
    i += 1  # i 加 1，接下來找下一格
    while i < n:  # 繼續執行直到出界為止
        if val[i] == -1:  # 如果是隔板
            if i - pre > 1:  # 如果這個隔板與前一個隔板距離超過一格
                val[pmax], val[pmin] = val[pmin], val[pmax]  # 交換商品銷售量
                key[pmax], key[pmin] = key[pmin], key[pmax]  # 交換商品編號
                imax, imin = 0, 1000  # 重置商品銷售量最大值、最小值
            pre = i  # pre 設定為 i
        else:  # 如果是商品
            if val[i] > imax:  # 如果是新的最大值
                imax, pmax = val[i], i  # 更新 imax, pmax
            if val[i] < imin:  # 如果是新的最小值
                imin, pmin = val[i], i  # 更新 imin, pmin
        i += 1  # i 加 1
    print(*key)  # 印出最後的商品編號

ZeroJudge 解題筆記：f442. 老鷹抓小雞 Eagle

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



ZeroJudge 題目連結：f442. 老鷹抓小雞 Eagle

解題想法

我將交換小雞、老鷹編號的部分拆開來寫，這樣會比較容易看懂。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 小雞數量
    arr = list(map(int, input().split()))  # 小雞編號
    e = int(input())  # 老鷹編號
    q = int(input())  # 遊戲回合
    tar = list(map(int, input().split()))  # 每回合抓到的小雞編號
    for t in tar:  # 從 tar 依序讀取編號
        i = arr.index(t)  # t 在 arr 中的索引值
        c = t  # 暫存下一回合老鷹編號
        arr[i] = e  # 更新 arr
        e = c  # 更新 e
    print(*arr)  # 印出答案

ZeroJudge 解題筆記：f441. 評分系統 Score

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



ZeroJudge 題目連結：f441. 評分系統 Score

解題想法

因為 Python 一次讀取一行資料，所以在 Python 程式碼中我是用 zip 將正確答案及學生的答案綁在一起讀取。在 C++ 中則是一次讀取一個整數，遇到空格就停下來，可以每次讀一個學生的答案計分。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, s = map(int, line.split())  # 題數 n，每題分數 s
    ans = list(map(int, input().split()))  # 答案
    m = int(input())  # 待批改試卷數量
    for _ in range(m):  # 執行 m 次
        cnt = 0  # 答對題數
        stu = list(map(int, input().split()))  # 學生的答案
        for a, b in zip(ans, stu):  # 由 ans 及 stu 依序讀取資料
            if a == b: cnt += 1  # 如果 a 等於 b，cnt 加 1
        print(cnt*s)  # 印出分數

ZeroJudge 解題筆記：f375. 神奇肥料 Fertilizer

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



ZeroJudge 題目連結：f375. 神奇肥料 Fertilizer

解題想法

按照題目指定規則寫條件即可。注意：每天都可以檢查花的高度，即使是每 9 天的休假日，如果花的高度大於等於顧客要求的高度，仍然可以印出天數。

Python 程式碼

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

import sys

for line in sys.stdin:
    s, e, a = map(int, line.split())  # 起始高度 s、目標高度 e、耐性 a
    h, d = 0, 0  # 增加的高度，天數
    while True:
        s += h; d += 1  # 更新 s 及 d
        if d%11 == 0 and s < e:  # 每隔 11 天而且 s 小於 e
            a -= 1  # a 減 1
            if a == 0:  # 如果 a 等於 0
                print("unsalable"); break  # 印出 unsalable 並中止迴圈
        if s >= e:  # 如果 s 大於等於 e
            print(d); break  # 印出天數並中止迴圈
        else:  # 如果 s 小於 e
            if d%9 == 0 or d%10 == 0: h = 0  # 每隔 9 天或 10 天，h 為 0
            elif d%3 == 0: h = s//3  # 每隔 3 天且不是休假日，h 為 s//3
            else: h = s//10  # 其它天，h 為 s//10

ZeroJudge 解題筆記：f374. 分組 Grouping

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



ZeroJudge 題目連結：f374. 分組 Grouping

解題想法

這題在 Python 我是用 enumerate 搭配字串切片 [::-1] 反向讀取字元，在 C++ 則是用索引值從字串中讀取字元。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, s = line.split()  # 將 line 分割成每組人數 n、戰力 s
    n = int(n)  # 將 n 轉成整數
    idx, imax = 0, 0  # 最大戰力組別、戰力
    group, tot = 1, 0  # 目前的組別、戰力
    for i, c in enumerate(s[::-1]):  # 從 s 最後面往前讀取
        tot += int(c)  # 將 c 轉成整數加到 tot
        if (i+1)%n == 0 or i == len(s)-1:  # 如果 (i+1) 可以被 n 整除或是 i 等於 len(s)-1，檢查小組戰力
            if tot >= imax:  # 如果 tot 大於等於 imax
                imax = tot  # imax 更新為 tot
                idx = group  # idx 更新為 group
            tot = 0; group += 1  # tot 歸零，group 加 1
    print(f"{idx:d} {imax:d}")  # 印出答案

ZeroJudge 解題筆記：f345. 新手練習題—陣列

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



ZeroJudge 題目連結：f345. 新手練習題—陣列

解題想法

這題很簡單，有很多不同的寫法，我盡量列出已知的寫法。

Python 程式碼

寫法 1

先將資料轉成整數儲存到串列中，再用索引值反過來輸出，使用時間約為 1.6 s，記憶體約為 132.6 MB，通過測試。

n = int(input())  # 陣列長度
arr = list(map(int, input().split()))  # 陣列
for i in range(n-1, -1, -1):  # 用索引值反向輸出
    print(arr[i], end="\n" if i == 0 else " ")

寫法 2

直接用字串儲存到串列中，再用索引值反過來輸出，使用時間約為 1.4 s，記憶體約為 106.8 MB，通過測試。

n = int(input())  # 陣列長度
arr = list(input().split())  # 陣列
for i in range(n-1, -1, -1):  # 用索引值反向輸出
    print(arr[i], end="\n" if i == 0 else " ")

寫法 3

先將資料轉成整數儲存到串列中，用串列切片將串列反過來，最後用開箱運算子印出串列內容。使用時間約為 0.9 s，記憶體約為 140.3 MB，通過測試。

_ = int(input())  # 陣列長度，用不到
arr = list(map(int, input().split()))  # 陣列
arr = arr[::-1]  # 用串列切片將陣列反過來
print(*arr)  # 用開箱運算子印出陣列內容

寫法 4

可以將上方的程式碼第3、4行合併。使用時間約為 0.9 s，記憶體約為 147.9 MB，通過測試。

_ = int(input())  # 陣列長度，用不到
arr = list(map(int, input().split()))  # 陣列
print(*arr[::-1])  # 用串列切片將陣列反過來，再用開箱運算子印出陣列內容

寫法 5

將資料轉成整數存到串列中，用 reversed 將串列反過來，最後用開箱運算子印出串列內容。使用時間約為 0.9 s，記憶體約為 140.3 MB，通過測試。

_ = int(input())  # 陣列長度，用不到
print(*reversed(list(map(int, input().split()))))

寫法 6

將寫法 3 改用字串格式，使用時間約為 0.6 s，記憶體約為 109.3 MB，通過測試。

_ = int(input())  # 陣列長度，用不到
arr = list(input().split())  # 陣列
arr = arr[::-1]  # 用串列切片將陣列反過來
print(*arr)  # 用開箱運算子印出陣列內容

寫法 7

將寫法 4 改用字串格式，使用時間約為 0.6 s，記憶體約為 116.7 MB，通過測試。

_ = int(input())  # 陣列長度，用不到
arr = list(input().split())  # 陣列
print(*arr[::-1])  # 用串列切片將陣列反過來，再用開箱運算子印出陣列內容

寫法 8

將寫法 5 改用字串格式，使用時間約為 0.6 s，記憶體約為 109.1 MB，通過測試。

_ = int(input())  # 陣列長度，用不到
print(*reversed(list(input().split())))

寫法 9

如果使用字串格式，還可以用 join 將串列內容用空格連接成一個很長的字串一起輸出，使用時間約為 0.2 s，記憶體約為 120.5 MB，通過測試。

_ = int(input())  # 陣列長度，用不到
print(" ".join(reversed(list(input().split()))))

ZeroJudge 解題筆記：f341. 5.閱讀順序(Reading)

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



ZeroJudge 題目連結：f341. 5.閱讀順序(Reading)

解題想法

這題考字串操作，在 Python 用字串切片很好寫，在 C++ 最好是使用 string 函式庫的 substr 及 algorithm 函式庫的 reverse 會比較好寫。

Python 程式碼

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

def solve(s, x):
    if s == x: return s  # 特例，直接回傳 s
    n, m = len(s), len(x)  # s、x 的長度
    c = s.find(x)  # 翻轉軸於 s 的索引值
    if c == 0:  # x 在開頭
        ri = s[m:]  # 取 x 右側的子字串
        return ri[::-1] + s[:m]  # 將 ri 放在左側並反向，加上 x 左側的子字串
    elif c+m == n:  # x 在結尾
        le = s[:c]  # 取 x 左側的子字事
        return s[c:] + le[::-1]  # x 右側的子字串，加上 le 放在右側並反向 
    else:  # x 在中間
        le, ri = s[:c], s[c+m:]  # 取 x 左、右兩側的子字串
        return ri[::-1] + s[c:c+m] + le[::-1]  # ri 放到左側並反向，le 放在右側並反向

s = input().strip()  # 原來的字串
x = input().strip()  # 翻轉軸
print(solve(s, x))  # 呼叫 solve 並印出答案

ZeroJudge 解題筆記：f340. 4.俄羅斯方塊 (Tetris)

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



ZeroJudge 題目連結：f340. 4.俄羅斯方塊 (Tetris)

解題想法

這題要先寫出各種指令對應的操作，還要檢查方塊是否在邊界使方塊無法旋轉，寫起來很容易出錯。

Python 程式碼

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

# 方向：0 朝右，1 朝下，2 朝左，3 朝上
def bottom(x, y, d):  # 檢查是否已觸底，輸入錨點座標 (x, y)，方向 d
    if d == 3: return y >= n-1  # 朝上，回傳 y 是否大於等於 n-1
    else: return y+1 >= n-1  # 其它方向，回傳 y+1 是否大於等於 n-1
    
def zero(x, y, d):  # 指令 0，方向 d，向下移一格
    return x, y+1, d

def one(x, y, d):  # 指令 1，輸入錨點座標 (x, y)，方向 d，向右、向下移一格
    # 如果「方向朝右、下、上且 x+1 小於 m-1」或是「方向朝左且 x 小於 m-1」，可以向右移一格
    if (d in (0, 1, 3) and x+1 < m-1) or (d == 2 and x < m-1): x += 1
    return x, y+1, d

def two(x, y, d):  # 指令 2，輸入錨點座標 (x, y)，方向 d，向左、向下移一格
    # 如果「方向朝下、左、上且 x-1 大於 0」或是「方向朝右且 x 大於 0」，可以向左移一格
    if (d in (1, 2, 3) and x-1 > 0) or (d == 0 and x > 0): x -= 1
    return x, y+1, d

def three(x, y, d):  # 指令 3，輸入錨點座標 (x, y)，方向 d，置底
    if d == 3: return x, n-1, d  # 朝上，錨點 y = n-1
    else: return x, n-2, d  # 其它方向，錨點 y = n-2

def four(x, y, d):  # 指令 4，輸入錨點座標 (x, y)，方向 d，右旋
    if d == 2 and x == m-1: d = 2  # 朝左且 x 等於 m-1，不能右旋
    elif d == 0 and x == 0: d = 0  # 朝右且 x 等於 0，不能右旋
    else: d = (d+1)%4  # 右旋
    if bottom(x, y, d): return x, y, d  # 如果已經觸底，回傳 x, y, d
    return x, y+1, d  # 否則回傳 x, y+1, d

### 初始化 ###
m, n = map(int, input().split())  # 畫面寬度 m、高度 n
s = int(input())  # 指令數量 s
arr = list(map(int, input().split()))  # 指令
if m%2 == 1: x = (m+1)//2 - 1  # 如果 m 是奇數
else: x = m//2 - 1  # 如果 m 是偶數
y = 0  # 初位置 y 座標
d = 1  # 方向朝下
### 依照指令改變方塊的位置及方向 ###
for a in arr:  # 依序由 arr 讀取指令 a
    if a == 0: x, y, d = zero(x, y, d)  # 指令 0
    elif a == 1: x, y, d = one(x, y, d)  # 指令 1
    elif a == 2: x, y, d = two(x, y, d)  # 指令 2
    elif a == 3: x, y, d = three(x, y, d); break  # 指令 3，執行完畢後中止迴圈
    else: x, y, d = four(x, y, d)  # 指令 4
    if bottom(x, y, d): break  # 如果已經觸底中止迴圈
### 畫出最後的地圖 ###
grid = [[0]*m for _ in range(n)]  # 地圖
if d == 0:  # 朝右
    grid[y-1][x] = grid[y][x] = grid[y+1][x] = grid[y][x+1] = 1
elif d == 1:  # 朝下
    grid[y][x-1] = grid[y][x] = grid[y][x+1] = grid[y+1][x] = 1
elif d == 2:  # 朝左
    grid[y-1][x] = grid[y][x] = grid[y+1][x] = grid[y][x-1] = 1
else:  # 朝上
    grid[y][x-1] = grid[y][x] = grid[y][x+1] = grid[y-1][x] = 1
for g in grid: print(*g, sep='')  # 印出地圖

ZeroJudge 解題筆記：f339. 3.下雪的日子(Snow)

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



ZeroJudge 題目連結：f339. 3.下雪的日子(Snow)

解題想法

有兩個要特別注意的地方：

1. Python 才有的問題，輸入的資料可能是長度等於 1 的字串，要跳過這些字串不處理。
2. 暢通的道路資料可能起點、終點相同，要跳過這些資料不處理。

Python 程式碼

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

import sys
from functools import cmp_to_key

def mycmp(a, b):  # 依照起點由小到大排序，若起點相同，依照終點由大到小排序
    if a[0] < b[0]: return -1
    elif a[0] > b[0]: return 1
    else:
        if a[1] > b[1]: return -1
        elif a[1] < b[1]: return 1
        else: return 0
        
for line in sys.stdin:
    if len(line) <= 1: continue  # 如果字串長度小於等於 1，繼續讀下一行
    n, m = map(int, line.split())  # 道路總長度 n， m 筆道路資訊
    pa = [list(map(int, input().split())) for _ in range(m)]  # 暢通道路
    pa.sort(key = cmp_to_key(mycmp))  # 排序
    ans = []  # 答案
    if pa[0][0] > 0: ans.append((0, pa[0][0]))  # 檢測第0段及 0 之間是否不通
    ri = pa[0][1]  # 目前檢測的右端點
    for s, e in pa[1:]:  # 由 pa[1] 開始依序讀取暢通道路起點 s、終點 e
        if s == e: continue  # 如果 s 等於 e，沒用的資料，繼續找下一段
        if s > ri: ans.append((ri, s))  # 如果 s 大於 ri，中間有不通的地方，(ri, s) 加入 ans
        ri = max(ri, e)  # 更新 ri，取 ri 及 e 較大者
    if n > ri: ans.append((ri, n))  # 最後的右端點與 n 之間不通
    if ans:  # 如果 ans 有內容才印出 ans
        for a in ans: print(*a)

ZeroJudge 解題筆記：f149. 3. 炸彈偵測器 (Detector)

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



ZeroJudge 題目連結：f149. 3. 炸彈偵測器 (Detector)

解題想法

因為在檢查周圍 8 格時可能會出界，造成 index error，所以我習慣在每列最後、最下面或四周加上 0。

Python 程式碼

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

m, n = map(int, input().split())  # 地圖 m*n
grid = [list(map(int, input().split())) + [0] for _ in range(m)]  # 地圖，結尾加上 0 作為哨兵
grid.append([0]*(n+1))  # 地圖最後加上 n+1 個 0 作為哨兵
bomb = set()  # 炸彈位置
found = set()  # 找到的炸彈位置
test = ((-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1))  # 要檢測的周圍 8 格
for r in range(m):  # 依序掃過 r = 0 ~ m-1
    for c in range(n):  # 依序掃過 c = 0 ~ n-1
        if grid[r][c] == 1: bomb.add((r, c))  # 找到炸彈，(r, c) 加入 bomb
        elif grid[r][c] == 5:  # 偵測器
            other = False  # 周圍 8 格是否有其它的偵測器
            tmp = []  # 暫存周圍 8 格的炸彈位置
            for dr, dc in test:  # 依序檢測周圍 8 格
                nr, nc = r+dr, c+dc  # 要檢測的格子 (nr, nc)
                if grid[nr][nc] == 5:  # 其它的偵測器
                    other = True  # other 設定為 True
                    break  # 中止迴圈
                elif grid[nr][nc] == 1:  # 找到炸彈，(nr, nc) 加入 tmp
                    tmp.append((nr, nc))
            if not other:  # 如果周圍 8 格沒有其它的偵測器
                for (nr, nc) in tmp:  # 從 tmp 依序讀取找到的炸彈位置
                    found.add((nr, nc))  # (nr, nc) 加入 found
print(f"{len(found):d} {len(bomb)-len(found):d}")  # 印出答案

ZeroJudge 解題筆記：f148. 2. 定向越野 (Orienteering)

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



ZeroJudge 題目連結：f148. 2. 定向越野 (Orienteering)

解題想法

如果使用 Python，可以將目標點的字母、x 座標、y 座標組成數組，再加到串列之中，排序時會用數組最前面的資料為基準。如果使用 C++，要先自訂結構體，將目標點的字母、x 座標、y 座標存到結構體之中，再放入陣列，排序時可以用 lambda function 指定要以結構體之中的哪一項資料排序。

Python 程式碼

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

w, h = map(int, input().split())  # 地圖 w 列、h 欄
n = int(input())  # 要找 n 個目標
target = []  # 目標，(字母, x, y)
for r in range(w):  # 執行 w 次
    line = list(input().split())  # 讀取一行資料
    for c, s in enumerate(line):  # 從 line 依序讀取字元 s，索引值 c
        if s != '0': target.append((s, r, c))  # 如果 s 不等於 0，(s, r, c) 加入 target
target.sort()  # 依照開頭的字母排序
if len(target) < n:  # 如果 target 數量小於 n
    print("Mission fail.")  # 印出 Mission fail.
else:  # 任務成功，印出 target 前 n 個的座標
    for (_, r, c) in target[:n]:
        print(f"{r:d} {c:d}")

ZeroJudge 解題筆記：f147. 1. 點餐系統 (Ordering System)

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



ZeroJudge 題目連結：f147. 1. 點餐系統 (Ordering System)

解題想法

如果使用 Python，可以把套餐、單點的名稱、價格，分別儲存在一個二維數組之中，也可以全部儲存在一個三維數組之中。但是 C++ 的陣列只能儲存相同格式的資料，如果想要全部儲存在同一個陣列之中，要自訂結構體才行。

Python 程式碼

把套餐、單點的名稱、價格，分別儲存在一個二維數組之中。使用時間約為 39 ms，記憶體約為 3.4 MB，通過測試。

combo = (("", 0), ("Medium Wac", 4), ("WChicken Nugget", 8),
         ("Geez Burger", 7), ("ButtMilk Crispy Chicken", 6), ("Plastic Toy", 3))
dish = (("", 0), ("German Fries", 2), ("Durian Slices", 3),
        ("WcFurry", 5), ("Chocolate Sunday", 7))
tot = 0  # 總金額
while True:
    order = int(input())  # 讀取指令
    if order == 0:  # 當指令等於 0，印出總金額，中止迴圈
        print(f"Total: {tot:d}")
        break
    num = int(input())  # 套餐或單點號碼
    if order == 1:
        print(f"{combo[num][0]:s} {combo[num][1]:d}")
        tot += combo[num][1]
    elif order == 2:
        print(f"{dish[num][0]:s} {dish[num][1]:d}")
        tot += dish[num][1]

ZeroJudge 解題筆記：f072. 3. 家裡的後花園 (Garden)

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



ZeroJudge 題目連結：f072. 3. 家裡的後花園 (Garden)

解題想法

因為某一塊地上面或四周可能有好幾隻害蟲，如果用 list 儲存不能種花的位置可能會重複儲存到同一塊地，所以我改用 set 儲存資料。

Python 程式碼

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

n = int(input())  # 有 n 塊地
arr = list(map(int, input().split()))  # 地形
fence = []  # 柵欄位置
bug = set()  # 因為害蟲不能種花的位置
for i in range(n):  # 依序掃過每一塊地
    if arr[i] == 1: fence.append(i)  # 如果是柵欄，加入 fence
    elif arr[i] == 9:  # 如果是害蟲
        bug.add(i)  # i 加入 bug
        if 0 <= i-1 < n and arr[i-1] == 0: bug.add(i-1)  # 如果 i-1 沒有出界且是空地，加入 bug
        if 0 <= i+1 < n and arr[i+1] == 0: bug.add(i+1)  # 如果 i+1 沒有出界且是空地，加入 bug
tot = 0  # 可以種花的空地總數
for i in range(len(fence)-1):  # 計算可以種花的空地總數
    le, ri = fence[i], fence[i+1]  # 相鄰兩片柵欄的位置
    for j in range(le+1, ri):  # 依序掃過兩片柵欄之間的位置
        if j not in bug: tot += 1  # 如果沒有害蟲，tot 加 1
print(tot)

ZeroJudge 解題筆記：f071. 2. 刮刮樂 (Lottery)

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



ZeroJudge 題目連結：f071. 2. 刮刮樂 (Lottery)

解題想法

注意：同一個號碼可能出現不只一次，金額可能會有好幾個。因為號碼可能不連續，所以我用字典儲存號碼與對應的金額。

Python 程式碼

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

a, b, c = map(int, input().split())  # 幸運數字
key = list(map(int, input().split()))  # 號碼
val = list(map(int, input().split()))  # 金額
lottery = dict()  # {號碼: [金額]}，同一個號碼可能出現不只一次，金額可能會有好幾個
for k, v in zip(key, val):  # 依序讀取 key 及 val
    if k not in lottery: lottery[k] = [v]  # 如果 k 不在 lottery 之中，對應的值為 [v]
    else: lottery[k].append(v)  # 如果 k 在 lottery 之中，對應的值加上 v
tot = 0  # 奬金
if a in lottery:  # 如果 a 在 lottery 之中，加上對應的金額
    for v in lottery[a]:
        tot += v
if b in lottery:  # 如果 b 在 lottery 之中，加上對應的金額
    for v in lottery[b]:
        tot += v
if c in lottery:  # 如果 c 在 lottery 之中，減去對應的金額
    for v in lottery[c]:
        tot -= v
else: tot *= 2  # 如果 c 不在 lottery 之中，tot 加倍
if tot < 0: tot = 0  # 如果 tot 為負值，歸零
print(tot)  # 印出答案

ZeroJudge 解題筆記：f070. 1. 韓信點兵 (HanXin)

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



ZeroJudge 題目連結：f070. 1. 韓信點兵 (HanXin)

解題想法

這題考數學，比較不像考演算法。

Python 程式碼

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

nums = sorted([list(map(int, input().split())) for _ in range(3)], reverse=True)
i = 1  # 倍數
while True:
    n = nums[0][0]*i + nums[0][1]  # 用最大的因數乘以 i 再加上餘數
    # 檢查 n 是否符合另外兩個因數，如果皆符合，印出 n 並中止迴圈
    if (n - nums[1][1])%nums[1][0] == 0 and (n - nums[2][1])%nums[2][0] == 0:
        print(n); break
    i += 1  # i 加 1

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<pair<int, int>> nums (3);
    for(int i=0; i<3; i++) cin >> nums[i].first >> nums[i].second;
    sort(nums.begin(), nums.end(), greater<pair<int, int>> ());
    int i = 1;  // 倍數
    while(true) {
        int n = nums[0].first*i + nums[0].second;  // 用最大的因數乘以 i 再加上餘數
        // 檢查 n 是否符合另外兩個因數，如果皆符合，印出 n 並中止迴圈
        if ((n - nums[1].second)%nums[1].first == 0 && (n - nums[2].second)%nums[2].first == 0) {
            cout << n << "\n"; break;
        }
        i++;  // i 加 1
    }
    return 0;
}

ZeroJudge 解題筆記：f045. 3. 身分驗證機制 (Verification)

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



ZeroJudge 題目連結：f045. 3. 身分驗證機制 (Verification)

解題想法

因為輸入的編號可能會以 0 開頭，要用字串儲存資料，不能用整數。

Python 程式碼

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

s = input().strip()  # 代號
a, b = 0, 0  # 最大的兩個數字
for c in s:  # 由 s 依序讀取字元 c
    c = int(c)  # 轉成整數
    if c >= a:  # 如果 c 大於等於 a，c 是最大值，b 改為原來的 a
        b = a; a = c
    elif c > b: b = c # 如果 c 小於 a 且 c 大於 b，b 改為 c
if a*a + b*b == int(s[-3:]): print("Good Morning!")
else: print("SPY!")

C++ 程式碼

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;  // 代號
    int a = 0, b = 0;  // 最大的兩個數字
    for(char c : s) {  // 由 s 依序讀取字元 c
        int d = c - '0';  // 轉成整數
        if (d >= a) {  // 如果 d 大於等於 a，d 是最大值，b 改為原來的 a
            b = a; a = d;
        } else if (d > b) b = d;  // 如果 d 小於 a 且 d 大於 b，b 改為 d
    }
    if (a*a + b*b == stoi(s.substr(s.size()-3))) cout << "Good Morning!\n";
    else cout << "SPY!\n";
    return 0;
}

ZeroJudge 解題筆記：f044. 2. 史萊姆生態區 (Slime)

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



ZeroJudge 題目連結：f044. 2. 史萊姆生態區 (Slime)

解題想法

要先找到數據的規律，列出前 5 天的數據應該就能寫出數量與天數的關係式。

day	big	small	total
0	1	0	1 = 20
1	1	1	2 = 21
2	1	1 + 2 = 3	1 + 3 = 4 = 22
3	1	3 + 7 = 7	1 + 7 = 8 = 23
4	1	7 + 8 = 15	1 + 15 = 16 = 24
5	1	15 + 16 = 31	1 + 31 = 32 = 25

Python 程式碼

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

n, t = map(int, input().split())  # 史萊姆王、小史萊姆的數量比例
if n > 1:  # 如果 n 大於 1，約分
    t //= n; n = 1
d, s = 0, 1  # 天數，總數
while s < n+t:  # 當 s 小於 n+t
    d += 1  # 天數加 1
    s *= 2  # s 變成 2 倍
print(d)

直接取 $\log_2$，使用時間約為 39 ms，記憶體約為 3.3 MB，通過測試。

import math
n, t = map(int, input().split())  # 史萊姆王、小史萊姆的數量比例
if n > 1:  # 如果 n 大於 1，約分
    t //= n; n = 1
print(int(math.log(n+t, 2)))

ZeroJudge 解題筆記：e975. 3. 情書解密 (Love)

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



ZeroJudge 題目連結：e975. 3. 情書解密 (Love)

解題想法

Python 可以用 find 在字串中找特定的子字串，如果有找到會回傳子字串開頭字元的索引值，沒有找到會回傳 -1；如果用 index 在沒有找到時會跳出錯誤訊息，所以用 find 比較好。

Python 程式碼

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

def test(s):
    for i in range(26):  # 依序測試偏移量 0 ~ 25
        t = ""  # 移動後的字串
        for c in s:  # 依序由 s 讀取字元 c，將 c 的編號 +i 轉成字元存入 t
            if 'A' <= c <= 'Z': t += chr((ord(c)-ord('A')+i)%26 + ord('A'))
            elif 'a' <= c <= 'z': t += chr((ord(c)-ord('a')+i)%26 + ord('a'))
        j = t.find("love")  # 在字串 t 中找 love，回傳索引值 j
        k = t.find("Love")  # 在字串 t 中找 Love，回傳索引值 k
        if j != -1 or k != -1: return i  # 如果 j 或 k 不等 -1，有找到 love 或 Love，回傳 i
    return -1  # 如果跑完以上的 for loop 都沒有回傳值，則回傳 -1 代表沒有找到 love

line = input().strip()  # 讀取一行字串，刪除最後面的 \n
ans = test(line)  # 呼叫 test
if ans >= 0: print(ans)
else: print("-1")

ZeroJudge 解題筆記：e974. 座位安排 (Seats)

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



ZeroJudge 題目連結：e974. 座位安排 (Seats)

解題想法

這題在 Python 用 list 切片比較用索引值好寫，而且速度也快很多。

Python 程式碼

用 list 切片比較好寫，使用時間約為 38 ms，記憶體約為 4.5 MB，通過測試。

r, c, n = map(int, input().split())  # 列數 r，行數 c，週數 n
seat = [list(range(i*c+1, (i+1)*c+1)) for i in range(r)]  # 原來的座位表
for i in range(2, n+1):  # 依序處理第 2 ~ n 週
    if i%2 == 1:  # 單數週，所有人往後移一個座位，原本最後一排的人換到第一排
        seat = [seat[-1]] + seat[:-1]
    else:  # 雙數週，所有人往右橫移一個座位，原本最右邊的人則換到最左邊
        for j in range(r):  # 依序處理第 0 ~ r-1 列
            seat[j] = [seat[j][-1]] + seat[j][:-1]
for row in seat: print(*row)

用索引值設定串列中的值，速度會比用切片慢很多。使用時間約為 0.5 s，記憶體約為 4.5 MB，通過測試。

r, c, n = map(int, input().split())  # 列數 r，行數 c，週數 n
seat = [list(range(i*c+1, (i+1)*c+1)) for i in range(r)]  # 原來的座位表
for i in range(2, n+1):  # 依序處理第 2 ~ n 週
    if i%2 == 1:  # 單數週，所有人往後移一個座位，原本最後一排的人換到第一排
        tmp = seat[-1].copy()  # 第 r-1 列的編號先存到 tmp
        for j in range(r-1, -1, -1):  # 依序處理第 r-1 ~ 0 列
            for k in range(c):  # 依序處理第 0 ~ c-1 行
                if j == 0: seat[j][k] = tmp[k]  # 第 0 列，設定為 tmp
                else: seat[j][k] = seat[j-1][k]  # 其它列，向後移一行
    else:  # 雙數週，所有人往右橫移一個座位，原本最右邊的人則換到最左邊
        for j in range(r):  # 依序處理第 0 ~ r-1 列
            tmp = seat[j][-1]  # 每列第 c-1 行的編號先存到 tmp
            for k in range(c-1, -1, -1):  # 依序處理第 c-1 ~ 0 行
                if k == 0: seat[j][k] = tmp  # 第 j 列第 0 行，設定為 tmp
                else: seat[j][k] = seat[j][k-1]  # 其它行，向右移一行
for row in seat: print(*row)

ZeroJudge 解題筆記：e973. 3. 滿意度調查 (Survey of Satisfaction)

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



ZeroJudge 題目連結：e973. 3. 滿意度調查 (Survey of Satisfaction)

解題想法

這題用 map 和自訂排序用的比較式，寫起來會很方便。

Python 程式碼

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

from collections import Counter
from functools import cmp_to_key

def mycmp(a, b):
    if a[0] > b[0]: return -1  # 如果 a[0] 大於 b[0]，a 往前放
    elif a[0] < b[0]: return 1  # 如果 a[0] nc 於 b[0]，a 往後放
    else:  # 如果 a[0] 等於 b[0]
        if a[1] < b[1]: return -1  # 如果 a[0] 小於 b[0]，a 往前放
        elif a[1] > b[1]: return 1  # 如果 a[0] 大於 b[0]，a 往後放
        else: return 0

cnt = Counter(list(input().strip()))  # 讀取字串，去掉結尾的 \n，轉成 list，傳入計數器
output = sorted([(val, key) for key, val in cnt.items()], key=cmp_to_key(mycmp))  # 讀取 cnt 的資料並排序
for i in range(len(output)):  # 印出答案
    print(output[i][1], end='\n' if i == len(output)-1 else ' ')

ZeroJudge 解題筆記：e972. 1. 貨幣轉換 (Currency)

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



ZeroJudge 題目連結：e972. 1. 貨幣轉換 (Currency)

解題想法

這題的第三筆測資是用 \r 換行，用 Python 解題反而很麻煩。

Python 程式碼

因為第3筆測資是用 \r 分隔資料，這樣寫過不了。

import re
ori = int(input())  # 原有的金額
rem = 0  # 剩下的金額
data = re.split(r"\s+", input())
cost = int(data[0])
if data[1] == 'T': rem = ori - cost  # 台幣
elif data[1] == 'U': rem = ori / 30.9 - cost  # 美金
elif data[1] == 'J': rem = ori / 0.28 - cost  # 日幣
elif data[1] == 'E': rem = ori / 34.5 - cost  # 歐元
if 0 < rem < 0.05: rem = 0.00  # 若 rem 為正數且小於 0.05，改成 0.00 
if rem < 0: print("No Money")  # 如果 rem 小於 0，印出 No Money
else: print(f"{data[1]:s} {rem:.2f}")  # 剩出幣制及餘額

改成這樣才能通過。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

data = input().replace('\r', ' ')  # 將 \r 換成空格
try:
    n = input()
except:  # 為了處理第 3 筆測資，\r 會使游標在換行後移到上一行
    data, a, b = data.split()  # 目的地幣值 b
else:
    a, b = n.split()
    
ori = int(data)  # 原有的金額
cost = int(a)  # 花費
rem = 0  # 剩下的金額

if b == 'T': rem = ori - cost  # 台幣
elif b == 'U': rem = ori / 30.9 - cost  # 美金
elif b == 'J': rem = ori / 0.28 - cost  # 日幣
elif b == 'E': rem = ori / 34.5 - cost  # 歐元
if 0 < rem < 0.05: rem = 0.00  # 若 rem 為正數且小於 0.05，改成 0.00 
if rem < 0: print("No Money")  # 如果 rem 小於 0，印出 No Money
else: print(f"{b:s} {rem:.2f}")  # 剩出幣制及餘額

ZeroJudge 解題筆記：e971. 2. 梗圖著色 (Coloring)

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



ZeroJudge 題目連結：e971. 2. 梗圖著色 (Coloring)

解題想法

只要記錄前一個 1 的位置就好，不需要用到 queue。

Python 程式碼

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

m, n = map(int, input().split())  # 圖的高度 m、寬度 n
for _ in range(m):  # 讀取 m 行資料
    arr = list(map(int, input().split()))  # 一行圖形資料
    pre = -1  # 前一個 1 的位置，預設為 -1
    for i, a in enumerate(arr):  # 由 arr 依序讀取數值 a、索引值 i
        if a == 1:  # 如果 a 等於 1
            if pre != -1:  # 如果 pre 不等於 -1
                for j in range(pre+1, i): arr[j] = 1 # 將 [pre+1, i-1] 之間都設定為 1
                pre = -1  # pre 重設為 -1
            else: pre = i  # 如果 pre 等於 -1，pre 設定為 i
    print(*arr)  # 印出這行塗色後的結果

C++ 程式碼

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n; cin >> m >> n;  // 圖的高度 m、寬度 n
    for(int i=0; i<m; i++) {  // 讀取 m 行資料
        int arr[n] = {0}, pre = -1;  // 一行圖形資料，前一個 1 的位置，預設為 -1
        for(int j=0, a; j<n; j++) {  // 讀取 n 個數值 a
            cin >> a; arr[j] = a;  // 讀取圖形資料
            if (a == 1) {  // 如果 a 等於 1
                if (pre != -1) {  // 如果 pre 不等於 -1
                    for(int k=pre+1; k<j; k++) arr[k] = 1;  // 將 [pre+1, i-1] 之間都設定為 1
                    pre = -1;  // pre 重設為 -1
                } else pre = j;  // 如果 pre 等於 -1，pre 設定為 j
            }
        }
        for(int j=0; j<n; j++) cout << arr[j] << " \n"[j == n-1];  // 印出這行塗色後的結果
    }
    return 0;
}

ZeroJudge 解題筆記：e970. 1. 粉專抽獎 (Lucky Draw)

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



ZeroJudge 題目連結：e970. 1. 粉專抽獎 (Lucky Draw)

解題想法

按照題目敘述的規則計算就好。

Python 程式碼

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

n = int(input())  # 留言量 n
arr = [0] + list(map(int, input().split()))  # n 個隨機數字
b = arr[-1]  # arr 最後一項是基數 b
tot = 0  # 索引值對應到之隨機數字加總
for i in range(1, n+1):  # 依序測試 1 ~ n
    if i%b == 1: tot += arr[i]  # 如果 i 除以 b 的餘數等於 1，將 arr[i] 加到 tot
m = tot%n  # 中獎留言索引值
if m == 0: m = n  # 如果 m 等於 0，最後一則留言中獎，m 改為 n
print(f"{m:d} {arr[m]:d}")  # 印出 m 及 arr[m]

C++ 程式碼

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 留言量 n
    int arr[n+1] = {0};  // n 個隨機數字，為了配合題目的索引值，前面多一個 0
    for(int i=1; i<=n; i++) cin >> arr[i];
    int b = arr[n], tot = 0;  // arr 最後一項是基數 b，索引值對應到之隨機數字加總
    for(int i=1; i<=n; i++) {  // 依序測試 1 ~ n
        if (i%b == 1) tot += arr[i];  // 如果 i 除以 b 的餘數等於 1，將 arr[i] 加到 tot
    }
    int m = tot%n;  // 中獎留言索引值
    if (m == 0) m = n;  // 如果 m 等於 0，最後一則留言中獎，m 改為 n
    cout << m << " " << arr[m] << "\n";  // 印出 m 及 arr[m]
    return 0;
}

ZeroJudge 解題筆記：e969. 大吃大喝 (Big eater)

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



ZeroJudge 題目連結：e969. 大吃大喝 (Big eater)

解題想法

這題要很注意輸出的內容，很容易弄錯一些細節。

Python 程式碼

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

n, m, k = map(int, input().split())
t = 0
food = ("eats an Apple pie", "drinks a Corn soup")
imin = (32, 55)

if n < imin[k]:
    print("Wayne can't eat and drink.")
else:
    while n >= imin[k]:
        n -= imin[k]
        print(f"{t:d}: Wayne {food[k]:s}, and now he ", end="")
        if n == 0: print(f"doesn't have money.")
        elif n == 1: print(f"has 1 dollar.")
        else: print(f"has {n:d} dollars.")
        k = (k+1)%2
        t += m

ZeroJudge 解題筆記：e948. 基礎代謝率 (BMR Calculation)

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



ZeroJudge 題目連結：e948. 基礎代謝率 (BMR Calculation)

解題想法

這題考輸出格式，要輸出小數點後 2 位，如果是用 C++ 可以用 printf 會比較方便。

Python 程式碼

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

n = int(input())  # 人數
for _ in range(n):  # 執行 n 次
    g, a, h, w = map(int, input().split())  # 性別、年齡、身高、體重
    if g == 1:  # 男
        print(f"{13.7*w + 5.0*h - 6.8*a + 66:.2f}")
    else:  # 女
        print(f"{9.6*w + 1.8*h - 4.7*a + 655:.2f}")

C++ 程式碼

使用 iomanip 函式庫的 setprecison 固定輸出的小數點位數。使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 人數
    for(int i=0; i<n; i++) {  // 執行 n 次
        int g, a, h, w; cin >> g >> a >> h >> w;  // 性別、年齡、身高、體重
        float bmr;
        if (g == 1) bmr = 13.7*w + 5.0*h - 6.8*a + 66.0;  // 男
        else bmr = 9.6*w + 1.8*h - 4.7*a + 655.0;  // 女
        cout << fixed << setprecision(2) << bmr << "\n";
    }
    return 0;
}

ZeroJudge 解題筆記：e841. P8. 幽靈寶藏(Treasure)

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



ZeroJudge 題目連結：e841. P8. 幽靈寶藏(Treasure)

解題想法

操作有以下 2 種

1. 在連續的數個藏寶箱內放入 $S$ 枚硬幣。
2. 使連續的數個藏寶箱內的硬幣價值變為 $S$ 倍，包括事後放入的硬幣。

所以操作時不需要考慮先加或是先乘，寫起來會簡單很多。

Python 程式碼

測資很大，第18筆測資開始超時。

n, m = map(int, input().split())  # n 個寶箱，編號 1 ~ n；m 次操作
add = [0]*(n+2)  # 各個寶箱硬幣增加的數量
mul = [1]*(n+2)  # 各個寶箱硬幣乘上的倍數
div = [1]*(n+2)  # 各個寶箱硬幣除掉的倍數
for _ in range(m):  # 讀取 m 次操作
    p, q, r, s = map(int, input().split())  # 範圍 [p, q]，操作種類 r，數量 s
    if r == 1:  # 操作是 1
        add[p] += s  # 編號 p 硬幣加 s
        add[q+1] -= s  # 編號 q+1 硬幣減 s
    elif r == 2:  # 操作是 2
        mul[p] *= s  # 編號 p 硬幣乘上的倍數乘以 s
        div[q+1] *= s  # 編號 q+1 硬幣除掉的倍數乘以 s
# end of for loop
idx, imax = 0, 0  # 最大值的寶箱編號，最大值
cur_val, cur_mul = 0, 1  # 目前的硬幣數量，目前乘上的倍數
for i in range(1, n+1):  # 更新各個寶箱的硬幣數量
    cur_mul = cur_mul * mul[i] // div[i]  # 更新 cur_mul
    cur_val += add[i]  # 更新 cur_val
    cur = cur_val * cur_mul  # 計算硬幣數量
    if cur > imax:  # 如果 cur 較大
        imax = cur  # 更新 imax
        idx = i  # 更新 i
print(f"{idx:d} {imax:d}")

ZeroJudge 解題筆記：e840. P7. 密碼強度測試(Passwords)

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



ZeroJudge 題目連結：e840. P7. 密碼強度測試(Passwords)

解題想法

按照題目給的規則計分就好，不過要注意連續數字的扣分方式，例如 1234，要扣的分數是 $(4-1) \times 2$。

Python 程式碼

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

digit = 0  # 數字數量
letter = 0  # 字母數量
cont = []  # 連續數字
s = input().strip()  # 讀取字串，用 strip 去掉最後的 \0
c1 = s[0]  # 處理 s 開頭的字元
if c1.isdigit():  # 如果 c1 是數字
    digit += 1  # digit 加 1
    cont.append([c1])  # [c1] 加到 cont
elif c1.isalpha(): letter += 1  # 如果 c1 是字母，letter 加 1
# 處理 s[1] ~ s[-1]
for i, c in enumerate(s[1:], start=1):
    if c.isdigit():  # 如果 c 是數字
        digit += 1  # digit 加 1
        if s[i-1].isdigit():  # 如果 s-1 是數字
            cont[-1].append(c)  # c 加到 cont[-1]
        else: cont.append([c])  # 如果 s-1 不是數字，[c] 加到 cont
    elif c.isalpha(): letter += 1  # 如果 c 是字母，letter 加 1
# 計算分數
score = len(s)*3 + letter*3 + digit*2  # 處理長度、字母數量、數字數量
if len(s) >= 8 and digit > 0 and letter > 0: score += 10  # 達最低要求
else: score -= 5  # 未達最低要求
if digit == 0 and letter > 0: score -= letter  # 只有英文字母
if digit > 0 and letter == 0: score -= digit  # 只有數字
for con in cont:  # 依序由 cont 讀取資料 con
    if len(con) > 1: score -= (len(con)-1)*2  # 如果 con 長度大於 1，扣分
print(score)  # 印出分數

ZeroJudge 解題筆記：e839. P6. 飲食分類 (Food)

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



ZeroJudge 題目連結：e839. P6. 飲食分類 (Food)

解題想法

這題用字典儲存各種類食物的名稱會比較方便。

Python 程式碼

使用預設的字典儲存食物名稱、種類。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

n = int(input())  # n 個食物
food = dict()  # 食物種類、名稱
for _ in range(n):  # 讀取 n 行資料
    f, s = input().split()  # 食物名稱 f、種類 s
    if s not in food: food[s] = [f]  # 如果 s 不在 food 之中，food[s] 設定為 [f]
    else: food[s].append(f)  # 如果 s 已經在 food 之中，food[s] 新增 f
t = input().strip()  # 要找的目標
if t not in food: print("No")  # 如果 t 不在 food 之中，印出 No
else:  # 如果 t 在 food 之中，將食物名稱排序後印出
    for f in sorted(food[t]):
        print(f)

改用 collections.defaultdict。使用時間約為 22 ms，記憶體約為 3.6 MB，通過測試。

from collections import defaultdict

n = int(input())  # n 個食物
food = defaultdict(list)  # 食物種類、名稱
for _ in range(n):  # 讀取 n 行資料
    f, s = input().split()  # 食物名稱 f、種類 s
    food[s].append(f)  # food[s] 新增 f
t = input().strip()  # 要找的目標
if t not in food: print("No")  # 如果 t 不在 food 之中，印出 No
else:  # 如果 t 在 food 之中，將食物名稱排序後印出
    for f in sorted(food[t]):
        print(f)

ZeroJudge 解題筆記：e838. P5. 炸彈超人(Bombs)

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



ZeroJudge 題目連結：e838. P5. 炸彈超人(Bombs)

解題想法

這題先將炸彈的位置儲存起來，等讀取完整個地圖資料之後再處理會比較方便。

Python 程式碼

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

n = int(input())  # 地圖為 n*n
bomb = []  # 炸彈位置
grid = []  # 地圖
for i in range(n):  # 讀取 n 行資料
    row = list(input().strip())  # 一行資料，轉成串列
    grid.append(row)  # row 加入 grid
    for j, ch in enumerate(row):  # 依序由 row 讀取字元 ch
        if ch == "*": bomb.append((i, j))  # ch 是炸彈，位置 (i, j) 加入 bomb
for i, j in bomb:  # 讀取炸彈位置 (i, j)，將十字方向上的位置皆改成 *
    for c in range(j, -1, -1): grid[i][c] = "*"
    for c in range(j, n, 1): grid[i][c] = "*"
    for r in range(i, -1, -1): grid[r][j] = "*"
    for r in range(i, n, 1): grid[r][j] = "*"
for row in grid:  # 由 grid 依序讀取整列的資料
    print("".join(row))  # 將 row 接成字串再印出

ZeroJudge 解題筆記：e837. P4. 字母排列 (Letters)

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



ZeroJudge 題目連結：e837. P4. 字母排列 (Letters)

解題想法

這題的說明不精準，題目中說要找按照順序排列的最長字串，實際上是要找按照順序且相鄰字母的最長字串。

Python 程式碼

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

import sys

for s in sys.stdin:
    s = s.strip()  # 去掉最後面的 \0
    now = s[0]  # 目前符合要求的最長字串，先放入 s[0]
    ans = ""  # 答案
    for c in s[1:]:  # 依序讀取 s[1] ~ s[-1]
        if ord(c) == ord(now[-1])+1: now += c # 如果 c 是 now[-1] 的下一個字母，將 c 接到 now 之後
        else:  # 如果 c 不是 now[-1] 的下一個字母
            if len(now) >= len(ans): ans = now  # 如果 now 的長度大於等於 ans 的長度，更新 ans
            now = c  # 更新 now
    if len(now) >= len(ans): ans = now  # 最後要再檢查一次 now 是否比 ans 長
    print(f"{len(ans):d} {ans:s}")  # 印出答案

ZeroJudge 解題筆記：e836. P3. 數字統計 (Counting)

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



ZeroJudge 題目連結：e836. P3. 數字統計 (Counting)

解題想法

這題用字典計數比較方便。

Python 程式碼

可以使用 collections 函式庫的 Counter，這是專門用來計算數量的工具，輸入一個可以迭代的物件，回傳物件中各項資料的數量。使用時間約為 45 ms，記憶體約為 3.8 MB，通過測試。

import sys
from collections import Counter

for line in sys.stdin:
    n = int(line)  # n 個數字
    rs = list(map(int, input().split()))  # 讀取一行數字
    cnt = Counter(rs)  # 計數器
    print(len(cnt))  # 印出不同的數字數量
    imax = max(cnt.values())  # 相同數字最大數量
    if imax < 2: print("NO")  # 沒有重複的數字，印出 NO
    else:  # 否則依照出現順序印出數字
        tmp = []  # 暫存用的串列
        for r in rs:  # 依序由 rs 讀取數字 r
            if cnt[r] == imax and r not in tmp:  # 如果 r 的數量最多而且不在 tmp 之中
                tmp.append(r)  # r 加入 tmp
        print(*tmp)  # 印出 tmp

由於 Counter 的 key 值會依照輸入的物件資料順序排序，上方程式第 11 到 16 行可以改為以下這行，使用時間約為 37 ms，記憶體約為 3.8 MB，通過測試。

else: print(*[key for key, val in cnt.items() if val == imax])

ZeroJudge 解題筆記：e808. 3.不再傻傻等公車 (Bus)

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



ZeroJudge 題目連結：e808. 3.不再傻傻等公車 (Bus)

解題想法

儲存公車到站時刻的串列，先將發車時刻存在開頭，之後各站牌的到站時間編號對應到串列的索引值，這樣寫比較方便。

Python 程式碼

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

n = int(input())  # 公車站牌數量
h, m = map(int, input().split())  # 發車時刻 h:m
time = [[h, m]] + [[0, 0] for _ in range(n)]  # 公車到站時刻
for i in range(1, n+1):  # 讀取 n 行行駛時間
    d = int(input())  # 行駛時間
    mc = time[i-1][1] + d  # 到站時刻 hc:mc
    hc = time[i-1][0]
    if mc >= 60:  # 如果 mc 大於等於 60
        hc += mc//60  # 更新 hc
        mc %= 60  # 更新 mc
    if hc >= 24: hc %= 24  # 如果 hc 大於等於 24，更新 hc
    time[i] = [hc, mc]  # 更新 time[i]
check = list(map(int, input().split()))  # 要查詢的站牌編號，最後一項是 0
for ch in check[:-1]:  # 依序從 check 讀取要查詢的站牌編號，不含最後一項
    print(f"{time[ch][0]:02d}:{time[ch][1]:02d}")

ZeroJudge 解題筆記：e807. 2.降雨量統計 (Rainfall statistics)

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



ZeroJudge 題目連結：e807. 2.降雨量統計 (Rainfall statistics)

解題想法

這題如果會用取最大值及找索引值的工具會很好寫 。

Python 程式碼

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

week = [0]*7  # 一週 7 天每天的累積雨量
quater = [0]*4  # 一天內 4 個時段的累積雨量
for i in range(7):  # 讀取 7 天的雨量
    M, A, N, E = map(float, input().split())
    week[i] = M + A + N + E  # 一天的累積雨量
    quater[0] += M; quater[1] += A  # 更新 4 個時段的累積雨量
    quater[2] += N; quater[3] += E
print(week.index(max(week)) + 1)  # 印出累積雨量最多的是星期幾，要加 1
name = ("morning", "afternoon", "night", "early morning")  # 時段對應的名稱
print(name[quater.index(max(quater))])  # 印出時段名稱

ZeroJudge 解題筆記：e806. 1.多項式計算 (Polynomial)

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



ZeroJudge 題目連結：e806. 1.多項式計算 (Polynomial)

解題想法

這題用 Python 的 dict、defaultdict 或 C++ 的 map、unordered_map 比較方便。

Python 程式碼

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

from collections import defaultdict

n = int(input())  # 第一個多項式資料有 n 對數字
imax = 0  # 最高次方
line1 = list(map(int, input().split()))  # 第一個多項式資料
poly1 = defaultdict(int)  # 用字典儲存第一個多項式的次方、係數
for i in range(0, 2*n, 2):  # 依序由 line1 讀取資料，每次跳 2 格
    poly1[line1[i]] = line1[i+1]
    imax = max(imax, line1[i])
m = int(input())  # 第二個多項式資料有 m 對數字
line2 = list(map(int, input().split()))  # 第二個多項式資料
poly2 = defaultdict(int)  # 用字典儲存第一個多項式的次方、係數
for i in range(0, 2*m, 2):  # 依序由 line2 讀取資料，每次跳 2 格
    poly2[line2[i]] = line2[i+1]
    imax = max(imax, line2[i])
ans = [0]*(imax+1)  # 儲存答案用的串列，依序為 0 ~ imax 次項的係數
for i in range(imax+1):  # 依序讀取兩個多項式 0 ~ imax 次項的係數
    ans[i] = poly1[i] + poly2[i]
if all(ans[i] == 0 for i in range(imax+1)):  # 如果 ans 每項都是 0
    print("NULL!")  # 印出 NULL!
else:  # 否則依序印出次方及係數，若係數為 0 跳過此項
    for i in range(imax, -1, -1):  # 依序印出 imax 次方項 ~ 常數項
        if ans[i] != 0:
            print(f"{i:d}:{ans[i]:d}")

ZeroJudge 解題筆記：e801. p8. 排課表

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



ZeroJudge 題目連結：e801. p8. 排課表

解題想法

這題考貪心法，先將課程依照結束時間由小到大排序，再依序讀取課程是星期幾 w、開始時間 s、結束時間 e，如果星期 w 還沒有選課則加入 (s, e)；如果已經選課而且 s 大於等於 chose[w] 最後一項結束時間，可以選課。

Python 程式碼

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

import sys

for line in sys.stdin:
    N = int(line)  # N 種課程
    course = [list(map(int, input().split())) for _ in range(N)]  # 讀取 N 行
    course.sort(key = lambda x : x[2])  # 依照結束時間由小到大排序
    chose = [[] for _ in range(6)]  # 一週內每天可以的課程開始、結束時間
    for w, s, e in course:  # 依序由 course 讀取課程是星期幾 w、開始時間 s、結束時間 e
        if not chose[w]:  # 如果星期 w 還沒有選課
            chose[w] = [(s, e)]  # 加入 (s, e)
        elif s >= chose[w][-1][1]:  # 如果 s 大於等於 chose[w] 最後一項結束時間，可以選課
            chose[w].append((s, e))  # 加入 (s, e)
    print(sum([len(ch) for ch in chose]))  # 將 chose 所有的項目數量加起來

ZeroJudge 解題筆記：e800. p7. 影片推薦

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



ZeroJudge 題目連結：e800. p7. 影片推薦

解題想法

這題考排序，如果用 Python 解題需要用 functools.cmp_to_key 自訂比較式，如果用 C++ 可以在 sort 裡面用 lambda function 寫比較式，也可以將比較式放在外面。

Python 程式碼

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

from functools import cmp_to_key

def mycmp(a, b):  # 自訂比較用的函式
    pa = a[2]*a[4]*a[5]/a[3]  # a 的優先推薦指數
    pb = b[2]*b[4]*b[5]/b[3]  # b 的優先推薦指數
    if pa > pb: return -1  # 如果 pa 大於 pb，a 往前放
    elif pa < pb: return 1  # 如果 pa 小於 pb，a 往後放
    else:  # 如果 pa 等於 pb
        if a[0] < b[0]: return 1  # 如果 a 的編號較小，a 往前放
        elif a[0] > b[0]: return -1  # 如果 a 的編號較大，a 往後放
        else: return 0  # 如果 a、b 的編號相等，不換順序

N = int(input())  # 影片個數
# 影片資料，內容為 [編號 i, 名稱 S, 觀看人數 P, 影片長度 L, 平均觀看時間 W, 相關係數 R]
data = []
for i in range(1, N+1):  # 讀取 N 行資料
    d = input().split()  # 拆開成串列
    data.append([i, d[0], int(d[1]), int(d[2]), int(d[3]), int(d[4])])  # 加入 data
data.sort(key = cmp_to_key(mycmp))  # 依照 mycmp 排序
for d in data: print(d[1])  # 印出排序後的影片名稱

ZeroJudge 解題筆記：e799. p6. 資工系的浪漫

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



ZeroJudge 題目連結：e799. p6. 資工系的浪漫

解題想法

這題用 Python 解題很方便，因為有內建的函式可以將整數轉換成 2 進位制的字串，如果用 C++ 就要自己寫轉換用的函式。

Python 程式碼

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

import sys

for line in sys.stdin:
    N, M = map(int, line.split())  # 圖形的高 N、寬 M
    C = input().strip()  # 字元 C，要用 strip() 刪除最後的 \n
    for _ in range(N):  # 讀取 N 行數字
        s = bin(int(input()))[2:]  # 讀取數字，用 bin 轉成 2 進位制的字串，刪除開頭的 0b
        if len(s) < M: s = "0"*(M-len(s)) +s  # 若 s 長度小於 M，在前面補 0
        for i, ch in enumerate(s):  # 依序由 s 讀取字元 ch，索引值 i
            if ch == "1": print(C, end="\n" if i == M-1 else " ")  # 如果 ch 是 1 印出符號 C
            else: print(".", end="\n" if i == M-1 else " ")  # 否則印出 .

ZeroJudge 解題筆記：e798. p5. 卷積神經網路

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



ZeroJudge 題目連結：e798. p5. 卷積神經網路

解題想法

可以讀取完整個矩陣的資料再處理最大池化，也可以每讀 2 列矩陣資料就輸出一次最大池化的結果，效率差不多。

Python 程式碼

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

n = int(input())  # 矩陣大小 n*n
mat = [list(map(int, input().split())) for _ in range(n)]  # 讀取矩陣資料
pool = [[0]*(n//2) for _ in range(n//2)]  # 儲存最大池化的結果
for r in range(0, n, 2):  # 依序掃過第 0 ~ n-1 列，每次跳 2 列
    for c in range(0, n, 2):  # 依序掃過第 0 ~ n-1 欄，每次跳 2 欄
        pool[r//2][c//2] = max(mat[r][c], mat[r][c+1], mat[r+1][c], mat[r+1][c+1])  # 取 4 格中的最大值
for row in pool: print(*row)  # 依序印出 pool 每列的資料

每讀取 2 列就輸出 1 次，使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

n = int(input())  # 矩陣大小 n*n
for r in range(0, n, 2):  # 依序掃過第 0 ~ n-1 列，每次跳 2 列
    row1 = list(map(int, input().split()))  # 讀取 2 列
    row2 = list(map(int, input().split()))
    pool = [0]*(n//2)  # 儲存最大池化結果的串列
    for c in range(0, n, 2):  # 依序掃過第 0 ~ n-1 欄，每次跳 2 欄
        pool[c//2] = max(row1[c], row1[c+1], row2[c], row2[c+1])  # 取 4 格中的最大值
    print(*pool)  # 印出 pool 的資料

ZeroJudge 解題筆記：e797. p4. 數位邏輯運算

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



ZeroJudge 題目連結：e797. p4. 數位邏輯運算

解題想法

要小心，每組測資有多筆測試資料。

Python 程式碼

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

import sys

for line in sys.stdin:  # 繼續執行直到沒有資料為止
    N, T = map(int, line.split())  # N 個訊號，T 個時間點
    data = [list(map(int, input().split())) for _ in range(N)]  # 訊號資料
    a, b, c = [0]*T, [0]*T, [0]*T  # AND, OR, XOR 的結果
    for i in range(T):  # 依序檢查 T 個時間點
        one = 0  # 訊號 1 的數量
        for j in range(N):  # 依序檢查 N 個訊號
            if data[j][i] == 1: one += 1  # 訊號 1，one 加 1
        if one == N: a[i] = 1  # 訊號是 N 個 1，a[i] = 1
        if one > 0: b[i] = 1  # 訊號至少有 1 個 1，b[i] = 1
        if one%2 == 1: c[i] = 1  # 訊號是奇數個 1，c[i] = 1
    print("AND:", *a)
    print(" OR:", *b)
    print("XOR:", *c)

ZeroJudge 解題筆記：e796. p3. 站牌廣告

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



ZeroJudge 題目連結：e796. p3. 站牌廣告

解題想法

因為測資範圍不太，在找人流最大值、最小值的站牌編號用線性搜尋，從頭到尾掃過一次即可，效率並不差。

Python 程式碼

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

B = int(input())  # 站牌數量，站牌編號 1 ~ B
P = int(input())  # 人數
cnt = [0]*(B+1)  # 各站牌人流，左端加上一格
for _ in range(P):  # 讀取 P 行資料
    u, v = map(int, input().split())  # 上車、下車站牌編號
    if u > v: u, v = v, u  # 如果 u 大於 v，兩者交換
    for i in range(u, v+1): cnt[i] += 1  # 更新 [u, v] 之間的人流
imax, imin = 0, P+1  # 人流最大值、最小值
pmax, pmin = 0, 0  # 人流最大值、最小值的站牌編號
for i in range(1, B+1):  # 依序檢查站牌 1 ~ B
    if cnt[i] >= imax:  # 如果 cnt[i] 大於等於 imax
        imax = cnt[i]  # 更新 imax
        pmax = i  # 更新 pmax
    if cnt[i] < imin:  # 如果 cnt[i] 小於 imin
        imin = cnt[i]  # 更新 imin
        pmin = i  # 更新 pmin
print(f"{pmin:d} {pmax:d}")  # 印出答案

ZeroJudge 解題筆記：e795. p2.質數日

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



ZeroJudge 題目連結：e795. p2.質數日

解題想法

因為測資範圍不太，在判斷數字 $n$ 是否為質數時，只要用 for 迴圈從 2 開始測試到 $\sqrt{n}$，任何一個數可以整除 $n$ 則 $n$ 不是質數，不需要用太複雜的作法。

Python 程式碼

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

def test(s):  # 輸入日期 s，字串格式，測試其是否為質數日
    while len(s) >= 1 and int(s) >= 2:  # 如果 s 長度大於等於 1，轉成整數大於等於 2，繼續執行
        date = int(s)  # s 轉成 int
        imax = int(date**0.5)  # 測試的上限，date 開根號
        for i in range(2, imax+1):  # 依序測試 2 ~ imax 是否能整除 date
            if date%i == 0: return False  # 如果能整除，回傳 Fasle 並跳出函式
        s = s[1:]  # 刪除 s 開頭的字元
    return True  # 如果能跑完 while 迴圈，s 是質數日，回傳 True

D = int(input())  # D 個日期
for _ in range(D):  # 測試 D 次
    N = input().strip()  # 讀取日期 N
    print(N, end=" ")  # 印出答案
    print("is" if test(N) else "isn't", end="")
    print(" a Prime Day!")

ZeroJudge 解題筆記：e623. 2. PPAP

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



ZeroJudge 題目連結：e623. 2. PPAP

解題想法

這題看起來好像不難，但是編號很容易算錯，尤其是某一輪或是某一組的最後一項。

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  # 如果 n 可以被 m 整除，剛好是某一項物品的最後一個，n 要減 1
    item = n // m  # 物品編號，取 n 除以 m 的整數部分
    if item == 0: print("Pen")  # 印出對應的物品名稱
    elif item == 1: print("Pineapple")
    elif item == 2: print("Apple")
    else: print("Pineapple pen")

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

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



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

解題想法

這題是迴圈的練習題，將 IV 值對應的 CP 值、升級後的 CP 值另外寫成函式，這樣程式碼比較好看。

Python 程式碼

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

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

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

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

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

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



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

解題想法

這題是很單純的算數題，跑 for 迴圈除一下就好了。

Python 程式碼

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

import sys

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

ZeroJudge 解題筆記：a445. 新手訓練系列- 我的朋友很少

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



ZeroJudge 題目連結：a445. 新手訓練系列- 我的朋友很少

解題想法

先用鄰接串列儲存節點之間的連接方式，注意，這題是無向圖，而且測資中某些行可能 兩個一樣的數字，因為不能自己連到自己，要記得排除。
由於題目要問 A 和 B 是否為朋友，只要 A、B 能夠相連就是朋友，理論上可以用 BFS 從 A 開始測試，如果能夠走到 B，兩人就是朋友。但這題要測試很多次，比較有效率的作法是利用併查集及路徑壓縮，先將每個點的父節點都設定成自己，再用 BFS 或是遞迴，從某一個點 n 開始，將所有與 n 相連的點其父節點都設定成 n，檢測時只要看這兩個點的父節點是否相同，就可以知道兩個點是否相連。

Python 程式碼

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

from collections import deque

def rfind(n, r):  # 自訂函式，輸入節點 n，根節點 r，路徑壓縮
    que = deque([n])  # 待走訪佇列，先放入 n
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 最前面讀取並移除資料
        for v in adj[u]:  # 依序讀取與 u 相連的節點 v
            if parent[v] == v:  # 如果 v 還沒有找到父節點
                parent[v] = r  # 將 v 的父節點設定成 r
                que.append(v)  # 將 v 加入 que
# 讀取資料
N, M, Q = map(int, input().split())  # N 個人，M 筆朋友關係，Q 筆詢問
adj = [[] for _ in range(N+1)]  # 人之間的關係，無向圖，人的編號為 1 ~ N
for _ in range(M):  # 讀取 M 行資料
    A, B = map(int, input().split())  # A 和 B 有朋友關係
    if A == B: continue  # 如果 A、B 是同一個人，找下一筆資料
    adj[A].append(B)
    adj[B].append(A)
# 找每個節點的父節點
parent = list(i for i in range(N+1))  # 每個節點的父節點，先設定成自己的編號
for i in range(1, N+1):  # 依序掃過 1 ~ N 號
    if parent[i] == i and adj[i]:  # 如果 i 還沒有找到父節點而且 i 有相連的點
        rfind(i, i)  # 呼叫 rfind，將與 i 相連的點其父節點都設定成 i
# Q 行待測資料
for _ in range(Q):
    A, B = map(int, input().split())  # 要測試的 A 和 B
    print(":)" if parent[A] == parent[B] else ":(")

ZeroJudge 解題筆記：a290. 新手訓練系列 ~ 圖論

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



ZeroJudge 題目連結：a290. 新手訓練系列 ~ 圖論

解題想法

先用鄰接串列儲存節點之間的連接方式，注意，這題是有向圖。由於題目要問城市 A 是否能走到城市 B，用 BFS 從 A 開始測試，如果能夠走到 B，就可以跳出 BFS 並且印出 Yes!!!，如果跑完 BFS 還是沒有走到 B 就印出 No!!!。

Python 程式碼

這題的測資大到 Python 連用 BFS 都過不了。

import sys
from collections import deque

for line in sys.stdin:
    N, M = map(int, line.split())  # N 個城市，M 條道路
    adj = [[] for _ in range(N+1)]  # 有向圖
    for _ in range(M):  # 讀取 M 行資料
        a, b = map(int, input().split())  # 城市 a、b
        adj[a].append(b)  # a 可以走到 b
    A, B = map(int, input().split())  # 起點A、終點 B
    que = deque([A])  # 待走訪佇列，先放入 A
    flag = False  # 是否能走到終點，假設為 False
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 最前面讀取並移除資料
        if u == B:  # 可以走到終點
            flag = True  # flag 設定為 True
            break  # 中止 while 迴圈
        for v in adj[u]: que.append(v)  # 將 u 可以走到的點都加入 que
    print("Yes!!!" if flag else "No!!!")  # 印出答案