ZeroJudge 解題筆記：c014. 10035 - Primary Arithmetic

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


ZeroJudge 題目連結：c014. 10035 - Primary Arithmetic

解題想法

這題只要依照直式加法的作法，從最後一位開始相加，如果最後一個分別為 a, b，目前的進位值為 carry，如果 $a + b + carry \geq 10$ 需要進位，進位次數 $cnt$ 加 1，同時 $carry$ 重設為 1；反之不需要進位，$carry$ 重設為 0。因為測資的數字在 10 位數以內，可以直接用整數處理就好；但如果數字很大，需要用字串格式才能處理。

Python 程式碼

整數格式，使用時間約為 22 ms，記憶體約為 2.9 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    cnt, carry = 0, 0
    while n > 0 or m > 0:
        a, b = n%10, m%10
        if a + b + carry >= 10:
            cnt += 1
            carry = 1
        else:
            carry = 0
        n //= 10
        m //= 10
    if cnt == 0:
        print("No carry operation.")
    elif cnt == 1:
        print("1 carry operation.")
    else:
        print(f"{cnt:d} carry operations.")

字串格式，使用時間約為 25 ms，記憶體約為 2.9 MB，通過測試。

import sys

for line in sys.stdin:
    s, t = line.split()
    if s == "0" and t == "0": break
    n, m = len(s), len(t)  # 長度
    # 前面補 0 讓 s, t 長度相等
    if n < m:
        s = s.zfill(m)
    else:
        t = t.zfill(n)
    # 由後往前計算加法及進位
    cnt, carry = 0, 0  # 進位次數，目前進位的值
    for a, b in zip(s[::-1], t[::-1]):
        if int(a) + int(b) + carry >= 10:
            cnt += 1
            carry = 1
        else:
            carry = 0
    # 輸出對應的答案
    if cnt == 0:
        print("No carry operation.")
    elif cnt == 1:
        print("1 carry operation.")
    else:
        print(f"{cnt:d} carry operations.")

ZeroJudge 解題筆記：c012. 10062 - Tell me the frequencies!

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


ZeroJudge 題目連結：c012. 10062 - Tell me the frequencies!

解題想法

這題如果用 Python 解題，可以用預設的 map 或是 collections 函式庫中的 Counter 計數，用 Counter 比較方便，只要寫 Counter(字串) 就可以算出字串每個字元的個數。測資會有空白，如果用 C++ 要用 getline 讀取資料，但是不能計算到結尾的 \n 或 \r。

Python 程式碼

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

from collections import Counter
import sys

first = True
for line in sys.stdin:
    if not first: print()
    first = False
    cnt = Counter(line.strip())
    ans = [(v, ord(k)) for k, v in cnt.items()]
    ans.sort(key = lambda x : (x[0], -x[1]))
    for a in ans: print(a[1], a[0])

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

