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