ZeroJudge 解題筆記：d574. 節約符咒

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


ZeroJudge 題目連結：d574. 節約符咒

解題想法

第4筆測資只有一行，用空格分隔數量與字串，用 Python 解題需要特別處理。依序讀取字串中每個字母，計算連續出現的相同字母數量，將數量與對應的字母組成字串。

Python 程式碼

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

line = list(input().split())  # 讀取一行資料並用空格分隔存成串列
n = int(line[0])  # 字串長度
if len(line) == 1: s = input().strip()  # 如果 line 只有一項，再讀取一行字串
else: s = line[1]  # 反之，字串在 line[1]
t = ""  # 儲存答案用的空字串
cnt = 1  # 連續相同字母的數量，預設為 1
last = s[0]  # 前一個字母，預設為 s[0]
for c in s[1:]:  # 依序讀取 s[1] ~ s[n-1]
    if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
    else:  # 反之，結算之的連續相同字母數量
        t += str(cnt) + last  # cnt 轉成字串加上 last，接到 t 之後
        cnt = 1  # cnt 重置為 1
        last = c  # last 重置為 c
t += str(cnt) + last  # 最後要再結算一次 cnt 與 last
if len(t) < n: print(t)  # 如果 t 較短，印出 t
else: print(s)  # 反之，印出 s

ZeroJudge 解題筆記：d566. 秒殺率

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


ZeroJudge 題目連結：d566. 秒殺率

解題想法

這題要注意：

1. 此處的解題紀錄排在前面的資料代表時間越晚
2. 第 4 筆測資格式有問題，全部塞在同一行，用 Python 解題需要特別處理這筆測資。

Python 程式碼

理論上這樣寫應該要過關，但是第 4 筆測資格式有問題，全部塞在同一行，要再修改程式碼。

cnt = dict()  # 計數器，是否 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # AC 人數
n = int(input())  # n 筆資料
data = [input().split() for _ in range(n)]  # 先讀完所有的資料
for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
    if name not in cnt:  # 如果 name 不在 cnt 之中
        if state == "AC":  # 如果第一次就 AC
            fir += 1  # fir 加 1
            ac += 1  # ac 加 1
            cnt[name] = True  # cnt[name] 為 True
        else:  # 第一次沒有 AC
            cnt[name] = False  # cnt[name] 為 False
    elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
        ac += 1  # ac 加 1
        cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

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

import sys

cnt = dict()  # 計數器，是否第一次就 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # 全部 AC 的人數
for line in sys.stdin:  # 讀資料直到 EOF 為止
    data = line.split()  # 先試著分割資料
    if len(data) == 1:  # 如果只有一筆，是 n
        n = int(data[0])
        data = [input().split() for _ in range(n)]  # 先讀完所有的資料
        for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
    else:  # 為了測資 4 全部塞在一行的狀況
        n = int(data[0])
        for i in range(2*n, 0, -2):  # 反向讀取資料，先讀取時間較早的資料
            name, state = data[i-1], data[i]
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

ZeroJudge 解題筆記：d563. 等值首尾和

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


ZeroJudge 題目連結：d563. 等值首尾和

解題想法

題目敘述有兩個問題：

1. 題目雖然說有兩行測資，第一行為一個數字 N，代表第二行有 N 個用空格分隔的數字，但實際上只有一行，如果用 Python 解題會出事。
2. 範例的寫法看起來好像從左、右加總的數量要一樣，但其實不需要，只要前綴和、後綴和相等就好，不看數量。

Python 程式碼

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

arr = list(map(int, input().split()))[1:]  # 讀取一行資料轉成串列，不取首項
psum = 0  # 前綴和
cand = set()  # 可能的加總
for a in arr:  # 依序讀取 arr 的資料
    psum += a  # 更新 psum
    cand.add(psum)  # psum 加入 cand
ssum = 0  # 後綴和
cnt = 0  # 答案
for a in arr[::-1]:  # 反向讀取 arr 的資料
    ssum += a  # 更新 ssum
    if ssum in cand: cnt +=1  # 如果 ssum 在 cand 之中，cnt 加 1
print(cnt)  # 印出 cnt

ZeroJudge 解題筆記：d561. 被秒殺的四捨五入

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


ZeroJudge 題目連結：d561. 被秒殺的四捨五入

解題想法

這題在 Python 可以用 decimal 函式庫作弊，將數值存成 Decimal 格式的浮點數再四捨五入即可。比較正常的作法，是用字串格式儲存數字，依序判斷數字的正負號、整數位、小數點後第一位、小數點後第二位，最後再依照小數點後第三位的值判斷是否要捨去或進位。

Python 程式碼

用 decimal 函式庫作弊，使用時間約為 24 ms，記憶體約為 3.9 MB，通過測試。

from decimal import Decimal, ROUND_HALF_UP
import sys

for line in sys.stdin:
    # 將 line 轉成 Decimal 格式的十進位數字，4捨5入到小數點後第2位
    n = Decimal(line.strip()).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)
    if str(n) == "-0.00":
        print("0.00")  # -0.00 要輸出為 0.00
    else:
        print(n)

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

import sys

for line in sys.stdin:
    s = line.strip()  # 字串格式的數字
    negative = False  # 是否為負值，預設為 False
    if s[0] == '-':  # 如果 s[0] 是負號
        negative = True  # negative 設定為 True
        s = s[1:]  # 刪除 s[0]
    num = int(s[0])  # 取整數位加到 num
    s = s[2:]  # 刪除整數位、小數點
    if s and s[0] != '0':  # 處理小數點後第 1 位
        num += int(s[0])*0.1
    s = s[1:]  # 刪除 s[0]
    if s and s[0] != '0':  # 處理小數點後第 2 位
        num += int(s[0])*0.01
    s = s[1:]  # 刪除 s[0]
    if negative: num = -num  # 如果是負值，乘以 -1
    if s and s[0] in '56789':  # 如果 s[0] 大於等於 5，要 4 捨 5 入
        if negative: num -= 0.01  # 如果是負值，減 0.01
        else: num += 0.01  # 如果是正值，加 0.01
    if str(num) == "-0.0": print("0.00")  # 如果轉成字串等於 -0.0，要印出 0.00
    else: print(f"{num:.2f}")

使用 Python 及 C++ 産生重複數字的所有排列方式

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

前言

由於最寫連續寫到好幾個題目，需要從測資讀取一列數字，再産生這列數字的所有排列方式，例如 d762. 10344 - 23 out of 5。我之前都是用 Python 的 itertools.permutations 偷懶，但是為了準備之後的課程，還是來研究一下如何用遞迴及回溯産生所有的排列方式。

Python itertools.permutations

這是一個效率很好的迭代器，官方說明書在此 itertools.permutations，通常會搭配 for 迴圈一起使用，語法為

for [産生的數組名稱] in itertools.permutations(可以迭代的物件):

例如要産生 [1, 2, 3, 2, 1] 的所有排列方式可以這樣寫

from itertools import permutations

nums = [1, 2, 3, 2, 1]
for perm in permutations(nums):
    print(*perm)

如果只考慮 5 個數字的排列方式，總共會有 $5! = 120$ 種，以上的程式碼會輸出 120 行。但是這裡面有不少重複的結果，如果只想輸出不重複的結果，可以再稍微修改一下程式碼，用集合記錄已經産生過的結果，這樣就只會輸出 30 行。

from itertools import permutations

nums = [1, 2, 3, 2, 1]
used = set()
for perm in permutations(nums):
    if perm in used: continue
    used.add(perm)
    print(*perm)

ZeroJudge 解題筆記：d555. 平面上的極大點

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


ZeroJudge 題目連結：d555. 平面上的極大點

解題想法

先讀取所有點的座標存入二維串列 points，由大到小排序。用變數 max_y 記錄目前最高的 y 座標，預設值為負無窮大。從 points 之中依序讀取點的座標 x, y，如果符合以下兩種狀況，將 (x, y) 加入答案 ans 之中：

1. y 大於 max_y
2. ans 之中沒有任何一個點可以支配 (x, y)

最後將 ans 排序再印出。

Python 程式碼

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

import sys

ca = 0
for line in sys.stdin:
    ca += 1
    print(f"Case {ca:d}:")
    n = int(line)
    point = sorted([tuple(map(int, input().split())) for _ in range(n)], reverse=True)
    ans = []  # 答案
    max_y = -float('inf')  # 目前最高的 y 座標，預設為極小值
    for x, y in point:  # 從 point 依序讀取點的座標 (x, y)
        if y > max_y:  # y 大於 max_y
            ans.append((x, y))  # (x, y) 加入 ans
            max_y = y  # 更新 max_y
        # 另一種可能性，ans 之中沒有任何點可以支配 (x, y)
        elif not any(px >= x and py >= y for px, py in ans):
            ans.append((x, y))
    ans.sort()  # 由小到大排序
    print(f"Dominate Point: {len(ans):d}")
    for x, y in ans: print(f"({x:d},{y:d})")

ZeroJudge 解題筆記：d526. Binary Search Tree (BST)

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


ZeroJudge 題目連結：d526. Binary Search Tree (BST)

解題想法

這題要自訂二元樹類別，遞迴版比較簡潔。

Python 程式碼

遞迴版，使用時間約為 0.7 s，記憶體約為 4 MB，通過測試。

class Node:  # 自訂節點類別
    def __init__(self, data):
        self.data = data  # 資料
        self.left = None  # 左子樹
        self.right = None  # 右子樹

class BST:  # 自訂二元搜尋樹類別
    def __init__(self):
        self.root = None  # 根節點

    def insert(self, data):  # 插入節點
        if self.root is None:  # 如果沒有根節點
            self.root = Node(data)  # 設定根節點
        else:  # 如果有根節點
            self._insert(data, self.root)  # 遞迴，代入 data 及 self.root

    def _insert(self, data, current):  # 內部使用的插入方法
        if data < current.data:  # 如果要插入的資料小於目前節點的資料
            if current.left is None:  # 如果沒有左子樹
                current.left = Node(data)  # data 放在左子樹
            else:  # 如果有左子樹
                self._insert(data, current.left)  # 遞迴，代入 data 及左子樹
        elif data > current.data:  # 如果要插入的資料大於目前節點的資料
            if current.right is None:  # 如果沒有右子樹
                current.right = Node(data)  # data 放在右子樹
            else:  # 如果有右子樹
                self._insert(data, current.right)  # 遞迴，代入 data 及右子樹
    
    def delete(self, data):  # 刪除資料
        self.root = self._delete(self.root, data)
    
    def _delete(self, current, data):  # 內部使用的刪除資料方法
        if current is None:  # 如果 current 是空的
            return current  # 回傳 current 並離開函式
        # 找要刪除的節點
        if data < current.data:  # 如果要刪除的資料小於目前節點的資料
            current.left = self._delete(current.left, data)  # 遞迴，代入左子樹及 data
        elif data > current.data:  # 如果要刪除的資料大於目前節點的資料
            current.right = self._delete(current.right, data)  # 遞迴，代入右子樹及 data
        else:  # 找到要刪除的節點
            if current.left is None:  # 如果左子樹是空的
                return current.right  # 用右子樹取代 node
            elif current.right is None:  # 如果右子樹是空的
                return current.left  # 用左子樹取代 node
            # 有左、右子樹
            temp = self._findMin(current.right)  # 找右子樹中最小資料的節點
            current.data = temp.data  # current 的資料改成 temp 的資料
            current.right = self._delete(current.right, temp.data)  # 刪除右子樹中最小資料的節點
        return current
    
    def _findMin(self, current):  # 內部使用的找最小值方法
        while current.left is not None:  # 向下找左子樹直到空節點為止
            current = current.left
        return current
    
    def preorder(self):  # 前序走訪
        self._preorder(self.root)
        print()

    def _preorder(self, current):  # 內部使用的前序走訪
        if current:  # 如果 current 不是 None
            print(current.data, end=' ')  # 印出 current.data
            self._preorder(current.left)  # 遞迴，代入左子樹
            self._preorder(current.right)  # 遞迴，代入右子樹

