熱門文章

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 解題,可以用預設的 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月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 時有三種可能性:
  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))


2026年1月25日 星期日

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