ZeroJudge 解題筆記：c031. 00264 - Count on Cantor

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


ZeroJudge 題目連結：c031. 00264 - Count on Cantor

解題想法

先觀察數列的特性，第 $i$ 列共有 $i$ 項，數值為 $1/i, 2/(i-1), \dots, (i-1)/2, i/1$，第 $1$ 到 $i$ 列總數 $$ total = 1 + 2 + \dots + i = \frac{i(i+1)}{2} $$ 因此，我先建一個陣列 $nums$ 儲存第 0 列到第 $i$ 列的項目數量，直到數量大於等於 $10^7$ 為止。讀取測資 $n$ 之後，再用二分搜尋法從 $nums$ 之中找 $n$ 的索引值 $m$。若第 $n$ 項為 $p/q$，由於題目的數列順序為 S 形，如果 m 是奇數，代表取數值方向往右上，則 $p = nums[m] - n +1, q = m - p +1$；反之，方向往左下。則 $q = nums[m] - n +1, p = m - p +1$。

Python 程式碼

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

import sys, bisect

nums = [0]
i, tot = 0, 0
while tot < 1E7:
    i += 1
    tot += i
    nums.append(tot)

for line in sys.stdin:
    n = int(line)
    m = bisect.bisect_left(nums, n)
    if m%2 == 1:
        p = nums[m] - n + 1
        q = m - p + 1
    else:
        q = nums[m] - n + 1
        p = m - q + 1
    print(f"TERM {n:d} IS {p:d}/{q:d}")

ZeroJudge 解題筆記：c024. 10079 - Pizza Cutting

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


ZeroJudge 題目連結：c024. 10079 - Pizza Cutting

解題想法

這題困難之處在於數學證明。假設切 $n$ 刀的最大分割數量為 $m$ 塊，先列出前幾項的數量 1. $n = 0, m = 1$ 2. $n = 1, m = 1 + 1 = 2$ 3. $n = 2, m = 2 + 2 = 4$ 4. $n = 3, m = 3 + 4 = 7$ 5. $n = 4, m = 4 + 7 = 11$ 如果要使分割數量最多，最後一刀要與前面每一刀都交會。若 $dp[n]$ 代表切 $n$ 刀分割的最大數量，由以上的式子可以看出 $$ \begin{align*} dp[n] &= dp[0] + dp[n-1] + n\\ &= 1 + 1 + 2 + \dots + (n-1) + n\\ &= 1 + \frac{n(n+1)}{2} \\ &= \frac{n^2 + n + 2}{2} \end{align*} $$

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)
    if n < 0: break
    print((n*n + n + 2) // 2)

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

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


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 解題筆記：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)