import sys

for line in sys.stdin:
    n = int(line)  # 一行有 n 個數字
    tree = BST()  # 建立 BST 物件
    for data in map(int, input().split()):  # 依序讀取此行的數字
        tree.insert(data)  # 將資料插入 tree 之中
    tree.preorder()  # 前序走訪

ZeroJudge 解題筆記：d326. 程式設計師的面試問題(二)

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


ZeroJudge 題目連結：d326. 程式設計師的面試問題(二)

解題想法

這題考二進位制補數的觀念，用 C++ 的 bitset 寫起來超快。

Python 程式碼

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

import sys

def negative(num):  # 輸入 10 進位負整數，輸出其補數加 1
    s = bin(num)[3:]  # 轉成 2 進位制字串，刪除開頭的 -0b
    s = s.zfill(32)  # 前面補 0 到 32 位數
    t = ''  # 儲存輸出結果的空字串
    for c in s:  # 從 s 依序讀取字元 c
        if c == '0': t += '1'  # 如果 c 是 0，將 1 加到 t
        else: t += '0'  # 如果 c 是 1，將 0 加到 t
    return int(t, 2)+1  # 將 t 轉回整數、加 1，再回傳

result = []
for line in sys.stdin:
    v, a ,b = map(int, line.split())  # 要計算的整數 v，第 a 位數改成 b
    if v < 0:  # 如果 v 是負數
        vb = f"{negative(v):032b}"  # 呼叫 negative 代入 v 計算結果，再用 format 輸出成 32 位數的 2 進位制整數字串
    else:  # 反之，直接用 format 輸出成 32 位數的 2 進位制整數字串
        vb = f"{v:032b}"
    ans = f"{vb[:31-a]}{b:d}{vb[32-a:]}\n"  # 用切片將第 a 位數換成 b
    result.append(ans)
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d244. 一堆石頭

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


ZeroJudge 題目連結：d244. 一堆石頭

解題想法

這題我是用字典計數，再用另一個集合記錄編號，如果某個編號的石頭有 3 個，將編號從集合中移n除，集合中最後只剩下一個編號，這個編號就是答案。如果是用 Python 解題，可以用 collections 函式庫中的 Counter，這個物件的速度更快。

Python 程式碼

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

from collections import Counter

cnt = Counter(map(int, input().split()))  # 計數器
for k, v in cnt.items():  # 依序由 cnt 讀取 key 與 value
    if v == 2:  # 如果 v 等於 2
        print(k); break  # 印出 k，中止迴圈

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

cnt = dict()  # 計數器
nums = set()  # 數字集合
for v in map(int, input().split()):  # 依序讀取值
    if v not in cnt:  # 如果 v 不在 cnt 之中
        cnt[v] = 1  # cnt[v] 等於 1
        nums.add(v)  # v 加入 nums
    else: cnt[v] += 1  # 如果 v 在 cnt 之中，cnt[v] 加 1
    if cnt[v] == 3: nums.remove(v)  # 如果 cnt[v] 等於 3，從 nums 中移除
print(*nums)  # nums 只剩一個值，就是答案

ZeroJudge 解題筆記：d212. 東東爬階梯

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


ZeroJudge 題目連結：d212. 東東爬階梯

解題想法

先找規律，假設走到第 $i$ 階的走法存在表格 $dp[i]$ 之中。

1. 走到第 0 階、第 1 階，只有一種走法，即 $dp[0] = 1, dp[1] = 1$。
2. 走到第 2 階，可以先走到第 1 階再往上走 1 階，也可以從第 0 階直接往上走 2 階，有 2 種走法，即 $dp[2] = dp[1] + dp[0] = 2$。
3. 走到第 3 階，可以先走到第 2 階再往上走 1 階，也可以先走到第 1 階直接往上走 2 階，有 3 種走法，即 $dp[3] = dp[2] + dp[1] = 3$。
4. 走到第 4 階，可以先走到第 3 階再往上走 1 階，也可以先走到第 2 階直接往上走 2 階，有 5 種走法，即 $dp[4] = dp[3] + dp[2] = 5$。
5. 走到第 $i$ 階，可以先走到第 $i-1$ 階再往上走 1 階，也可以先走到第 $i-2$ 階直接往上走 2 階，即 $dp[i] = dp[i-1] + dp[i-2]$。

看到這裡應該已經發現了，答案就是費氏數列。因為這題有多筆測資，而且題目範圍不大，最多到 99 階，所以先建表算出走到第 0 階至走到第 99 階的走法，讀取一個數量 $n$ 之後再查表找答案，這樣會比較快。

Python 程式碼

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

import sys

dp = [0]*100  # 建表，內容為走到指定階數的走法
dp[0] = dp[1] = 1  # 第 0 階、第 1 階，只有一種走法
for i in range(2, 100): dp[i] = dp[i-1] + dp[i-2]  # 第 2 階開始，走法等於前兩項的和

for n in sys.stdin: print(dp[int(n)])  # 讀取 n 代入 dp 找答案

ZeroJudge 解題筆記：d166. 反轉表

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


ZeroJudge 題目連結：d166. 反轉表

解題想法

實際上有多筆測資，讀取到 EOF 才停止，如果整行只有一個 -1 要 continue 不能 break。 倒著往回讀資料，像是範例中的資料為

2 3 6 4 0 2 2 1 0

共有 9 個數字，代表 1 ~ 9 前面各有幾個數字比自己還大，因為最後一位是 9，前面不可能有比 9 大的數，因此資料中這格一定是 0，先將 9 放到儲存答案的陣列之中。

9

倒數第 2 位代表 8，前面有 1 位比 8 大的數字，代表 8 放在 9 後面，因此陣列為

9 8

倒數第 3 位代表 7，前面有 2 位比 7 大的數字，代表 7 放在最後面，因此陣列為

9 8 7

倒數第 4 位代表 6，前面有 2 位比 6 大的數字，代表 6 放在 7、8 之間，因此陣列為

9 8 6 7

倒數第 5 位代表 5，前面沒有比 5 大的數字，代表 5 放最前面，因此陣列為

5 9 8 6 7

我們可以看出，位數對應的值代表這個位數要插入陣列中的索引值，依照這個方式寫程式碼即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    rev = tuple(map(int, line.split()))  # 反轉表
    n = len(rev)  # n 個數字
    if n == 1 and rev[0] == -1: continue  # 如果整行只有 -1，讀下一筆
    arr = []  # 輸出答案用的串列
    for i in range(n, 0, -1):  # 倒著讀反轉表
        arr.insert(rev[i-1], i)  # 依照反轉表的值將位數插入 arr 之中
    print(*arr)  # 印出 arr

ZeroJudge 解題筆記：d119. 有獎徵答：換零錢

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


ZeroJudge 題目連結：d119. 有獎徵答：換零錢

解題想法

這題考動態規畫，使用的硬幣及鈔票面額有 (1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000)，先計算總金額為 0 ~ 50000 元所有的硬幣及鈔票面額組合數，再依照讀到的測資總金額查表、輸出答案。

Python 程式碼

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

dp = [0]*(50001)  # 0 ~ 50000 各種金額組合數
dp[0] = 1  # 沒有用任何硬幣，1 種組合數
coins = (1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000)  # 可用的面額，要由小到大排序

for coin in coins:  # 依序讀取各種面額
    for j in range(coin, 50001):  # 依序更新 dp[coin] ~ dp[50000]
        dp[j] += dp[j - coin]  # dp[j] 的方法數要加上 dp[j - coin]

while True:
    arr = list(map(int, input().split()))  # 讀取一行資料
    if len(arr) == 1 and arr[0] == 0: break  # 如果 arr 長度為 1 而且等於 0，中止迴圈
    print(dp[sum(arr)] - 1)  # 查表找答案，要扣掉題目給的 1 種組合

ZeroJudge 解題筆記：d115. 數字包牌

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


ZeroJudge 題目連結：d115. 數字包牌

解題想法

這題通常是用自訂函式及遞迴，窮舉所有的組合。如果用 Python 解題，可以使用迭代器 itertools.combinations。這題的測資不太，看起來兩者效率差不多。

Python 程式碼

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

def solve(idx, arr, maxdepth, choose):
    if len(choose) + len(arr) - idx < maxdepth:  # 如果剩下的數字不夠用，跳出函式
        return
    if len(choose) == maxdepth:  # 如果 choose 長度等於 maxdepth，印出 choose
        print(*choose); return
    for i in range(idx, len(arr)):  # 依序讀取 arr[idx] ~ arr[-1]
        choose.append(arr[i])  # arr[i] 加入 choose
        solve(i+1, arr, maxdepth, choose)  # 遞迴，idx 改成 i+1
        choose.pop()  # 移除 choose 最後一筆資料

while True:  # 無窮迴圈
    line = list(map(int, input().split()))  # 讀取一行資料
    if len(line) == 1 and line[0] == 0: break  # 如果只有一個 0，中止迴圈
    n, m = line[0], line[-1]  # n 個數取 m 個
    arr = sorted(line[1:-1])  # 可用的數字
    solve(0, arr, m, [])  # 呼叫 solve 解題
    print("")  # 最後要換行

ZeroJudge 解題筆記：c669. missing and duplicate

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


ZeroJudge 題目連結：c669. missing and duplicate

解題想法

先讀取數列，將數列由小到大排序，取最小值 $imin$、最大值 $imax$、項數 $n$，等差數列加總理論值 $$ theory = \frac{(imin + imax) \times n}{2} $$ 如果實際上的數列加總為 $isum$，兩者相減 $$ diff = theory - isum = 缺少的項 - 重複的項 $$ 再用 set 刪除數列中重複的項，計算 set 的加總 $sum(uni)$，重複的項 $$ dup = isum - sum(uni) $$ 最後可以得到缺少的項 $$ mis = diff + dup $$

Python 程式碼

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

