ZeroJudge 解題筆記：a020. 身分證檢驗

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


ZeroJudge 題目連結：a020. 身分證檢驗

解題想法

英文字母轉換成整數的部分沒有固定的規律，用字典儲存對照會比較簡單。

Python 程式碼

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

letter = {"A": 10, "B": 11, "C": 12, "D": 13, "E": 14, "F": 15,
          "G": 16, "H": 17, "I": 34, "J": 18, "K": 19, "L": 20,
          "M": 21, "N": 22, "O": 35, "P": 23, "Q": 24, "R": 25,
          "S": 26, "T": 27, "U": 28, "V": 29, "W": 32, "X": 30,
          "Y": 31, "Z": 33}

s = input()
first = letter[s[0]]
code = first//10 + first%10*9
for i, c in enumerate(s[1:9], start=1): code += int(c)*(9-i)
code += int(s[-1])
print("real" if code%10 == 0 else "fake")

ZeroJudge 解題筆記：f698. 後序運算式求值

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


ZeroJudge 題目連結：f698. 後序運算式求值

解題想法

依序讀取算式的每個字串，如果是數字就轉成整數存入堆疊；如果是運算符號，從疊堆最上面取出兩個數字，依照運算符號種類計算兩個數字，再將計算結果存入堆疊。最後堆疊裡只會剩下一個整數，就是答案。

Python 程式碼

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

