ZeroJudge 解題筆記：c044. 10008 - What's Cryptanalysis

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


ZeroJudge 題目連結：c044. 10008 - What's Cryptanalysis

解題想法

這題可以用表格或字典計數，以下的寫法採用表格計數，用一個長度為 26 的陣列記錄每個字母出現的次數，不是英文字母的字元不需要計數。計數完畢之後，再將次數、字母組成 tuple 或 pair 存入陣列之中，先依照次數由大到小排序，如果次數相同再依照字母由小到大排序。

Python 程式碼

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

n = int(input())
cnt = [0]*26
for _ in range(n):
    s = input()
    for c in s:
        if c.isupper():
            cnt[ord(c) - ord('A')] += 1
        elif c.islower():
            cnt[ord(c) - ord('a')] += 1
ans = [(v, chr(k+ord('A'))) for k, v in enumerate(cnt) if v > 0]
ans.sort(key = lambda x : (-x[0], ord(x[1])))
for a in ans: print(a[1], a[0])

ZeroJudge 解題筆記：c039. 00100 - The 3n + 1 problem

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


ZeroJudge 題目連結：c039. 00100 - The 3n + 1 problem

解題想法

用一個自訂函式 cycle 處理數值 n 的循環次數，寫起來會比較方便。函式內部按照題目的要求，分別處理 n 為奇數、偶數兩種狀況，更新 n 的數值。

Python 程式碼

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

import sys

def cycle(n):
    times = 1  # 如果 n 等於 1，至少有 1 次
    while n != 1:
        times += 1
        if n%2 == 1: n = 3*n + 1
        else: n //= 2
    return times

for line in sys.stdin:
    a, b = map(int, line.split())
    print(f"{a:d} {b:d} ", end="")
    if a > b: a, b = b, a
    imax = 0
    for i in range(a, b+1):
        imax = max(imax, cycle(i))
    print(f"{imax:d}")

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

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


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

解題想法

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

1. 白天往上爬高度 $u$，如果 $y > h$ 印出 success on day {days}，中止迴圈。
2. 晚上向下滑高度 $d$，如果 $y < 0$ 印出 failure on day {days}，中止迴圈。
3. 更新下一天向上爬的高度 $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

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;
}

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)

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

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