T = int(input())
for _ in range(T):
    arr = sorted(list(map(int, input().split())))  # 排序後的數列
    imin, imax, n = arr[0], arr[-1], len(arr)  # 最小值、最大值、數量
    isum = sum(arr)  # arr 的加總
    theory = (imin + imax) * n // 2  # 理論上的等差數量加總
    diff = theory - isum  # arr 加總與理論值的差
    uni = set(arr)  # 刪除重複的數字
    dup = isum - sum(uni)  # 重複的數字
    mis = dup + diff  # 遺失的數字
    print(mis, dup)

ZeroJudge 解題筆記：c665. 進制轉換

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


ZeroJudge 題目連結：c665. 進制轉換

解題想法

先建立兩個對照表，table 是串列格式，用來找出 0 ~ 35 對應的字元；val 是字典格式，用來找出 0 ~ 35 字元對應的數值。用自訂函式 convert，將 a 進位制的字串 s 先轉換成 10 進位制的整數 d，再將 d 轉換成 b 進位制的字串 t。

Python 程式碼

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

import sys

# 0 ~ 35 對應的字元表格
table = [str(i) for i in range(10)]
for i in range(26): table.append(chr(i+ord('A')))

# 0 ~ 35 字元對應的數值
val = dict()
for i in range(10): val[str(i)] = i
for i in range(26): val[chr(i+ord('A'))] = i+10

# 主要的解題過程，a 進位制字串 s，轉成 b 進位制
def convert(s, a, b):
    d = 0  # 10 進位制的數字
    base = 1  # a 進位制基底
    for c in s[::-1]:  # 依序讀取 s[-1] ~ s[0]
        d += val[c]*base  # 更新 d
        base *= a  # 更新 base
    t = ""  # 儲存轉換後結果的空字串
    while d:  # 如果 d 大於 0 繼續執行
        t = table[d%b] + t  # d%b 代入 table 找出對應的字元
        d //= b  # 更新 d
    return t  # 回傳 t

for line in sys.stdin:
    n, b1, b2 = line.split()
    b1 = int(b1); b2 = int(b2)
    print(convert(n, b1, b2))

ZeroJudge 解題筆記：c658. 小新的提款卡密碼

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


ZeroJudge 題目連結：c658. 小新的提款卡密碼

解題想法

先列出 1 ~ $10^{10}$ 之間的完全平方數 sq，將 sq 之中數字 0 ~ 9 的數量組成字串 dig，用字典儲存資料，以 dig 作為 key，以 sq 作為 value。讀取測資時，直接從表格中找出對應的答案，如果不在表格之中則印出 0。

Python 程式碼

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

import sys

def digits(num):  # 計算整數 0 ~ 9 的數量
    cnt = [0]*10  # 計數器
    for c in num: cnt[int(c)] += 1  # 從 nu 依序讀取字元 c 計算數量
    return "".join([str(i) for i in cnt])  # 取出 cnt 的資料組成字串再回傳

table = dict()  # 各種 0 ~ 9 出現數量對應的完全平方數
for i in range(1, 100000):  # 題目最大到 1E10，表格只要算 1 ~ 100000-1
    sq = i*i  # i 平方
    dig = digits(str(sq))  # 轉成 0 ~ 9 的數量字串
    if dig not in table: table[dig] = [sq]  # 如果 dig 不在 table 之中，新增 [sq]
    else: table[dig].append(sq)  # 反之，串列加入 sq

for line in sys.stdin:  # 讀取字串直到 EOF 為止
    dig = digits(line.strip())  # 計算 0 ~ 9 的數量
    if dig not in table: print(0)  # 如果 dig 不在 table 之中印出 0
    else: print(*table[dig])  # 反之印出 table[dig]

ZeroJudge 解題筆記：c657. 最長連續字母

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


ZeroJudge 題目連結：c657. 最長連續字母

解題想法

依序讀取字串內容，如果這一個字母與前一個字母相同，連續相同字母長度加1；反之，更新最大值，重設連續相同字母長度為1。讀取完最後一個字母之後， 要再更新一次最大值。

Python 程式碼

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

import sys

for line in sys.stdin:
    line = line.strip()  # 讀取一行字串
    imax, cnt = 0, 1  # 最長連續字母長度，目前的連續字母長度
    ans = last = line[0]  # 答案對應的字母，目前的字母，預設為 line[0]
    for c in line[1:]:  # 依序讀取 line[1] ~ line[-1]
        if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
        else:  # 如果 c 不等於 last
            if cnt > imax:  # 如果 cnt 大於 imax
                imax = cnt; ans = last  # 更新 imax, ans
            cnt = 1; last = c  # 重設 cnt, last
    if cnt > imax:  # 最後要再檢查一次
        imax = cnt; ans = last
    print(ans, imax)  # 印出答案

ZeroJudge 解題筆記：c560. SF 愛運動

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


ZeroJudge 題目連結：c560. SF 愛運動

解題想法

用動態規畫解題，假設 $dp[i]$ 代表走到第 $i$ 階的方法數，走到第 1 階、1 種方法；走到第 2 階、1 種方法；走到第 3 階、2 種方法；走到第 4 階以上、$dp[i] = dp[i-1] + dp[i-3]$。

Python 程式碼

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

n, m = map(int, input().split())
ss = list(map(int, input().split()))
MOD = 1000000007
dp = [0]*(n+1)
dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2
for i in range(4, n+1): dp[i] = (dp[i-1] + dp[i-3]) % MOD
now, ans = 0, 1
for s in ss:
    ans = (ans * dp[s-now]) % MOD
    now = s

ans = (ans * dp[n-now]) % MOD
print(ans)

ZeroJudge 解題筆記：c440. Bert Love QQ !

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


ZeroJudge 題目連結：c440. Bert Love QQ !

解題想法

由左向右依序讀取字元，目前讀到的 Q 總數為 tq，左側的 Q 加權後數量為 lq。讀到 Q 時答案 ans 加上 lq，並將 tq 加 1；讀到 A 時將 lq 加上 tq，相當於讀到第2個A時，第1個A左側的Q有效數量為2倍。

Python 程式碼

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

s = input()  # 要測試的字串
n = len(s)  # 字串長度
ans, lq, tq = 0, 0, 0  # 答案ans，左側Q的數量lq，Q的總數tq 
for c in s:  # 依序取出字元
    if c == 'Q':  # 如果讀到 Q
        ans += lq  # ans 加上 lq
        tq += 1  # tq 加 1
    elif c == 'A':  # 如果讀到 A
        lq += tq  # lq 加上 tq
# end of for loop
print(ans)  # 印出答案

ZeroJudge 解題筆記：c435. MAX ! MAX ! MAX !

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


ZeroJudge 題目連結：c435. MAX ! MAX ! MAX !

解題想法

假設陣列 d 共有 n 項，用變數 small 記錄目前的最小值，變數 large 記錄目前的最大值，兩者預設值皆為 d[0]。由左向右掃過 d[1] ~ d[n-1]，如果 d[i] 小於 small，找到新的最小值，可能有新的答案；如果 d[i] 大於 large，重設 small 及 large。

Python 程式碼

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

n = int(input())  # 數量 n
d = list(map(int, input().split()))  # 要檢測的資料 d
small = large = d[0]  # 目前的最小值 small、最大值 large，先預設為 d[0]
ans = tmp = 0  # 答案 ans，暫存差距用的 tmp，先預設為 0
for i in range(1, n):  # 依序檢測 d[1] ~ d[n-1]
    if d[i] < small:  # 如果 d[i] 小於 small
        small = d[i]  # 更新 small 為 d[i]
        ans = max(large - small, tmp)  # ans 更新為 large - small 及 tmp 較大者
    elif d[i] > large:  # 如果 d[i] 大於 large
        tmp = ans  # 先將 ans 暫存到 tmp
        small = large = d[i]  # 更新 small、large 為 d[i]
# end of for loop
print(ans)  # 印出答案

ZeroJudge 解題筆記：c364. 我鄙視你

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


ZeroJudge 題目連結：c364. 我鄙視你

解題想法

從每個人開始，向左、向右各找一次遞減序列。

Python 程式碼

從第9筆測資開始超過記憶體上限。

n = int(input())  # 人數
hs = [1000000001] + list(map(int, input().split())) + [1000000001]  # 身高，兩端加上很大的值
pre = [0]*(n+2)  # 前綴和
st = [0]  # 左側較高的人編號，先放入0
ans = [0]*(n+2)  # 每個人對應的答案，先預設為0
for i in range(1, n+1):  # 依序掃過第 1 ~ n 個人
    pre[i] = pre[i-1] + hs[i]  # 計算前綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] = pre[i-1] - pre[st[-1]]  # 更新答案為第 i-1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

post = [0]*(n+2)  # 後綴和
st = [n+1]  # 右側較高的人編號，先放入n+1
for i in range(n, 0, -1):  # 依序掃過第 n ~ 1 個人
    post[i] = post[i+1] + hs[i]  # 計算後綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] += post[i+1] - post[st[-1]]  # 更新答案為第 i+1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

for i in range(1, n+1): print(ans[i])  # 印出答案

ZeroJudge 解題筆記：c356. Justin 愛加密

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


ZeroJudge 題目連結：c356. Justin 愛加密

解題想法

這題記憶體只有 16 MB，據說 Python 至少要用 32MB，如果記憶體太少一定會遇到 RE: code 127。要用 cstdio 函式庫中的 fgets，每次讀取指定長度的字元，這樣才能過關。

Python 程式碼

超過記憶體上限。

n = int(input())
s = input()
m = len(s)
d = -1
w = m//n
for i in range(0, m, n):
    d = (d+1)%w
    print(s[i+d], end="")
print()

ZeroJudge 解題筆記：c317. 硬幣問題！前傳

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


ZeroJudge 題目連結：c317. 硬幣問題！前傳

解題想法

原則上盡量用面額最大的硬幣，這樣使用的硬幣總數會越少。

Python 程式碼

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

n = int(input())
for _ in range(n):
    x, a, b = map(int, input().split())
    na = x//a  # 硬幣 a 的數量
    x %= a  # x 剩下的數值
    nb = x//b  # 硬幣 b 的數量
    if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
        print(na+nb)  # 找到答案，印出 na+nb
    else:  # 否則要測試將硬幣 a 換回來的狀況
        while na > 0:  # 如果還有硬幣 a
            na -= 1  # na 減 1
            x += a  # x 加 a
            if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
                nb = x//b  # 找到硬幣 b 正確的數量
                break  # 中止 while 迴圈
        # 如果 x 可以被 b 整除印出 na+nb，否則印出 -1
        print(na+nb if x%b == 0 else "-1")

ZeroJudge 解題筆記：c315. I, ROBOT 前傳

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


ZeroJudge 題目連結：c315. I, ROBOT 前傳

解題想法

依序讀取測資並更新位置即可。

Python 程式碼

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

n = int(input())
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
x, y = 0, 0
for _ in range(n):
    a, b = map(int, input().split())
    x += dirs[a][0]*b
    y += dirs[a][1]*b
print(f"{x:d} {y:d}")