ans = []
for d in input().split():
    if d not in "+-*/":
        ans.append(int(d))
    elif d == "+":
        a = ans.pop(); b = ans.pop()
        ans.append(b + a)
    elif d == "-":
        a = ans.pop(); b = ans.pop()
        ans.append(b - a)
    elif d == "*":
        a = ans.pop(); b = ans.pop()
        ans.append(b * a)
    elif d == "/":
        a = ans.pop(); b = ans.pop()
        ans.append(b // a)
print(ans[0])

ZeroJudge 解題筆記：f377. 運算式轉換

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


ZeroJudge 題目連結：f377. 運算式轉換

解題想法

用堆疊處理算式，同時要注意括號配對的狀況。

Python 程式碼

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

import sys

for line in sys.stdin:
    tmp = []                                 # 暫存運算子及變數的串列
    ans = []                                 # 儲存答案的串列
    for d in line.split():                   # 依序從串列 data 取出字元並儲存到變數 d
        if d == ")":                         # 若 d 為 )
            while tmp[-1] != "(":            # 當 tmp 最後一項不是 ( 繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.pop()                        # 結束 while 迴圈後移除 tmp 最後一項，此時為 (
        elif d == "(":                       # 若 d 為 )
            tmp.append(d)                    # 將 d 加到 tmp 最後面
        elif d in "*/":                      # 若 d 為 */
            while tmp and tmp[-1] in "*/":   # 當 tmp 之中有資料且最後一項為 */ 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        elif d in "+-":                      # 若 d 為 ＋＝
            while tmp and tmp[-1] in "+-*/": # 當 tmp 之中有資料且最後一項為 +-*/ 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        else:                                # 若 d 不為 ()+-*/ 即為變數
            ans.append(d)                    # 直接加到 ans 最後面 
    # 移除 tmp 最後一項並加到 ans 最後面，直到 tmp 無資料時停止
    while tmp: ans.append(tmp.pop())
    print(*ans)

ZeroJudge 解題筆記：a017. 五則運算

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


ZeroJudge 題目連結：a017. 五則運算

解題想法

這題如果用 Python 解題，可以直接用 eval 求值。但是 Online Judge 網站通常不能使用 eval，還是要用堆疊處理算式。

Python 程式碼

由於題目要求用整數計算數值，需要先用 replace 將 / 換成 //。使用時間約為 21 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    print(eval(line.replace("/", "//")))

將所有的程式碼寫在同一行，使用時間約為 21 ms，記憶體約為 3.3 MB，通過測試。

[print(eval(line.replace("/", "//"))) for line in __import__("sys").stdin]

以下是採用 f377. 運算式轉換，將輸入的測資轉成後序運算式，再用 f698. 後序運算式的寫法，由後序運算式求值。使用時間約為 22 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    data = list(line.split())                # 輸入的測資儲存到串列 data
    tmp = []                                 # 暫存運算子及變數的串列
    ans = []                                 # 儲存後序運算資料的串列
    # 由輸入的測資轉成後序運算資料
    for d in data:                           # 依序從串列 data 取出字元並儲存到變數 d
        if d == ")":                         # 若 d 為 )
            while tmp[-1] != "(":            # 當 tmp 最後一項不是 ( 繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.pop()                        # 結束 while 迴圈後移除 tmp 最後一項，此時為 (
        elif d == "(":                       # 若 d 為 )
            tmp.append(d)                    # 將 d 加到 tmp 最後面
        elif d in "*/%":                     # 若 d 為 */%
            while tmp and tmp[-1] in "*/%":  # 當 tmp 之中有資料且最後一項為 */% 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        elif d in "+-":                      # 若 d 為 ＋＝
            while tmp and tmp[-1] in "+-*/%":# 當 tmp 之中有資料且最後一項為 +-*/% 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        else:                                # 若 d 不為 ()+-*/% 即為變數
            ans.append(d)                    # 直接加到 ans 最後面 
        #print("tmp = ", tmp)
        #print("ans = ", ans)
    # 移除 tmp 最後一項並加到 ans 最後面，直到 tmp 無資料時停止
    while tmp: ans.append(tmp.pop())
    # 由處理過的後序運算資料 ans 計算結果
    func = { "+": int.__add__,       # int.__add__(a, b) = a.__add__(b) = a + b
             "-": int.__rsub__,      # int.__rsub__(a, b) = a.__rsub__(b) = b - a 
             "*": int.__mul__,       # int.__mul__(a, b) = a.__mul__(b) = a * b
             "/": int.__rfloordiv__, # int.__rfloordiv__(a, b) = a.__rfloordiv__(b) = b // a
             "%": int.__rmod__       # int.__rmod__(a, b) = a.__rmod__(b) = b % a
            }
    result = []
    for a in ans:
        if a not in "+-*/%":         # 如果 a 不是 +-*/% 則為數字
            result.append(int(a))    # 加到 result 最後面
        else:   # 如果 a 是 +-*/% 其中一個，代入字典物件 func 轉成對應的函式，取出 result 最後兩個元素並代入求值
            result.append(func[a](result.pop(), result.pop()))
    print(result[0])

ZeroJudge 解題筆記：a034. 二進位制轉換

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


ZeroJudge 題目連結：a034. 二進位制轉換

解題想法

因為 Python 有內建整數轉成二進位字串的工具 bin，可以直接用 bin 解題。比較一般的作法是用 while 迴圈及位元運算，從個位數開始依序計算此位是 1 或 0，用字串儲存答案。

Python 程式碼

先用 int 將輸入字串 line 轉成整數，再用 bin 轉成2進位制，但是直接輸出時開頭會有 **0b**，所以再用 str 轉換成字串，只從索引值為2的位置開始輸出。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。
使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    print(str(bin(int(line)))[2:])

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

import sys

def convert(n):
    s = ""
    while n > 0:
        s = str(n&1) + s
        n >>= 1
    return s

for line in sys.stdin:
    print(convert(int(line)))

ZeroJudge 解題筆記：a015. 矩陣的翻轉

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


ZeroJudge 題目連結：a015. 矩陣的翻轉

解題想法

用二維陣列儲存矩陣資料，輸出時將列、欄的順序反過來就行了。

Python 程式碼

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

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 矩陣 m*n
    matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
    for c in range(n):
        for r in range(m):
            print(matrix[r][c], end="\n" if r == m-1 else " ")

ZeroJudge 解題筆記：a013. 羅馬數字

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


ZeroJudge 題目連結：a013. 羅馬數字

解題想法

這題最麻煩的地方在於 900、400、90、40、9、4 的轉換，分別換成 CM、CD、XC、XL、IX、IV。程式碼寫起來很長，我想不到更精簡的寫法。

Python 程式碼

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

import sys

# 羅馬數字字串 s 換成整數
def rton(s):
    # 字母換成對應的整數
    cton = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1}
    n = n1 = cton[s[0]]  # 第1位數
    for c in s[1:]:  # 依序讀取 s[1] ~ s[-1]
        n2 = cton[c]  # 對應的整數 n2
        if n2 > n1:  # 如果 n2 較大，n 加上 n2，減掉 2 倍 n1
            n = n - 2*n1 + n2
        else:  # 反之，直接加上 n2
            n = n + n2
        n1 = n2  # 更新 n1
    return n  # 回傳 n