from collections import Counter
import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    if result: result.append("\n")
    cnt = Counter(line.strip())
    ans = [(v, ord(k)) for k, v in cnt.items()]
    ans.sort(key = lambda x : (x[0], -x[1]))
    for a in ans: result.append(f"{a[1]:d} {a[0]:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c010. 10107 - What is the Median?

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


ZeroJudge 題目連結：c010. 10107 - What is the Median?

解題想法

這題如果用串列，每次插入一個新的數字之後再排序、取中位數，這樣一定會超時。我試過以下兩種解法。第一種是用 C++ 的 priority_queue 及 Python 的 heapq 儲存資料，小於等於中位數的值儲存在最大優先佇列 small 之中，大於中位數的值儲存在最小優先佇列 large 之中，並且保持 small 的數量與 large 相等或是多一個。當讀取到一筆新的資料 x 時有三種可能性：

1. x 小於等於 small 最上面的資料：如果 small 的數量比 large 還多，將 small 最上面的資料移到 large。最後將 x 加入 small。
2. large 有資料而且 x 小於 large 最上面的資料： 如果 small 與 large 數量相等，將 x 加入 small，反之將 x 加入 large。
3. 其它狀況：如果 small 與 large 數量相等，將 large 最上面的資料移到 small。最後將 x 加入 large。

中位數有兩種可能性：

1. 如果 small 數量比 large 還多，中位數就是 small 最上面的資料。
2. 如果 small 與 large 數量相等，中位數是 small 與 large 最上面的資料平均值。

第二種解法是用 C++ algorithm 函式庫的 lower_bound 找出插入新資料並維持排序的位置，再用 vector.insert 插入新資料。在 Python 則可以用 bisect.insort 直接將新資料插入到 list 之中。由於這兩種工具是利用二分搜尋法找位置，速度相當快，寫起來也會比第一種法方簡單。

Python 程式碼

方法1，使用時間約為 21 ms，記憶體約為 4.2 MB，通過測試。

import sys, heapq

mid = int(sys.stdin.readline())
result = [f"{mid:d}\n"]
large, small = [], [-mid]
for line in sys.stdin:
    x = int(line)
    if x <= -small[0]:
        if len(small) > len(large):
            heapq.heappush(large, -heapq.heappop(small)) 
        heapq.heappush(small, -x)
    elif large and x < large[0]:
        if len(small) == len(large):
            heapq.heappush(small, -x) 
        else:
            heapq.heappush(large, x)
    else:
        if len(small) == len(large):
            heapq.heappush(small, -heapq.heappop(large))
        heapq.heappush(large, x)
    if len(small) > len(large):
        mid = -small[0]
    else:
        mid = (large[0] - small[0]) // 2
    result.append(f"{mid:d}\n")
sys.stdout.write("".join(result))

方法2，使用時間約為 26 ms，記憶體約為 4.8 MB，通過測試。

import sys
from bisect import insort

result = []
arr = []
lines = sys.stdin.readlines()
for line in lines:
    x = int(line)
    insort(arr, x)
    n = len(arr)
    if n%2 == 1:
        result.append(f"{arr[n//2]:d}\n")
    else:
        result.append(f"{(arr[n//2 - 1] + arr[n//2]) // 2:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c009. 10473 - Simple Base Conversion

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


ZeroJudge 題目連結：c009. 10473 - Simple Base Conversion

解題想法

這題如果用 Python 寫很簡單，可以用內建的工具 int(字串, 基底) 將字串以指定的基底轉換成十進位整數，也可以用 hex(整數) 將十進位整數轉換成 16 進位制字串。如果用 C++ 解題則需要自己寫轉換用的函式。

Python 程式碼

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

import sys

for s in sys.stdin:
    s = s.rstrip()
    if s[0] == "-": break
    elif s[:2] == "0x":
        print(int(s[2:], 16))
    else:
        t = hex(int(s))[2:].upper()
        print("0x" + t)

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

import sys

result = []
lines = sys.stdin.readlines()
for s in lines:
    s = s.strip()
    if not s: continue
    if s[0] == "-": break
    elif s[:2] == "0x":
        result.append(f"{int(s[2:], 16):d}\n")
    else:
        t = hex(int(s))[2:].upper()
        result.append(f"0x{t}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c007. 00272 - TeX Quotes

作者：王一哲
日期：2026年1月24日


ZeroJudge 題目連結：c007. 00272 - TeX Quotes

解題想法

讀取一行測資，再依序讀取這行的每個字元並記錄讀到 " 的次數 left，讀到第 1 個 " 時將 left 設定成 1，在要輸出的字串中加上 ｀｀；如果讀到 " 時 left 等於 1，代表這是第 2 個 "，將 left 歸零，在要輸出的字串中加上 ''；如果是其它字串則直接加到要輸出的字串後面。

Python 程式碼

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

import sys

left = 0
result = []
lines = sys.stdin.readlines()
for line in lines:
    s = []
    for c in line.rstrip():
        if c == "\"":
            if left == 0:
                s += ["`", "`"]
                left = 1
            else:
                s += ["\'", "\'"]
                left = 0
        else: s.append(c)
    res = "".join(s)
    result.append(f"{res}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c006. 10550 - Combination Lock

作者：王一哲
日期：2026年1月23日


ZeroJudge 題目連結：c006. 10550 - Combination Lock

解題想法

刻度差 1 要轉 9 度，順時鐘方向轉刻度減少，逆時鐘方向轉刻度增加。

Python 程式碼

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

import sys

for line in sys.stdin:
    if line.rstrip() == "0 0 0 0":
        break
    a, b, c, d = map(int, line.split())
    tot = 360*3
    tot += 360 - (9*b + 360 - 9*a) % 360
    tot += (9*c + 360 - 9*b) % 360
    tot += 360 - (9*d + 360 - 9*c) % 360
    print(tot)

ZeroJudge 解題筆記：c004. 10812 - Beat the Spread!

作者：王一哲
日期：2026年1月22日


ZeroJudge 題目連結：c004. 10812 - Beat the Spread!

解題想法

這題在算數學。假設兩隊的分數分別為 $x, y$ 而且 $x \geq y$，因為分數為大於等於 0 的整數，因此 $s \geq d$。如果測資 $s < d$，直接印出 impossible。 接下來解聯立 $$ x + y = s ~~~~~ x - y = d $$ 將兩式相加可得 $$ 2x = s + d ~\Rightarrow~ x = \frac{s + d}{2} $$ 如果 $s + d$ 是奇數，直接印出 impossible。再將 $x$ 代入其中一條式子可得 $$ y = s - x $$

Python 程式碼

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

n = int(input())
for _ in range(n):
    s, d = map(int, input().split())
    if d > s:
        print("impossible")
        continue
    xx = s + d
    if xx%2 == 1:
        print("impossible")
        continue
    x = xx//2
    y = s - x
    print(x, y)

ZeroJudge 解題筆記：c001. 10405 - Longest Common Subsequence

作者：王一哲
日期：2026年1月21日


ZeroJudge 題目連結：c001. 10405 - Longest Common Subsequence

解題想法

只要找最長共同子序列 (longest common subsequence, LCS) 的長度，用二維串列 dp 儲存兩個字串 s, t 的第 i 個、第 j 個字母對應的 LCS 長度。

Python 程式碼

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

import sys

def length_LCS(s, t):
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    a = lines[idx].strip()
    idx += 1
    b = lines[idx].strip()
    idx += 1
    ans = length_LCS(a, b)
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b917. 11059 Maximum Product

作者：王一哲
日期：2026年1月20日


ZeroJudge 題目連結：b917. 11059 Maximum Product

解題想法

這題用兩層 for 迴圈硬算，假設要測試的數字存在串列 $nums$，依序測試從 $nums[i]$ 為首項，再乘以 $nums[j], (j < i)$ 到 $nums[-1]$，每次乘完之後更新最大值。時間複雜度約為 $O(n^2)$，可以通過測試。反而是輸出格式要小心，每一行測資對應的結果底下都要印出一行空行。

Python 程式碼

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

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
ca = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    ca += 1
    n = int(lines[idx])
    idx += 1
    nums = list(map(int, lines[idx].split()))
    idx += 1
    imax = 0
    for i in range(n):
        curr = 1
        for j in range(i, n):
            curr *= nums[j]
            imax = max(imax, curr)
    result.append(f"Case #{ca:d}: The maximum product is {imax:d}.\n\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b587. 10918 - Tri Tiling

作者：王一哲
日期：2026年1月19日


ZeroJudge 題目連結：b587. 10918 - Tri Tiling

解題想法

因為地板的尺寸為 $3 \times n$，要放入的地板磚尺寸為 $1 \times 2$，如果 $n$ 為奇數時無解。接下來列出 $n$ 的前幾項可能的拼法，例如 $n = 2$ 有 3 種

AA   AB   CC
BB   AB   AB
CC   CC   AB

如果以 $dp[n]$ 代表地板尺寸為 $3 \times n$ 的拼法數量，其中 $dp[0] = 1$，因為沒有放置地板算 1 種；$dp[2] = 3$，像是上面的例子；接下來推算 $n \geq 4$ 的狀況。 狀況1，如果最右側是完整的 $3 \times 2$，這個部分有 3 種拼法，左側的拼法為 $dp[n-2]$，因此 $dp[n] = 3 \times dp[n-2]$。 狀況2，如果最右側不是完整的 $3 \times 2$，先列出 $$ dp[n] = 3 \times dp[n-2] + 2 \times (dp[n-4] + dp[n-6] + \dots + dp[0]) $$ 再列出 $$ dp[n-2] = 3 \times dp[n-4] + 2 \times (dp[n-6] + dp[n-8] + \dots + dp[0]) $$ 將兩式相減 $$ dp[n] - dp[n-2] = 3 \times dp[n-2] - dp[n-4] $$ 移項後得到 $$ dp[n] = 4 \times dp[n-2] - dp[n-4] $$

Python 程式碼

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

import sys

def solve(n):
    if n == 0: return 1
    if n == 2: return 3
    if n%2 == 1: return 0
    dp = [0]*(n+1)
    dp[0] = 1; dp[2] = 3
    for i in range(4, n+1, 2):
        dp[i] = 4*dp[i-2] - dp[i-4]
    return dp[n]

for line in sys.stdin:
    n = int(line)
    if n == -1: break
    print(solve(n))