ZeroJudge 解題筆記：c050. 00453 - Goldbach's Conjecture

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


ZeroJudge 題目連結：c050. 00453 - Goldbach's Conjecture

解題想法

先建立 1000000 以內的質數表 primes，但是不包含 2，因為題目要測試的數字大於 4。如果要測試的數字為 $n$，先用二分搜尋法從表格中找到最接近且大於等於 $n$ 的質數索引值 $idx$，接下來從 3 開始往上找到 $primes[idx]$ 為止，最早找到的解就是差值最大的解。

Python 程式碼

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

import sys, bisect

### 建立 1 ~ 1000000 的質數表，不包含 2 ###
maxn = 1000000
sieve = [True]*(maxn+1)
sieve[0] = sieve[1] = False
for i in range(0, maxn+1, 2): sieve[i] = False
for i in range(3, int(maxn**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, maxn+1, i):
            sieve[j] = False
primes = [i for i in range(maxn+1) if sieve[i]]

### 主要的解題過程 ###
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    n = int(data[ptr])
    ptr += 1
    if n == 0: break
    idx = bisect.bisect_left(primes, n)
    a, b = 0, 0
    for x in primes[:idx+1]:  # 從 3 開始往上找，最早找到的解就是差值最大的解
        y = n-x
        idy = bisect.bisect_left(primes, y)
        if primes[idy] == y:
            a, b = x, y
            break
    if a == 0 and b == 0:
        reesult.append("Goldbach's conjecture is wrong.\n")
    else:
        result.append(f"{n:d} = {a:d} + {b:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c049. 00356 - Square Pegs And Round Holes

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


ZeroJudge 題目連結：c049. 00356 - Square Pegs And Round Holes

解題想法

先算數學，如果正方形的邊長為 $n$，則圓的半徑為 $r = 0.5 \times (2n - 1)$。接下來用兩層 for 迴圈掃過正方形的右上角每一格，假設正方形正中央為原點 $(0, 0$)，格子座標的左下角 $(x, y)$，如果 $(x+1)^2 + (y+1)^2 \leq r^2$ 代表這格在圓之中，如果 $x^2 + y^2 > r^2$ 代表這格在圓之外，再將計算結果乘以 4 就是對應的答案 $inner$ 及 $outer$，圓上的格子數則是 $4n^2 - outer - inner$。

Python 程式碼

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

import sys

first = True
for line in sys.stdin:
    if not first: print()
    first = False
    n = int(line)
    r = (2*n - 1) * 0.5
    inner, outer = 0, 0
    for x in range(n):
        for y in range(n):
            if (x+1)**2 + (y+1)**2 <= r*r: inner += 1
            elif x**2 + y**2 > r*r: outer += 1
    inner *= 4; outer *= 4
    print(f"In the case n = {n:d}, {4*n*n-outer-inner:d} cells contain segments of the circle.")
    print(f"There are {inner:d} cells completely contained in the circle.")

ZeroJudge 解題筆記：c048. 10161 - Ant on a Chessboard

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


ZeroJudge 題目連結：c048. 10161 - Ant on a Chessboard

解題想法

觀察位置的規律，第 1 格在左下角，第 4 格在邊長 $2 \times 2$ 正方形右下角，第 9 格在邊長 $3 \times 3$ 正方形左上角，第 16 格在邊長 $4 \times 4$ 正方形右下角，第 25 格在邊長 $5 \times 5$ 正方形左下角，第 36 格在邊長 $6 \times 6$ 正方形右下角。可以先建表，再用二分搜尋法找 n 在第幾列。也可以直接開根號，向上取整數。

Python 程式碼

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

import sys, bisect

maxn = 44722  # 平方為 2000057284，超出題目上限 2000000000
nums = [i*i for i in range(maxn+1)]  # i 平方的數字，開頭放 0，用二分搜尋法時比較方便
for line in sys.stdin:
    n = int(line)  # 時間 n
    if n == 0: break
    m = bisect.bisect_left(nums, n)  # n 在 nums 之中的棋盤的第 m 列
    b = nums[m] - n  # n 是 nums 第 m 列往回數 b 格
    if m%2 == 1:  # 如果 m 是奇數，先向上，再向左
        if b < m: print(b+1, m)  # 倒過來向右數
        else: print(m, m+m-b-1)  # 倒過來向下數
    else:  # 如果 m 是偶數，先向右，再向下
        if b < m: print(m, b+1)  # 倒過來向上數
        else: print(m+m-b-1, m)  # 倒過來向左數

ZeroJudge 解題筆記：c045. 00490 - Rotating Sentences

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


ZeroJudge 題目連結：c045. 00490 - Rotating Sentences

解題想法

這題我在 Python 是用二維串列儲存字串內容，在 C++ 則是用 vector 加 string 儲存內容。先讀取所有的測資，接下來用二層 for 迴圈讀取測資中的字元，外層處理欄位，內容從最後一列讀取到第 0 列。輸出答案時，如果這一列不是整整空白才要輸出。

Python 程式碼

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

import sys

lines = sys.stdin.readlines()  # 一次讀取所有的資測，包含結尾的 \n
n = len(lines)  # 共有 n 列
ans = [[] for _ in range(100)]  # 答案，題目限制每列最多 100 個字元
for c in range(100):  # 欄位，題目限制每列最多 100 個字元
    for r in range(n-1, -1, -1):  # 依序讀取第 n-1 到 0 列
        m = len(lines[r]) - 1
        if c < m: ans[c].append(lines[r][c])  # 如果 r 沒有出界，lines[r][c] 加入 ans[c]
        else: ans[c].append(" ")  # 反之，空格加入 ans[c]
for a in ans:  # 依序讀取 ans 每一列的資料 a
    row = "".join(a)  # 將 a 組成字串 row
    if not row.isspace():  # 如果 row 不是整列空白
        sys.stdout.write(row + "\n")

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