# 整數換成羅馬數字
def ntor(n):
    s = ""  # 儲存結果用的空字串
    # 處理 1000 的倍數
    M = n//1000; s += "M"*M; n %= 1000
    # 處理 500 的倍數
    D = n//500; s += "D"*D; n %= 500
    # 處理 100 的倍數
    C = n//100; n %= 100
    if C == 4 and D == 1:  # 900
        s = s[:-1]  # 刪除最後一位
        s += "CM"  # 加上 "CM"
    elif C == 4 and D == 0:  # 400
        s += "CD"  # 加上 "CM"
    else: s += "C"*C  # 其它狀況，加上 C 個 "C"
    # 處理 50 的倍數
    L = n//50; n %= 50
    if L == 1: s += "L"  # 如果 L 等於 1，加上 "L"
    # 處理 10 的倍數
    X = n//10; n %= 10
    if X == 4 and L == 1:  # 90
        s = s[:-1]  # 刪除最後一位
        s += "XC"  # 加上 "XC"
    elif X == 4 and L == 0:  # 40
        s += "XL"  # 加上 "XL"
    else: s += "X"*X  # 其它狀況，加上 X 個 "X"
    # 處理 5 的倍數
    V = n//5; n %= 5
    if V == 1: s += "V"  # 如果 V 等於 1，加上 "V"
    # 處理 1
    I = n
    if I == 4 and V == 1:  # 9
        s = s[:-1]  # 刪除最後一位
        s += "IX"  # 加上 "IX"
    elif I == 4 and V == 0:  # 4
        s += "IV"  # 加上 "IV"
    else: s += "I"*I  # 其它狀況，加上 I 個 "I"
    # 回傳結果
    return s

for line in sys.stdin:
    if line.rstrip() == "#": break
    a, b = line.split()  # 羅馬數字 a, b
    na, nb = rton(a), rton(b)  # 轉成整數 na, nb
    diff = abs(na - nb)  # 差值
    print("ZERO" if diff == 0 else ntor(diff))

ZeroJudge 解題筆記：e925. pD. 學號檢查

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


ZeroJudge 題目連結：e925. pD. 學號檢查

解題想法

要檢查 4 個部分：

1. 大學部學號開頭要是 B
2. s[1], s[2] 必須是數字
3. s[3:7] 要在院、系、所的集合之中
4. s[7], s[8] 必須是數字

Python 程式碼

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

n = int(input())  # n 個院、系、組
dep = set(input() for _ in range(n))  # 院、系、組編號
cnt = 0  # 不合法的學號數量
for _ in range(10):  # 讀取 10 行資料
    s = input()  # 學號
    # 大學部學號開頭要是 B，s[1:3] 必須是數字，s[3:7] 要在 dep 之中，s[7:] 必須是數字
    if s[0] == 'B' and s[1:3].isdigit() and s[3:7] in dep and s[7:].isdigit():
        print("Y")  # 合法，印出 Y
    else:
        print("N")  # 不合法，印出 N
        cnt += 1  # 不合法的數量加 1
if cnt == 0: print("0")  # 全部合法，印出 0
elif cnt == 10: print("1")  # 全部不合法，印出 1
else: print(f"0.{cnt:d}")  # 其它狀況，印出 0.X

ZeroJudge 解題筆記：a010. 因數分解

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


ZeroJudge 題目連結：a010. 因數分解

解題想法

因為測資 n 不大，依序測試 2 ~ n 是否為因數，如果這個數字 i 是因數就繼續除下去，同時將 n 縮小為 n/i，直到 n 不能被整除為止，就能夠得到因數及對應的次方。

Python 程式碼

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

n = int(input())  # 要測試的數
ans = []  # 答案
fac = 2  # 要測試的因數，從 2 開始
""" 找因數及次方 """
while n > 1 and fac <= n:  # 如果 n 大於 1 且 fac 小於等於 n，還可以分解，繼續執行
    cnt = 0  # 次方
    while n%fac == 0:  # 如果 n 可以被 fac 整除，繼續執行
        cnt += 1; n //= fac  # 次方加 1，n 變為除以 fac 的值
    if cnt == 1:  # 如果次方等於 1
        ans.append(f"{fac:d}")  # ans 加入 fac
    elif cnt > 1:  # 如果次方大於 1
        ans.append(f"{fac:d}^{cnt:d}")  # ans 加入 fac 及次方
    fac += 1  # fac 加 1
""" 輸出答案 """
if not ans: print(n)  # 如果 ans 是空的，n 是質數，印出 n
else: print(" * ".join(ans))  # 反之，用 " * " 連接 ans 再輸出

ZeroJudge 解題筆記：a006. 一元二次方程式

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


ZeroJudge 題目連結：a006. 一元二次方程式

解題想法

先找判別式 $D = b^2 - 4ac$，如果 $D > 0$ 有相異實根，如果 $D = 0$ 為重根，如果 $D < 0$ 沒有實根。如果在 Python 可以用 math.sqrt 或是 0.5 次方開根號，如果在 C++ 可以用 cmath 函式庫的 sqrt 開根號。

Python 程式碼

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

import math

a, b, c = map(int, input().split())
D = b**2 - 4*a*c