C++ 程式碼

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int x = 0, y = 0;
    for(int i=0; i<n; i++) {
        int a, b; cin >> a >> b;
        x += dirs[a][0]*b;
        y += dirs[a][1]*b;
    }
    cout << x << " " << y << "\n";
    return 0;
}

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

#include <cstdio>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int x = 0, y = 0;
    for(int i=0; i<n; i++) {
        int a, b; scanf("%d %d", &a, &b);
        x += dirs[a][0]*b;
        y += dirs[a][1]*b;
    }
    printf("%d %d\n", x, y);
    return 0;
}

ZeroJudge 解題筆記：c276. 沒有手機的下課時間

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


ZeroJudge 題目連結：c276. 沒有手機的下課時間

解題想法

其實就是猜數字。先掃過一次，找出位置、數字皆正確的部分，再掃過一次，找出數字對、位置錯的部分。

Python 程式碼

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

ans = input()  # 答案
n = int(input())  # 猜測次數
for _ in range(n):  # 執行 n 次
    guess = input()  # 猜測的數字
    a, b = 0, 0  # 位置數字皆正確的個數 a，只有數字正確的個數 b
    ar, gr = [], []  # ans 及 guess 中檢測完位置及數字後剩下的部分
    for i in range(4):  # 先掃過一次
        if guess[i] == ans[i]:  # 位置數字皆正確
            a += 1  # a 加 1
        else:  # 否則將此位數加入 ar 及 gr
            ar.append(ans[i])
            gr.append(guess[i])
    for g in gr:  # 由 gr 依序取出數字
        if g in ar:  # 如果 ar 之中有 g 
            b += 1  # b 加 1
            ar.pop(ar.index(g))  # 將 ar 之中的 g 移除一個
    print(f"{a:d}A{b:d}B")  # 印出答案

ZeroJudge 解題筆記：c184. 盈虧互補

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


ZeroJudge 題目連結：c184. 盈虧互補

解題想法

先找出 n 包含 1 的因數 fac 及加總 facSum，如果 facSum 等於 n，n 是完全數；如果 facSum 不等於 n，還要再找 facSum 的因數 fac2 及加總 facSum2，如果 facSum2 等於 n，則兩者是友好數。

Python 程式碼

用 set 儲存因數，用 join 組合要輸出的因數加總算式。使用時間約為 39 ms，記憶體約為 3.5 MB，通過測試。

