一個地球人在臺北

2026年2月4日星期三

ZeroJudge 解題筆記：c036. 00573 - The Snail

作者：王一哲
日期：2026年2月4日

ZeroJudge 題目連結：c036. 00573 - The Snail

解題想法

用 $y$ 儲存目前的高度，預設值為 0。用一個無窮迴圈，不斷更新每天的高度，更新的順序為

白天往上爬高度 $u$，如果 $y > h$ 印出 success on day {days}，中止迴圈。
晚上向下滑高度 $d$，如果 $y < 0$ 印出 failure on day {days}，中止迴圈。
更新下一天向上爬的高度 $u$，如果 $u < 0$ 時歸零。

Python 程式碼

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

import sys

for line in sys.stdin:
    if line.rstrip() == "0 0 0 0": break
    h, u, d, f = map(float, line.split())
    days = 0
    dec = u*f*0.01
    y = 0.0
    while True:
        days += 1
        y += u
        if y > h:
            print(f"success on day {days:d}")
            break
        y -= d
        if y < 0:
            print(f"failure on day {days:d}")
            break
        u -= dec
        if u < 0: u = 0.0

2026年2月3日星期二

ZeroJudge 解題筆記：c034. 00424 - Integer Inquiry

作者：王一哲
日期：2026年2月3日

ZeroJudge 題目連結：c034. 00424 - Integer Inquiry

解題想法

Python 支援大數運算，直接加起來就好。C++ 則要用字串儲存數字，然後從最後一位往前加。

Python 程式碼

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

import sys

isum = 0
for line in sys.stdin:
    n = int(line)
    if n == 0: break
    isum += n
print(isum)

C++ 程式碼

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

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

string big_sum(string s, string t) {  // 輸出字串 s, t，輸出相加後的字串 u
    string u = "";  // 儲存相加的結果
    int m = (int)s.size(), n = (int)t.size();  // s, t 的長度
    if (m > n) {  // s 較長，在 t 前面補 0
        string zeros (m-n, '0');
        t = zeros + t;
    } else if (m < n) {  // t 較長，在 s 前面補 0
        string zeros (n-m, '0');
        s = zeros + s;
    }
    int mn = max(m, n), carry = 0;  // 最大長度 mn，進位數值只會是 0 或 1
    for(int i=mn-1; i>=0; i--) {  // 由最後一位向前讀取
        char a = s[i], b = t[i];  // 字元 a, b
        int c = (a-'0') + (b-'0') + carry;  // a, b 相加後的結果 c
        u = char(c%10 + '0') + u;  // 更新 u
        carry = c/10;  // 更新 carry
    }
    if (carry == 1) u = '1' + u;  // 如果 carry 等於 1，在 u 前面補 1
    for(int i=0; i<(int)u.size(); i++) {  // 刪除 u 前面的 0
        if (u[i] != '0') {
            u = u.substr(i);
            break;
        }
    }
    return u;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s, t;
    getline(cin, s);
    while(getline(cin, t)) s = big_sum(s, t);
    cout << s << "\n";
    return 0;
}

2026年2月2日星期一

ZeroJudge 解題筆記：c033. 00406 - Prime Cuts

作者：王一哲
日期：2026年2月2日

ZeroJudge 題目連結：c033. 00406 - Prime Cuts

解題想法

這個題目的 1 被視為質數。質數表最大值到 1009，因為測資的 n 最大值為 1000，如果只建到 1000，在質數表中用二分搜尋法找 n 可能會出界。

Python 程式碼

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

import sys, bisect

nums = [1]
state = [True]*1010
for i in range(2, 1010):
    if not state[i]: continue
    nums.append(i)
    for j in range(i+i, 1010, i):
        state[j] = False

first = True
for line in sys.stdin:
    n, c = map(int, line.split())
    if not first: print()
    first = False
    idx = bisect.bisect_left(nums, n)
    if nums[idx] == n: k = idx + 1
    else: k = idx
    if (k%2 == 0 and 2*c >= k) or \
       (k%2 == 1 and 2*c + 1 >= k):
        sub = nums[:k]
    elif k%2 == 0: sub = nums[k//2 - c : k//2 + c]
    else: sub = nums[(k+1)//2 - c : k//2 + c]
    print(f"{n:d} {c:d}: ", end="")
    print(*sub)

2026年2月1日星期日

ZeroJudge 解題筆記：c032. 00382 - Perfection

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

ZeroJudge 題目連結：c032. 00382 - Perfection

解題想法

注意，實際上有多行測資。我是用試除法找 $n$ 的因數，將所有的因數儲存在集合之中。最後再比較所有的因數加總 $isum$ 與 $n$ 的大小，輸出對應的答案。

Python 程式碼

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

import sys

def test(n):
    if n == 1: return "DEFICIENT"
    factors = {1}
    for i in range(2, int(n**0.5)+1):
        if n%i == 0:
            factors.add(i)
            factors.add(n//i)
    isum = sum(factors)
    if isum == n:
        return "PERFECT"
    elif isum < n:
        return "DEFICIENT"
    else:
        return "ABUNDANT"

print("PERFECTION OUTPUT")
for line in sys.stdin:
    for n in map(int, line.split()):
        if n == 0: continue
        print(f"{n:5d}  {test(n):s}")
print("END OF OUTPUT")

2026年1月31日星期六

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}")

2026年1月30日星期五

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)

2026年1月29日星期四

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))

2026年1月28日星期三

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.")

2026年1月27日星期二

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

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

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

解題想法

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))

2026年1月26日星期一

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 時有三種可能性：

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

中位數有兩種可能性：

如果 small 數量比 large 還多，中位數就是 small 最上面的資料。
如果 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))

訂閱：意見 (Atom)

熱門文章

2026年2月4日 星期三

解題想法

Python 程式碼

2026年2月3日 星期二

解題想法

Python 程式碼

C++ 程式碼

2026年2月2日 星期一

解題想法

Python 程式碼

2026年2月1日 星期日

解題想法

Python 程式碼

2026年1月31日 星期六

解題想法

Python 程式碼

2026年1月30日 星期五

解題想法

Python 程式碼

2026年1月29日 星期四

解題想法

Python 程式碼

2026年1月28日 星期三

解題想法

Python 程式碼

2026年1月27日 星期二

解題想法

Python 程式碼

2026年1月26日 星期一

解題想法

Python 程式碼

2026年2月4日星期三

2026年2月3日星期二

2026年2月2日星期一

2026年2月1日星期日

2026年1月31日星期六

2026年1月30日星期五

2026年1月29日星期四

2026年1月28日星期三

2026年1月27日星期二

2026年1月26日星期一