if D > 0:
    x1 = int((-b + math.sqrt(D))/(2*a))
    x2 = int((-b - math.sqrt(D))/(2*a))
    print(f"Two different roots x1={x1:d} , x2={x2:d}")
elif D == 0:
    x = int(-b/(2*a))
    print(f"Two same roots x={x:d}")
else:
    print("No real root")

ZeroJudge 解題筆記：a005. Eva 的回家作業

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


ZeroJudge 題目連結：a005. Eva 的回家作業

解題想法

用迴圈檢查前 4 項是等差或等比數列，再補上第 5 項，最後輸出這 5 項。

Python 程式碼

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

t = int(input())
for _ in range(t):
    arr = list(map(int, input().split()))
    state = True  # True 為等差, False 為等比
    d = arr[1] - arr[0]  # 公差
    for i in range(1, 3):  # 檢查 arr[1] ~ arr[3]
        if arr[i+1] - arr[i] != d:  # 如果差不相等，為等比數列
            state = False
            break
    if state:  # 等差數列
        arr.append(arr[3] + d)
    else:  # 等比數列，題目保證是整數
        arr.append(arr[3] * (arr[3] // arr[2]))
    print(*arr)

ZeroJudge 解題筆記：p902. 凱撒密碼 (Cipher)

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


ZeroJudge 題目連結：p902. 凱撒密碼 (Cipher)

解題想法

用字母的 ASCII 編號平移後再除以 26 取餘數，換成平移後的字母。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = line.strip()  # 要加密的字串
    k = int(input())  # 位移量
    a = ""  # 儲存答案用的空字串
    for c in s:  # 從 s 依序讀取字元 c
        if c.islower():  # 如果 c 是小寫字母
            c = chr((ord(c)+k-ord('a'))%26 + ord('a'))
        elif c.isupper():  # 如果 c 是大寫字母
            c = chr((ord(c)+k-ord('A'))%26 + ord('A'))
        a += c  # a 加上 c
    print(a)

ZeroJudge 解題筆記：a981. 求和問題

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


ZeroJudge 題目連結：a981. 求和問題

解題想法

這題要用遞迴窮舉所有的組合，輸出其中符合條件的組合，並且要適當地剪枝，節省運算時間。不過我在 Python 一直沒有寫出能夠過關的程式碼，最後一筆測資超時。

Python 程式碼

最後一筆測資超時。

def solve():
    import sys
    lines = sys.stdin.readlines()
    head = 0
    while head < len(lines):
        n, m = map(int, lines[head].split())  # 讀取數量 n，要找的加總 m
        nums = sorted(list(map(int, lines[head+1].split())))  # 讀取候選的數值
        head += 2  # 從 lines 讀取資料的索引值
        choice = [False]*n  # 是否選這個數字
        have_ans = False  # 是否有解
        ### 主要的解題過程，輸入目前檢測的 nums 索引值，加總 ###
        def backtrack(curr, total):
            nonlocal have_ans  # 這樣才能改變外層 have_ans 的值
            if total == m:  # 有解，印出選擇的數字，結束遞迴
                have_ans = True
                solution = " ".join([str(num) for i, num in enumerate(nums) if choice[i]])
                sys.stdout.write(f"{solution}\n")
                return
            if curr == n or total > m: return # 已出界或是目標為負值，結束遞迴
            choice[curr] = True  # 選此項
            backtrack(curr + 1, total + nums[curr])  # 遞迴，索引值加 1，total 加上此項的值
            choice[curr] = False  # 回溯，不選此項
            backtrack(curr + 1, total)  # 遞迴，索引值加 1，total 不變
        ### End of backtrack ###
        backtrack(0, 0)  # 從索引值 0、加總 0 開始
        if not have_ans: sys.stdout.write("-1\n")  # 如果無解，印出 -1
        
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：p901. 香料 (Spices)

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


ZeroJudge 題目連結：p901. 香料 (Spices)

解題想法

這題用字典儲存每個編號的香料在貨架上的位置，速度較慢但程式好寫。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個要找的香料
    si = list(map(int, input().split()))  # 要找的香料編號
    r, c = map(int, input().split())  # 貨架 r*c
    shelf = [list(map(int, input().split())) for _ in range(r)]  # 貨架上的香料編號
    table = dict()  # 各編號香料的位置
    for i in range(r):  # 依序掃過貨架每一格
        for j in range(c):
            table[shelf[i][j]] = (i+1, j+1)  # 題目的編號從 1 開始
    for s in si:  # 依序讀取要找的香料編號
        if s not in table: print(-1)  # 如果 s 不在 table 之中印出 -1
        else: print(*table[s])  # 反之印出編號

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