n = int(input())  # 要測試數字 n
fac = {1}  # 儲存 n 的因數，先放入 1
for i in range(2, int(n**0.5)+1):
    if n%i == 0:
        fac.add(i)
        fac.add(n//i)
facSum = sum(fac)  # n 的因數加總
print("+".join(map(str, sorted(fac))) + "=" + f"{facSum:d}")  # 印出 n 的因數及加總
if n == facSum:  # 如果 n 等於 facSum
    print(f"{n:d} is perfect.")  # n 是完全數
elif len(fac) == 1:  # 如果 fac 只有 1
    print("=0")  # 印出 =0
    print(f"{n:d} has no friends.")  # 不可能有友好數
else:  # 其它狀況
    n2 = facSum  # 要檢測 facSum 是否為友好數
    fac2 = {1}  # 儲存 n2 的因數，先放入 1
    for i in range(2, int(n2**0.5)+1):
        if n2%i == 0:
            fac2.add(i)
            fac2.add(n2//i)
    facSum2 = sum(fac2)  # n2 的因數加總
    print("+".join(map(str, sorted(fac2))) + "=" + f"{facSum2:d}")  # 印出 n2 的因數及加總
    if facSum2 == n:  # 如果 facSum2 等於 n，兩者是友好數
        print(f"{n:d} and {n2:d} are friends.")
    else:  # 否則 n 沒有友好數
        print(f"{n:d} has no friends.")

ZeroJudge 解題筆記：b911. 我想跟Kevin借筷子系列4

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


ZeroJudge 題目連結：b911. 我想跟Kevin借筷子系列4

解題想法

先列出幾種可能性

1. n = 0, data = [0], ans = 0
2. n = 1, data = [1], ans = 1
3. n = 2, data = [1, 2] => [0, 1] => [0, 0], ans = 2
4. n = 3, data = [1, 2, 3] => [1, 0, 1] => [0, 0, 0], ans = 2
5. n = 4, data = [1, 2, 3, 4] => [1, 0, 1, 2] => [0, 0, 0, 1] => [0, 0, 0, 0], ans = 3
6. n = 5, data = [1, 2, 3, 4, 5] => [1, 2, 0, 1, 2] => n = 2 的狀況，ans = 1 + 2 = 3
7. n = 6, data = [1, 2, 3, 4, 5, 6] => [1, 2, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
8. n = 7, data = [1, 2, 3, 4, 5, 6, 7] => [1, 2, 3, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
9. n = 8, data = [1, 2, 3, 4, 5, 6, 7, 8] => [1, 2, 3, 0, 1, 2, 3, 4] => n = 4 的狀況，ans = 1 + 3 = 4

找出規律，數量 n 如果可以除以 2 則 ans 加 1，直到 n = 1 時 ans 加 1 或是 n = 2 時 ans 加 2。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)
    ans = 0
    while n >= 1:
        if n == 1:
            ans += 1
            break
        elif n == 2:
            ans += 2
            break
        else:
            ans += 1
            n //= 2
    print(ans)

與上方的寫法邏輯相同，但改用遞迴，使用時間約為 24 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    def solve(x, a=0):
        if x == 1: return 1
        if x == 2: return 2
        return 1 + solve(x//2, a)
    # end of def
    print(solve(n))

ZeroJudge 解題筆記：b897. 10219 - Find the ways !

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


ZeroJudge 題目連結：b897. 10219 - Find the ways !

解題想法

這題就是在計算組合數 $$ C^n_k = \frac{n!}{(n-k)! k!} = \frac{n(n-1)(n-2) \dots (n-k+1)}{k(k-1)(k-2) \dots \times 2 \times 1} $$ 取 $\log_{10}$ $$ \begin{align*} ans &= \log_{10} n + \log_{10} (n-1) + \log_{10} (n-2) + \dots + \log_{10} (n-k+1) \\ & ~~~~- (\log_{10} k + \log_{10} (k-1) + \log_{10} (k-2) + \dots + 0) \end{align*} $$ 最後再無條件進位到整數即為答案。
改用史特靈公式取近似，由其中一個表達式史特靈級數 $$ \ln n! = n \ln n - n + \frac{1}{2} \ln (2 \pi n) + \frac{1}{12n} - \frac{1}{360n^3} + \dots $$ 若忽略高次項並用換底公式換成以10為底的對數 $$ \begin{align*} \frac{\log_{10} n!}{\log_{10} e} &= n \cdot \frac{\log_{10} n}{\log_{10} e} - n + \frac{1}{2} \cdot \frac{\log_{10} (2 \pi n)}{\log_{10} e} \\ \log_{10} n! &= n \log_{10} n - n \log_{10} e + \frac{1}{2} \log_{10} (2 \pi) + \frac{1}{2} \log_{10} n \\ \log_{10} n! &\approx (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \end{align*} $$ 因此 $C^n_k$ 取 $\log_{10}$ $$ \begin{align*} & \\ \log_{10} C^n_k \approx & (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \\ & - [(n-k + 0.5) \log_{10} (n-k) - 0.4343 (n-k) + 0.39909] \\ & - [(k + 0.5) \log_{10} k - 0.4343 k + 0.39909] \end{align*} $$ 但是上式的第二行中有 $\log_{10}(n-k)$，當 $n=k$ 時會出問題，程式碼之中需要排除這個特例。

Python 程式碼

理論上用 math 函式庫中的 comb 可以很方便地計算組合數，但是這個函式在 Python 3.8 才加入，ZeroJudge 網站的 Python 版本為 3.6.9，不能用。

from math import comb, log10, ceil
import sys

for line in sys.stdin:
    n, k = map(int, line.split())
    print(ceil(log10(comb(n, k))))

改成不使用 comb，直接取 log10 ，還是會超時。

from math import log10, ceil
import sys

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == k: print("1")
    else:
        ans = 0
        for i in range(n, n-k, -1): ans += log10(i)
        for i in range(k, 1, -1): ans -= log10(i)
        print(ceil(ans))

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

from math import log10, ceil
import sys

def fac(x):
    return (x+0.5)*log10(x) - 0.4343*x + 0.39909

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == k: print("1")
    else: print(ceil(fac(n) - fac(n-k) - fac(k)))

ZeroJudge 解題筆記：b893. 勘根定理

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


ZeroJudge 題目連結：b893. 勘根定理

解題想法

因為 $-2147483647 \leq x^6 \leq 2147483647 ~\Rightarrow -36 \leq x \leq 36$，只要一路由 $-36$ 每次加 1 檢測到 $36$ 即可。 這題的敘述有問題，題目中說無解時輸出 N0THING! >\\<，但實際上是 N0THING! >\\\<。

Python 程式碼

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

def func(x):
    return a*x**5 + b*x**4 + c*x**3 + d*x**2 + e*x + f

a, b, c, d, e, f = map(int, input().split())
if a == b == c == d == e == f == 0:
    print("Too many... = =\"")
else:
    real = False
    for i in range(-36, 36):
        if func(i) == 0:
            print(f"{i:d} {i:d}")
            real = True
        elif func(i)*func(i+1) < 0:
            print(f"{i:d} {i+1:d}")
            real = True
    if not real: print("N0THING! >\\\\\\<")

ZeroJudge 解題筆記：b877. 我是電視迷

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


ZeroJudge 題目連結：b877. 我是電視迷

解題想法

這題可以用 if 判斷頻道號碼是否已經超過上限，從最前面繞回來；也可以取餘數找下一個頻道號碼。

Python 程式碼

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

a, b = map(int, input().split())
if b > a: print(b-a)
else: print(100-a+b)

將第2、3行合併。使用時間約為 17 ms，記憶體約為 3.3 MB，通過測試。

a, b = map(int, input().split())
print(b-a if b > a else 100-a+b)

取餘數，因為 Python 的取餘數若遇到被除數是負值，會先將被除數加上除數之後再取餘數，餘數和除數同號，不需要像 C++ 要在程式碼中自己加上除數量值。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

a, b = map(int, input().split())
print((b-a)%100)

ZeroJudge 解題筆記：b860. 獨角蟲進化計算器

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


ZeroJudge 題目連結：b860. 獨角蟲進化計算器

解題想法

用 while 迴圈不斷更新糖果、獨角蟲、鐵殼蛹的數量，直到獨角蟲的數量歸零為止。

Python 程式碼

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

c, w = map(int, input().split())  # 讀取糖果數量 c，獨角蟲數量 w
k = 0  # 鐵殼蛹數量 k

while w > 0:  # 如果 w 大於 0 繼續執行
    if c >= 12 and w >= 1:  # 如果 c 大於等於 12 而且 w 大於等於 1 才能進化
        c -= 10  # c 減 10，先用掉 12 顆，進化得 1 顆，再將鐵殼蛹送給博士得 1 顆
        w -= 1  # 進化，獨角蟲數量 w 減 1
        k += 1  # 鐵殼蛹數量 k 加 1
    else:  # 否則將獨角蟲送給博士換糖果
        w -= 1
        c += 1
# end of while loop
print(k)  # 印出答案

ZeroJudge 解題筆記：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

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


ZeroJudge 題目連結：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

解題想法

共有 $n$ 片花瓣，第一次拔1片，接下來每次比上一次多拔 $m$ 片，假設共拔 $k$ 次，拔掉的花瓣總數為 $$ t = k + [m + 2m + 3m + \dots + (k-1)m] = k + \frac{(k-1)km}{2} = \frac{1}{2} [m k^2 + (2-m) k] $$ 若要剛好拔完，則 $t = n$，且 $k \in N$ 才能符合條件，因此 $$ mk^2 + (2-m)k - 2n = 0 $$ 若有正整數的根，輸出 "Go Kevin!!"，否則輸出 "No Stop!!"。

Python 程式碼

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

import sys, math

for line in sys.stdin:  # 讀取多行測資直到 EOF 為止
    n, m = map(int, line.split())  # 花瓣數量 n，每次多拔的花瓣數量 m
    if m == 0:  # 如果 m 等於 0 一定有解
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    a, b, c = m, 2-m, -2*n  # 一元二次方程式的係數
    D = b*b - 4*a*c  # 判別式
    if D < 0:  # 判別式小於 0 無實數解
        print("No Stop!!")  # 印出 No Stop!!，繼續檢測下一行
        continue
    x1 = (-b + math.sqrt(D)) / (2*a)  # 較大的根
    x2 = (-b - math.sqrt(D)) / (2*a)  # 較小的根
    if x1 > 0 and int(x1) == math.ceil(x1):  # 如果 x1 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    elif x2 > 0 and int(x2) == math.ceil(x2):  # 如果 x2 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    else: print("No Stop!!")  # 否則印出 No Stop!!

ZeroJudge 解題筆記：b762. 英國聯蒙

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


ZeroJudge 題目連結：b762. 英國聯蒙

解題想法

這題用字典或串列儲存對應的訊息，寫起來會比較簡潔。

Python 程式碼

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

act = {"Get_Kill": 1, "Get_Assist": 2, "Die": 3}  # 輸入的狀態
# 連續擊殺數對應的訊息
kill_mess = ["",
             "You have slain an enemie.",
             "You have slain an enemie.",
             "KILLING SPREE!",
             "RAMPAGE~",
             "UNSTOPPABLE!",
             "DOMINATING!",
             "GUALIKE!",
             "LEGENDARY!"]
# 陣亡時連續擊殺數對應的訊息
die_mess = [ "You have been slained.",
             "SHUTDOWN."]

N = int(input())  # 指令數量
cont = 0  # 連續擊殺數
kill = 0  # 總擊殺數
ast = 0  # 助攻次數
die = 0  # 陣亡次數
for _ in range(N):
    a = act[input().strip()]  # 讀取 N 行指令，要用 strip() 刪除某些測資後方多的 \t 或空白
    if a == 1:  # 如果是 Get_Kill
        cont += 1  # 連續擊殺數加 1
        if cont >= 8: print(kill_mess[8])  # 如果連續擊殺數大於等於 8，印出 kill_mess[8]
        else: print(kill_mess[cont])  # 否則印出 kill_mess[cont]
    elif a == 2: ast += 1  # 如果是 Get_Assist 助攻數加 1
    elif a == 3:  # 如果是 Die
        if cont < 3: print(die_mess[0])  # 如果連續擊殺數小於 3，印出 die_mess[0]
        else: print(die_mess[1])  # 否則印出 die_mess[1]
        die += 1  # 陣亡次數加 1
        kill += cont  # 更新擊殺總數
        cont = 0  # 連續擊殺數歸零
kill += cont  # 最後要再加上一次連續擊殺數
print(f"{kill:d}/{die:d}/{ast:d}")  # 印出答案

ZeroJudge 解題筆記：b759. 我明明就有說過= =

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


ZeroJudge 題目連結：b759. 我明明就有說過= =

解題想法

這題可以只用字串切片或是索引值組合出每次要印出的內容，也可以每次都更新字串的內容，兩種方法的速度都很快。

Python 程式碼

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

X = input()
for i in range(len(X)):
    print(X[i:]+X[:i])

每次印出字串後，重新組合字串。使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

X = input()
for i in range(len(X)):
    print(X)
    X = X[1:] + X[0]

ZeroJudge 解題筆記：b604. Center of Symmetry

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


ZeroJudge 題目連結：b604. Center of Symmetry

解題想法

比較直接的作法，先將所有的點座標 (x, y) 存入集合之中，同時計算所有點座標的平均值 (xc, yc)。接下來從集合中取出一個點，計算對稱點的座標 (xn, yn)，檢查 (xn, yn) 是否在集合之中，如果沒有就可以印出 no 並停止檢查，反之從集合中移除 (xn, yn)，重複這個過程直到集合清空為止。如果集合可以清空，印出 yes。
另一個作法，是將所有的點存入陣列、由小到大排序。因為排在陣列最前面的點，其對稱點一定在陣列的最後面。由陣列兩端向中間檢查，只要頭尾兩個點不對稱，就可以印出 no 並停止檢查。如果可以檢查完整個陣列，印出 yes。

Python 程式碼

寫法1，從集合 points 中取出點，找到對稱點並移除。使用時間約為 0.1 s，記憶體約為 5.8 MB，通過測試。

def solve(n):
    points = set()  # 儲存點 (x, y) 的集合
    xc, yc = 0, 0  # 中心點座標 (xc, yc)
    for _ in range(n):  # 讀取 n 個點
        x, y = map(int, input().split())  # 讀取點座標 (x, y)
        x *= 2; y *= 2  # 為了使 (xc, yc) 皆為整數，先將 (x, y) 乘以 2
        xc += x; yc += y  # 先計算加總
        points.add((x, y))  # 將 (x, y) 加入 points
    ### end of for loop ###
    xc //= n; yc //= n  # 除以 n，取平均
    while points:  # 如果 points 還有資料繼續執行
        x, y = points.pop()  # 從 points 隨機取出一筆資料
        xn, yn = 2*xc - x, 2*yc - y  # 計算對稱點座標 (xn, yn)
        if (xn, yn) not in points:  # 如果 (xn, yn) 不在 points 之中
            return False  # 回傳 False
        points.remove((xn, yn))  # 否則從 points 中移除 (xn, yn)
    ### end of while loop ###
    return True  # 跑到這行代表有解，回傳 True

while True:
    n = int(input())  # 讀取點數 n
    if n == 0: break  # 如果讀到 0 中止迴圈
    print("yes" if solve(n) else "no")

ZeroJudge 解題筆記：b603. 拋物線方程式

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


ZeroJudge 題目連結：b603. 拋物線方程式

解題想法

這題考數學。假設開口向上或向下的抛物線頂點為 $(h, k) = (x_1, y_1)$，其方程式為 $$ y = A(x-h)^2 + k = A(x-x_1)^2 + y_1 $$ 線上另一個點為 $(x_2, y_2)$，將這個點代入上式可得 $$ y_2 = A(x_2 - x_1)^2 + y_1 ~\Rightarrow~ A = \frac{y_2 - y_1}{(x_2 - x_1)^2} $$ 另外二次曲線的通式為 $$ y = Ax^2 + Bx + C $$ 將上式與第1式比較係數，由 $x$ 項可得 $$ B = -2Ax_1 = -2 \times \frac{y_2 - y_1}{(x_2 - x_1)^2} \times x_1 $$ 由常數項可得 $$ C = Ax_1^2 + y_1 = \frac{y_2 - y_1}{(x_2 - x_1)^2} \times x_1^2 + y_1 $$ 為了將係數化為整數，將每一項同乘以 $x_2 - x_1$，再換成此題要求的型式 $ay = bx^2 + cx + d$，4個係數分別為 $$ \begin{align*} a &= x_2 - x_1 \\ b &= (x_2 - x_1) A = \frac{y_2 - y_1}{x_2 - x_1} \\ c &= (x_2 - x_1) B = -\frac{2x_1 (y_2 - y_1)}{x_2 - x_1} \\ d &= (x_2 - x_1) C = \frac{x_1^2 (y_2 - y_1)}{x_2 - x_1} + y_1 (x_2 - x_1) \end{align*} $$ 因為 $a$ 必須是正值，最後要再檢查一下係數的正負號。由以上的公式得到的係數可能需要約分。

Python 程式碼

第9行的 math.gcd，我使用的 Python 版本為 3.10.12，可以一次輸入多個參數求最大公因數，但是 ZeroJudge 網站的 Python 版本為 3.6.9，每次只能輸入2個參數。使用時間約為 21 ms，記憶體約為 3.4 MB，通過測試。

from math import gcd

def solve(x1, y1, x2, y2):
    a = x2-x1
    b = (y2-y1)//(x2-x1)
    c = -2*x1*(y2-y1)//(x2-x1)
    d = x1*x1*(y2-y1)//(x2-x1) + y1*(x2-x1)
    if a < 0:
        a, b, c, d = -a, -b, -c, -d
    g = gcd(gcd(gcd(a, b), c), d)
    if g != 1:
        a, b, c, d = a//g, b//g, c//g, d//g
    return a, b, c, d

while True:
    try:
        x1, y1, x2, y2 = map(int, input().split())
        a, b, c, d = solve(x1, y1, x2, y2)
        print(f"{a:d}y = {b:d}x^2 + {c:d}x + {d:d}")
    except EOFError: break

ZeroJudge 解題筆記：b595. Special Touring Car Racing

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


ZeroJudge 題目連結：b595. Special Touring Car Racing

解題想法

依序掃過 i = 1 ~ n 站，先計算從起點直接開到第 i 站的成本，再用另一層 for 迴圈，計算以 j = 1 ~ i-1 站為前一個停靠站到第 i 站的成本，更新第 i 站最低成本及前一個停靠站。最後再從終點往起點找出各停靠站的編號，將編號反向輸出。

Python 程式碼

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

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)  # 讀取 n
    if n == 0: break  # 如果 n 等於 0 中止迴圈
    stop = [0] + list(map(int, sys.stdin.readline().split()))  # 讀取停靠站位置，加入 stop[0] = 0 
    cost = [float('inf')]*(n+1)  # 移動到第 i 站的成本，預設為極大的值
    prev = [0]*(n+1)  # 移動到第 i 站之前停靠的前一站
    for i in range(1, n+1):  # 依序檢查第 1 ~ n 站
        cost[i] = min(cost[i], (200 - stop[i])**2)  # 計算由開頭直接走到第 i 站的成本
        for j in range(1, i):  # 依序檢查由第 1 ~ i-1 站走到第 i 站的成本
            val = cost[j] + (200 - (stop[i] - stop[j]))**2
            if val < cost[i]:  # 如果 val 小於 cost[i] 目前的值
                prev[i] = j; cost[i] = val  # 更新 prev[i] 為 j、 cost[i] 為 val
    ### end of for loop ###
    ans = [n]  # 答案，先加入終點 n
    idx = n  # 由 prev 讀取資料的索引值
    while prev[idx] != 0:  # 如果 prev[idx] 不等於 0 繼續執行
        ans.append(prev[idx])  # 將 prev[idx] 加入 ans
        idx = prev[idx]  # 更新 idx 為 prev[idx]
    print(*([0] + ans[::-1]))  # 反序列印

ZeroJudge 解題筆記：b594. A Marvelous Pet

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


ZeroJudge 題目連結：b594. A Marvelous Pet

解題想法

這題比較直接的想法，是用兩個指針從小到大掃過一次，變數 low 從 1 到 n-2，變數 high 從 2 到 n-1，區間 [low, high] 之間的加總為 isum。每次更新時有三種可能性：

1. 如果 isum = n，答案 ans 加 1，再將整個區間向右平移，isum 減去 low，low 加 1，high 加 1，isum 加上 high。
2. 如果 isum > n，isum 減去 low，再將 low 加 1。
3. 如果 isum < n，high 加 1，再將 isum 加上 high。

這個寫法用 Python 會超時，用 C++ 可以過關。 另一種寫法會利用到等差級數和公式，假設首項為 $a$、項數為 $k$、公差為 $1$，級數和 $$ s = \frac{k[a + a + (k-1)]}{2} = \frac{k(2a+k-1)}{2} $$ 依照題目的要求 $s = n$、$a = 1$，上式的 $k$ 必須有正整數的解，因此 $$ 2n = k^2 + k ~\Rightarrow~ k^2 + k -2n = 0 ~\Rightarrow~ k = \frac{-1 \pm \sqrt{1 + 8n}}{2} $$ 要測試的 $k$ 值上限為 $$ k_{max} = \frac{\sqrt{1 + 8n} - 1}{2} $$ 先寫一個 for 迴圈，依序測試 $2 \leq k \leq k_{max}$，判斷 $k$ 值是否為解的步驟為

1. $mod(2n, k) = 0$
2. $tmp = \frac{2n}{k} - k + 1 > 0$
3. $mod(tmp, 2) = 0$
4. $a = \frac{tmp}{2}, a \leq 1, a+k-1 < n$

Python 程式碼

寫法1，超時。

import sys

def solve(n):
    low, high, isum, ans = 1, 2, 3, 0
    while low < n-1 and high < n:
        if isum == n:
            ans += 1
            isum -= low
            low += 1
            high += 1
            isum += high
        elif isum > n:
            isum -= low
            low += 1
        else:
            high += 1
            isum += high
    return ans

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    ans = solve(n)
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b558. 求數列第 n 項

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


ZeroJudge 題目連結：b558. 求數列第 n 項

解題想法

這題的測資不大，而且遞迴關係也很簡單，可以先用遞迴建表，把 $1 \leq n \leq 500$ 對應的函數值都算出來，再逐行讀取測資、查表、輸出答案。也可以找一般式，先列出前幾項找規律 $$ \begin{align*} f(1) &= 1\\ f(2) &= f(1) + 1\\ f(3) &= f(2) + 2 \\ f(4) &= f(3) + 3 \\ &\vdots \\ f(n) &= f(n-1) + (n-1) \\ \end{align*} $$ 以上的式子相加之後可得 $$ f(n) = 1 + [1 + 2 + 3 + \dots + (n-1)] = 1 + \frac{n(n-1)}{2} $$

Python 程式碼

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

import sys

table = [0]*501
table[1] = 1
for i in range(2, 501): table[i] = table[i-1] + i - 1

for line in sys.stdin:
    print(table[int(line)])

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

table = [0]*501
table[1] = 1
for i in range(2, 501): table[i] = table[i-1] + i - 1
while True:
    try:
        print(table[int(input())])
    except:
        break

ZeroJudge 解題筆記：b557. 直角三角形

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


ZeroJudge 題目連結：b557. 直角三角形

解題想法

比較直接的作法是用三層迴圈掃過所有的邊長，找出可以組成直角三角形的邊長組合，這個作法在 C++ 很快，在 Python 會超時。另一種作法是先計算所有的邊長平方各有幾個，再由小到大取出邊長平方，如果兩者相加的值有在邊長平方的計數器之中，再用計數器中的數量相乘、計算直角三角形的數量。

Python 程式碼

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

t = int(input())  # t 組測資
for _ in range(t):
    n = int(input())  # n 個邊長
    edges = sorted(list(map(int, input().split())))
    cnt = dict()  # 邊長平方的計數器
    cand = []  # 邊長平方
    for edge in edges:  # 計算各種邊長平方的數量
        x = edge * edge
        if x not in cnt:
            cnt[x] = 1
            cand.append(x)
        else:
            cnt[x] += 1
    m = len(cnt)  # 邊長平方的數量
    ans = 0  # 答案
    for i in range(m-1):  # 依序讀取由小到大的邊長平方
        for j in range(i+1, m):
            a, b = cand[i], cand[j]  # 邊長平方 a, b
            if a+b in cnt:  # 如果 cnt 之中有 a+b 才會更新 ans
                ans += cnt[a+b]* cnt[a] * cnt[b]
    print(ans)

ZeroJudge 解題筆記：b538. 分數運算-2

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


ZeroJudge 題目連結：b538. 分數運算-2

解題想法

這題比b537. 分數運算-1簡單很多，只要按照分數運算的規則，分別寫出加、減、乘、除的計算方式，再用 gcd 將分子、分母約分。輸出時分別三種：0、整除、分數，如果分母是負的，負號要加在分子的前面。

Python 程式碼

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

import sys, math

def fac_cal(a, b, c, d, op):
    num, den = 1, 1  # 計算結果的分子、分母
    if op == "+":  # a/b + c/d = (a*d + c*b) / (b*d)
        num = a*d + c*b 
        den = b*d
    elif op == "-":  # a/b - c/d = (a*d - c*b) / (b*d)
        num = a*d - c*b
        den = b*d
    elif op == "*":  # a/b * c/d = (a*c) / (b*d)
        num = a*c
        den = b*d
    else:  # a/b / c/d = a/b * d/c = (a*d) / (b*c)
        num = a*d
        den = b*c
    if den < 0:  # 如果分母小於 0，將分子、分母的正負號都反過來
       num = -num; den = -den
    g = math.gcd(num, den)  # 取分子、分母最大公因數約分
    num //= g; den //= g
    if num == 0: return "0\n"  # 分子為 0，回傳 0
    elif num%den == 0: return f"{num:d}\n"  # 可以整除，回傳分子
    else: return f"{num:d}/{den:d}\n"  # 不能整除

result = []
lines = sys.stdin.readlines()
for line in lines:
    arr = line.split()
    a, b, c, d = map(int, arr[:4])  # 分割出前 4 個數字
    op = arr[-1]  # 運算符號
    result.append(fac_cal(a, b, c, d, op))
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b512. 高維度稀疏向量

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


ZeroJudge 題目連結：b512. 高維度稀疏向量

解題想法

這題的維度不連續而且範圍很大，用字典儲存維度及對應的值比較方便，如果用陣列儲存值會有很多浪費掉、沒有儲存資料的空間。

Python 程式碼

先儲存兩個向量的資料，再計算相乘的結果。使用時間約為 43 ms，記憶體約為 6.1 MB，通過測試。

A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    B[k] = v
ans = 0
for k, v in A.items():
    ans += v * B.get(k, 0)
    if a in B: ans += n*B[a]  # 也可以這樣寫
print(ans)

只儲存第一個向量的資料，讀取第二個向量資料同時計算相乘的結果。使用時間約為 45 ms，記憶體約為 4.5 MB，通過測試。

A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
ans = 0
for sub in input().split():  # 不需要略過 0:0，不影響答案
    k, v = map(int, sub.split(":"))
    ans += v*A.get(k, 0)
print(ans)

ZeroJudge 解題筆記：b511. 換銅板

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


ZeroJudge 題目連結：b511. 換銅板

解題想法

這題我用函式遞迴窮舉所有面額硬幣、數量、總金額的組合，如果遇到總金額符合題目要求的組合就輸出答案。

Python 程式碼

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

def solve():
    import sys
    n = int(sys.stdin.readline())  # n 種面額
    coins = sorted(list(map(int, sys.stdin.readline().split())))  # 硬幣面額，由小到大排序
    target = int(sys.stdin.readline())  # 目標
    ### 主要的解題過程 ###
    def backtrack(curr, nums, total):
        if total == target:  # 遞迴出口，符合目標
            s = "(" + ",".join(map(str, nums)) + ")"  # 要輸出的字串
            sys.stdout.write(f"{s}\n")
            return
        if curr == n or total > target:  # 遞迴出口，已經到最後一種面額或超過目標
            return
        maxn = (target-total) // coins[curr]  # 這個面額可用的最大數量
        for i in range(maxn+1):  # 依序測試 0 ~ maxn 個
            nums[curr] = i  # 設定這個面額的數量
            backtrack(curr+1, nums, total + coins[curr]*i)  # 遞迴
    ### End of backtrack ###
    backtrack(0, [0]*n, 0)  # 從索引值 0、個數 0、加總 0 開始測試
### End of solve ###

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：b373. [福州19中]车厢重组

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


ZeroJudge 題目連結：b373. [福州19中]车厢重组

解題想法

這題實際上就是考氣泡排序法的交互次數。據說第二筆測資車廂編號的資料有問題，可能被空行分隔，不是只有一行，用 Python 解題時，需要加上一些濾掉空行的工具。

Python 程式碼

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

import sys

n = int(sys.stdin.readline())  # n 節車廂
arr = []  # 車廂編號
for line in sys.stdin:  # 讀取多行測資
    if not line.strip(): continue  # 如果是空行，讀下一行
    arr += list(map(int, line.split()))  # 如果不是空行，轉成串列接到 arr
### 氣泡排序法，找交換次數 ###
cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        if arr[i] > arr[j]:
            arr[i], arr[j] = arr[j], arr[i]
            cnt += 1
sys.stdout.write(f"{cnt:d}\n")

ZeroJudge 解題筆記：b367. 翻轉世界

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


ZeroJudge 題目連結：b367. 翻轉世界

解題想法

可以用二維串列儲存圖的內容，再從上下兩端逐行檢查，下方的列前後順序對調之後內容是否與上方的列相同；如果共有奇數列，還要再單獨檢查中間的列。也可以將圖的內容接成很長的一維串列，只要從兩端往中間依序檢查數字是否相同，寫起來比較簡單。

Python 程式碼

用二維串列儲存圖的內容，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

def check(grid):  # 輸入圖，判斷是否轉 180 度之後對稱
    n, m = len(grid), len(grid[0])  # 圖的尺寸
    for i in range(n//2):  # 從上下兩端往中間檢查
        if grid[i] != grid[n-i-1][::-1]:  # 如果將底下的列翻轉之後不相等
            return False  # 回傳 False
    if n%2 == 1:  # 如果為奇數列，再檢查中間的列
        if grid[n//2] != grid[n//2][::-1]:
            return False
    return True  # 最後回傳 True

t = int(input())  # t 張圖
for _ in range(t):  # 執行 t 次
    n, m = map(int, input().split())  # 圖的尺寸 n*m
    grid = [list(map(int, input().split())) for _ in range(n)]  # 讀取圖
    print("go forward" if check(grid) else "keep defending")

ZeroJudge 解題筆記：b265. Q11286 - Conformity

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


ZeroJudge 題目連結：b265. Q11286 - Conformity

解題想法

這個題目的中文敘述很奇怪。題目的意思應該是要統計各種課程組合的選課人數，例如

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100

第 2、4 列是一樣的課程組合，因此答案為 2。另一筆範例測資

3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444

因為 2、3、4 列是不一樣的課程組合，各有 1 個人選擇這個組合，題目是將所有最多選課人數的課程組合都加起來，所以答案為 3。

Python 程式碼

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

import sys
from collections import defaultdict

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    cnt = defaultdict(int)
    for _ in range(n):
        course = tuple(sorted(list(map(int, sys.stdin.readline().split()))))
        cnt[course] += 1
    ans = imax = 0
    for v in cnt.values():
        if v > imax:
            ans = v; imax = v
        elif v == imax:
            ans += v
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a982. 迷宮問題#1

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


ZeroJudge 題目連結：a982. 迷宮問題#1

解題想法

這題我用 BFS 解題。可以用兩個二維串列分別儲存地圖及步數，也可以用一個二維串列儲存步數，-1 代表邊界。

Python 程式碼

用兩個二維串列，分別儲存地圖及步數。使用時間約為 33 ms，記憶體約為 3.9 MB，通過測試。

from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input()) for _ in range(n)]  # 地圖資料
steps = [[0]*n for _ in range(n)]  # 步數資料
steps[1][1] = 1  # 起點為 (1, 1)，步數 1
que = deque([(1, 1)])  # 待走訪佇列，先放入 (1, 1)
while que:  # BFS
    r, c = que.popleft()  # 目前的座標 (r, c)
    for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要測試的點 (nr, nc)
        if grid[nr][nc] == '#' or steps[nr][nc] != 0:  # 如果是邊界或已走過
            continue  # 找下一個點
        steps[nr][nc] = steps[r][c] + 1  # 更新 (nr, nc) 的步數
        que.append((nr, nc))  # (nr, nc) 加到 que
### End of BFS ###
# 如果 (n-2, n-2) 此格不是 0，有解；反之無解
print(steps[n-2][n-2] if steps[n-2][n-2] != 0 else "No solution!")

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 解題筆記：a915. 二维点排序

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


ZeroJudge 題目連結：a915. 二维点排序

解題想法

這題在 Python 先將座標 (x, y) 組成 tuple 再存入 list，再用 sort 將 list 排序。在 C++ 可以用 pair 或自訂 struct 儲存座標 (x, y)，再存入 array 或 vector，再用 algorithm 函式庫的 sort 排序。

Python 程式碼

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

n = int(input())
arr = sorted([tuple(map(int, input().split())) for _ in range(n)])
for a in arr: print(*a)

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

n = int(input())
for a in sorted([tuple(map(int, input().split())) for _ in range(n)]): print(*a)

ZeroJudge 解題筆記：a746. 画蛇添足

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


ZeroJudge 題目連結：a746. 画蛇添足

解題想法

這題的測資 2 有空行，如果用 Python 需要過濾掉空行，否則會出錯。而且這題的記憶體限制很嚴格，如果用 Python 直接産生 $(n+2) \times (n+2)$ 的二維串列會超過記憶體上限。

Python 程式碼

第3行是為了濾掉測資中的空行，但是這樣測試不會過，因為本題的記憶體限制很嚴格，在第 7 行産生 $(n+2) \times (n+2)$ 的二維串列時會超過記憶體上限。

import sys

lines = [line for line in sys.stdin.readlines() if line.strip()]
idx = 0

while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    grid = [[" "]*(n+2) for _ in range(n+2)]
    for c in range(n+2):
        grid[0][c] = grid[n+1][c] = "-"
    for r in range(1, n+1):
        grid[r][0] = grid[r][n+1] = "|"
    ri, ci = map(int, lines[idx].split())
    idx += 1
    for _ in range(m-1):
        rf, cf = map(int, lines[idx].split())
        idx += 1
        if ri == rf:
            for c in range(min(ci, cf), max(ci, cf)+1):
                grid[ri][c] = "*"
        elif ci == cf:
            for r in range(min(ri, rf), max(ri, rf)+1):
                grid[r][ci] = "*"
        ri, ci = rf, cf
    for row in grid:
        sys.stdout.write("".join(row) + "\n")

ZeroJudge 解題筆記：a740. 质因数之和

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


ZeroJudge 題目連結：a740. 质因数之和

解題想法

測試 i = 2 ~ 根號 x 是否為 x 的因數，如果 i 是因數就繼續將 x 縮小為 1/i，直到 i 不是因數為止。最後如果 x 不等於 1，代表此時 x 是某一個質數，答案再加上 x。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)
    ans = 0
    for i in range(2, int(x**0.5)+1):  # 測試 2 ~ 根號 x
        while x%i == 0:  # 如果 i 可以整除 x
            ans += i  # 加上 i
            x //= i  # x 變為 1/i
    if x != 1: ans += x  # 如果 x 不是 1，x 為質數
    sys.stdout.write(f"{ans:d}\n")

ZeroJudge 解題筆記：a694. 吞食天地二

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


ZeroJudge 題目連結：a694. 吞食天地二

解題想法

題目中的 x 軸應該是對應到列，y 軸對應到欄，有點奇怪。解題技巧主要利用的是二維前綴和，産生前綴和的原則

psum[i][j] = matrix[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1]

因為 $psum[i-1][j-1]$ 會被多加一次，最後要扣掉。用前綴和取範圍 $[r1, c1]$ 到 $[r2, c2]$ 區間和的原則

isum = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]

因為 $psum[r1-1][c1-1]$ 會被多扣一次，最後要加回來。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    psum = [[0]*(n+1) for _ in range(n+1)]  # 最上面、最左邊補 0
    for i in range(1, n+1):  # 讀取 n 行資料
        row = [0] + list(map(int, sys.stdin.readline().split()))
        for j in range(1, n+1):  # 處理前綴和
            psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + row[j]
    for _ in range(m):  # 讀取 m 行
        r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
        isum = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]
        sys.stdout.write(f"{isum:d}\n")

ZeroJudge 解題筆記：a693. 吞食天地

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


ZeroJudge 題目連結：a693. 吞食天地

解題想法

用前綴和解題，如果要求陣列中索引值 [left, right] 的區間和，即為前綴和 psum[right] - psum[left-1]。

Python 程式碼

逐行讀取測資、輸出結果，使用時間約為 0.5 s，記憶體約為 11.8 MB，通過測試。如果改用 print 輸出答案，使用時間約為 1.2 s，記憶體約為 11.7 MB。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    psum = [0] + list(map(int, sys.stdin.readline().split()))
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, sys.stdin.readline().split())
        isum = psum[right] - psum[left-1]
        sys.stdout.write(f"{isum:d}\n")

一次讀取所有測資，最後再一次輸出所有結果，使用時間約為 0.5 s，記憶體約為 36.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    psum = [0] + list(map(int, lines[idx].split()))
    idx += 1
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, lines[idx].split())
        idx += 1
        isum = psum[right] - psum[left-1]
        result.append(f"{isum:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a248. 新手訓練 ~ 陣列應用

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


ZeroJudge 題目連結：a248. 新手訓練 ~ 陣列應用

解題想法

理論上這題是要先計算 a, b 相除的商，接著再取 a %= b，每次將 a 乘以 10 倍之後除以 b，計算小數的部分直到 n 位數為止，但是這個作法在 Python 會太慢。反而可以利用 Python 支援大數運算的特性，直接將 a%b 乘以 $10^n$ 再除以 b 計算小數的部分，但是要記得在小數部分前面補 0 到 n 位數。

Python 程式碼

寫法1，超時。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.rstrip(): continue
    a, b, n = map(int, line.split())
    int_part = a//b
    a %= b
    res = [f"{int_part:d}."]
    for _ in range(n):
        a *= 10
        c = a//b
        res.append(f"{c:d}")
        a %= b
    result.append("".join(res) + "\n")
sys.stdout.write("".join(result))

寫法2，大數運算，使用時間約為 0.5 s，記憶體約為 17.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.rstrip(): continue
    a, b, n = map(int, line.split())
    int_part = a//b
    dec_part = str(a%b*(10**n) // b).zfill(n)
    result.append(f"{int_part:d}.{dec_part}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a528. 大數排序

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


ZeroJudge 題目連結：a528. 大數排序

解題想法

因為 Python 支援大數運算，可以直接排序。C++ 則要用字串格式，分成兩個字串 a、b 開頭都是 +，開頭都是 -，a 正 b 負、a 負 b 正，共 4 種狀況排序。

Python 程式碼

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

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    nums = sorted([int(sys.stdin.readline()) for _ in range(n)])
    result = [f"{num:d}\n" for num in nums]
    sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a524. 手機之謎

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


ZeroJudge 題目連結：a524. 手機之謎

解題想法

這題在 Python 可以用 itertools.permutations，在 C++ 可以用 algorithm 函式庫的 prev_permutation 産生所有的排列，速度很快。也可以用函式遞迴産生所有的排列方式。由於測資有空行，用 Python 解題時要記得跳過空行，否則會吃 RE。

Python 程式碼

寫法1，用 itertools.permutations 産生所有的排列，使用時間約為 0.2 s，記憶體約為 7.5 MB，通過測試。

import sys
from itertools import permutations

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    for arr in permutations(range(n, 0, -1), n):  # 從 n ~ 1 的數字取 n 個排列
        res = [f"{a:d}" for a in arr]  # arr 的內容轉成字串存入 res
        result.append("".join(res) + "\n")  # res 接成一個字串加入 result
sys.stdout.write("".join(result))  # 一次輸出所有的結果

寫法2，用函式遞迴窮舉所有的排列，使用時間約為 0.4 s，記憶體約為 7.5 MB，通過測試。

import sys

result = []
def perm(arr, nums, used, depth):
    # 代入已選數字串列 arr, 可用數字串列 nums，已選數字的集合 used，目標長度 depth
    if len(arr) == depth:  # 遞迴出口，如果 arr 長度等於 depth
        result.append("".join([f"{a:d}" for a in arr]) + "\n")  # 接成字串加入 result
        return
    for num in nums:  # 依序由 nums 讀取數字
        if num in used: continue  # 如果 num 已用過，找下一個數字
        arr.append(num)  # num 接到 arr 最後面
        used.add(num)  # num 加入 used
        perm(arr, nums, used, depth)  # 遞迴
        arr.pop()  # 從 arr 最後面移除數字
        used.remove(num)  # 從 used 移除 num

lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    perm([], list(range(n, 0, -1)), set(), n)
sys.stdout.write("".join(result))  # 一次輸出所有的結果

ZeroJudge 解題筆記：a417. 螺旋矩陣

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


ZeroJudge 題目連結：a417. 螺旋矩陣

解題想法

我是先填完矩陣的值再輸出，速度會慢一點。

Python 程式碼

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

def draw(n, m):
    ### 填格子 ###
    if m == 1:  # 方向順序是右、下、左、上
        dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)
    else:  # 方向順序是下、右、上、左
        dr, dc = (1, 0, -1, 0), (0, 1, 0, -1)
    matrix = [[0]*n for _ in range(n)]  # n*n 矩陣，預設值皆為 0
    r, c, v = 0, 0, 1  # 座標 (r, c)，值為 1
    d = 0  # 一開始朝右方或下
    while v < n*n:  # 還沒有填完
        matrix[r][c] = v  # 設定此格的值
        nr, nc = r+dr[d], c+dc[d]  # 要走的格子
        if nr < 0 or nr >= n or nc < 0 or nc >= n or matrix[nr][nc] != 0:  # 出界或已經填過了
            d = (d+1)%4  # 轉向
            nr, nc = r+dr[d], c+dc[d]  # 更新 (nr, nc)
        r, c = nr, nc  # 走到 (nr, nc)
        v += 1  # 值加 1
    matrix[r][c] = v  # 設定最後一格的值
    ### 輸出 ###
    for row in matrix:
        for c, v in enumerate(row):
            print(f"{v:5d}", end="\n" if c == n-1 else "")

T = int(input())
for t in range(T):
    if t > 1: print()
    draw(*map(int, input().split()))

ZeroJudge 解題筆記：a414. 位元運算之進位篇

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


ZeroJudge 題目連結：a414. 位元運算之進位篇

解題想法

假設二進位制數字 $n$ 要加 1，其進位次數等於 $n$ 從最右側向左算共有幾個連續的 1。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 65.9 MB，通過測試。這題的測資量很大，用 print 輸出會很慢，大約要 2 s。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n == 0: break
    cnt = 0
    while n&1:
        n >>= 1
        cnt += 1
    result.append(f"{cnt:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a410. 解方程

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


ZeroJudge 題目連結：a410. 解方程

解題想法

這題用克拉瑪公式，假設二元一次方程式為 $$ \left\{\begin{matrix} a_1 x + b_1 y &= c_1 \\ a_2 x + b_2 y &= c_2 \end{matrix}\right. $$ 令 $$ \Delta = \begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{vmatrix} ~~~~~\Delta_x = \begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \end{vmatrix} ~~~~~\Delta_y = \begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \end{vmatrix} $$ 有以下三種狀況

1. 如果 $\Delta \neq 0$，方程式恰有一組解，其解為 $x = \frac{\Delta_x}{\Delta}, ~ y = \frac{\Delta_y}{\Delta}$
2. 如果 $\Delta = 0$，但 $\Delta_x, \Delta_y$ 至少有一個不為 0，無解。
3. 如果 $\Delta = \Delta_x = \Delta_y = 0$，無限多組解。

Python 程式碼

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

a1, b1, c1, a2, b2, c2 = map(int, input().split())
delta = a1*b2 - a2*b1
deltax = c1*b2 - c2*b1
deltay = a1*c2 - a2*c1
if delta != 0:  # 恰有一組解
    print(f"x={deltax/delta:.2f}")
    print(f"y={deltay/delta:.2f}")
else:
    if deltax != 0 or deltay != 0: print("No answer")   # 無解
    elif deltax == 0 and deltay == 0: print("Too many") # 無窮多組解

ZeroJudge 解題筆記：a291. nAnB problem

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


ZeroJudge 題目連結：a291. nAnB problem

解題想法

先掃過一次答案與猜測的數字，計算位置、數字都對的數量 A，如果不是位置、數字都對，則用兩個串列記錄 0 ~ 9 各個數字的數量。接下來再掃過這兩個串列，計算位置不對、數字對的數量 B。但是這一題我在 Python 上遇到很大的困難，換了好幾種寫法都超時，用 C++ 會過關但是速度還不夠快，需要改變寫法。

Python 程式碼

超時。

import sys
   
result = []
for line in sys.stdin:
    if not line.rstrip(): continue
    ans = list(map(int, line.split()))
    n = int(sys.stdin.readline())
    for _ in range(n):
        guess = list(map(int, sys.stdin.readline().split()))
        A, B = 0, 0  # 位置、數字都對的數量 A，位置不對、數字對的數量 B
        cnt_a, cnt_g = [0]*10, [0]*10  # 0 ~ 9 各個數字的數量
        for a, g in zip(ans, guess):  # 先掃一輪
            if a == g: A += 1  # 位置、數字都對，A 加 1
            else:  # 反之，記錄數字對應的數量
                cnt_a[a] += 1
                cnt_g[g] += 1
        for a, g in zip(cnt_a, cnt_g):  # 計算 B 的數量
            if a >= g: B += g
            else: B += a
        result.append(f"{A:d}A{B:d}B\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a229. 括號匹配問題

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


ZeroJudge 題目連結：a229. 括號匹配問題

解題想法

我用函式遞迴枚舉所有可能的組合，但是 Python 的部分一直超時，C++ 的部分用 string 儲存字串會超時，要用字元陣列才能過關。

Python 程式碼

寫法1，用字串儲存答案，超時。

import sys

def solve(n):
    """
    輸入括號對數 n，枚舉所有合法的組合
    """
    if n == 0: return [""]  # 特例，回傳只有空字串的串列
    result = []  # 儲存組合用的串列
    def backtrack(curr, left, right):
        """
        回溯，輸入現在的字串 curr、左括號數量 left、右括號數量 right
        """
        if left == n and right == n:  # 找到新的組合，加到 result
            result.append(f"{curr}\n")
            return
        if left < n:  # 如果左括號數量不夠，回溯，加上 (
            backtrack(curr+"(", left+1, right)
        if right < left:  # 如果右括號比左括號少，回溯，加上 )
            backtrack(curr+")", left, right+1)
    ### End of backtrack ###
    backtrack("", 0, 0)  # 呼叫 backtrack
    return result

ca = 0
for line in sys.stdin:
    if not line.rstrip(): continue
    ca += 1
    if ca > 1: sys.stdout.write("\n")
    sys.stdout.write("".join(solve(int(line))))

ZeroJudge 解題筆記：a225. 明明愛排列

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


ZeroJudge 題目連結：a225. 明明愛排列

解題想法

這題在 Python 可以用內建的排序工具 sort，搭配 functools.cmp_to_key 與自訂比較式；在 C++ 可以用 algorithm 函式庫的 sort，搭配 lambda function 自訂比較式，寫起來會快很多。

Python 程式碼

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

import sys
from functools import cmp_to_key

def mycmp(a, b):
    if a%10 == b%10:
        if a > b: return -1
        elif a < b: return 1
        else: return 0
    elif a%10 < b%10: return -1
    else: return 1

for line in sys.stdin:
    n = int(line)
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort(key = cmp_to_key(mycmp))
    print(*arr)

ZeroJudge 解題筆記：a224. 明明愛明明

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


ZeroJudge 題目連結：a224. 明明愛明明

解題想法

先將所有字母轉成小寫，再用字典或表格計數，計算每個字母出現的次數，同時計算所有字母的數量 n。如果 n 是奇數，只能有一個字母的數量是奇數；如果 n 是偶數，所有的字母數量都必須是偶數。

Python 程式碼

寫法1，字典計數，使用時間約為 22 ms，記憶體約為 3.6 MB，通過測試。

import sys
from collections import defaultdict

def check(s):
    n = 0
    cnt = defaultdict(int)
    for c in s.lower():
        n += 1
        if c.isalpha():
            cnt[c] += 1
    even = sum(v%2 for v in cnt.values())
    if n%2 == 1:
        return even <= 1
    else:
        return even == 0

for line in sys.stdin:
    print("yes !" if check(line.rstrip()) else "no...")

ZeroJudge 解題筆記：a216. 數數愛明明

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


ZeroJudge 題目連結：a216. 數數愛明明

解題想法

方法1，使用函式遞迴，但是可能會因為遞迴次數太多而超時。方法2，找一般式，例如 $$ \begin{align*} f(1) &= 1\\ f(2) &= 2 + f(1)\\ f(3) &= 3 + f(3)\\ & \vdots \\ f(n) &= n + f(n-1) \end{align*} $$ 將以上式子相加可得 $$ f(n) = 1 + 2 + 3 + \dots + n = \frac{1}{2} \cdot n(n+1) $$ 接下來求 $g(n)$，先列出幾行 $$ \begin{align*} g(1) &= 1\\ g(2) &= f(2) + g(1)\\ g(3) &= f(3) + g(2)\\ & \vdots \\ g(n) &= f(n) + g(n-1) \end{align*} $$ 將以上式子相加可得 \begin{align*} g(n) &= f(1) + f(2) + f(3) + \dots + f(n)\\ &= \frac{1}{2} \sum_{i=1}^n (i^2 + i)\\ &= \frac{1}{2} \cdot \left [ \frac{1}{6} \cdot n(n+1)(2n+1) + \frac{1}{2} \cdot n(n+1) \right ]\\ &= \frac{1}{12} \cdot n(n+1) \left [ (2n+1) + 3 \right ] \\ &= \frac{1}{6} \cdot n(n+1)(n+2)\\ \end{align*}

Python 程式碼

方法1，使用函式遞迴，果然不意外地在測試題會超時。

import sys

def f(n):
    if n == 1: return 1
    else: return n + f(n-1)

def g(n):
    if n == 1: return 1
    else: return f(n) + g(n-1)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

方法2，找出一般式直接代入 n 求答案，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def f(n):
    return int(n*(n+1)/2)

def g(n):
    return int(n*(n+1)*(n+2)/6)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

ZeroJudge 解題筆記：a054. 電話客服中心

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


ZeroJudge 題目連結：a054. 電話客服中心

解題想法

先取英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起，存到一個對應的陣列之中。依照規則計算數字部分的編碼 code，加上英文字母對應的值要能被 10 整除，因此答案就是 (10 - code%10) % 10 對應的字母。

Python 程式碼

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

# 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
letters = ("BNZ", "AMW", "KLY", "JVX", "HU", "GT", "FS", "ER", "DOQ", "CIP")
s = input()  # 身分證字號
# 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
code = sum(int(c)*(8-i) for i, c in enumerate(s[:9])) + int(s[-1])
print(letters[(10 - code%10) % 10])

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
    string letters[10] = {"BNZ", "AMW", "KLY", "JVX", "HU", 
                          "GT", "FS", "ER", "DOQ", "CIP"};
    string s; cin >> s;  // 身分證字號
    // 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
    int code = 0;
    for(int i=0; i<9; i++) code += (s[i]-'0')*(8-i);
    code += s.back() - '0';
    cout << letters[(10 - code%10) % 10] << "\n";
    return 0;
}

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)