ZeroJudge 解題筆記：e494. 無窮級數之和(二)

作者：王一哲
日期：2025年9月26日


ZeroJudge 題目連結：e494. 無窮級數之和(二)

解題想法

這題考數學及大數運算，所以我只有寫 Python 版本。公式解 $$ \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots + \frac{1}{p} = \ln(\ln p) + M = \ln(\ln p) + 0.2614972128476427837554268386 $$ 由於輸出的小數位數很多，甚至要用到 decimal 函式庫的浮點數物件 Decimal 才行。

Python 程式碼

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

import sys, decimal

def solve(n):
    decimal.getcontext().prec = 1000  # 設定小數位數
    p = decimal.Decimal(n)  # 用 Decimal 格式的浮點數
    if p == decimal.Decimal(2):  # 特例，n 等於 2，回傳 0.5
        return decimal.Decimal('0.5')
    # 公式解，ln(ln(n)) + M
    ln_ln_p = p.ln().ln()
    M = decimal.Decimal('0.2614972128476427837554268386')
    return round(ln_ln_p + M, 3)

for line in sys.stdin:
    print(f"{solve(decimal.Decimal(line)):.3f}")

ZeroJudge 解題筆記：e484. 我是優質學生

作者：王一哲
日期：2025年9月25日


ZeroJudge 題目連結：e484. 我是優質學生

解題想法

這題要判斷輸入的數字是否為 2 到 10000 之間的質數，由於輸入只有一行，不要建質數表，直接判斷這個數是否為質數就好。

Python 程式碼

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

def is_prime(n):  # 判斷是否為質數
    if n <= 1: return False  # 特例，小於等於1，回傳 False
    if n == 2 or n == 3: return True  # 特例，等於 2 或 3，回傳 True
    if n%2 == 0 or n%3 == 0: return False  # 特例，可以被 2 或 3 整除，回傳 False
    for i in range(5, int(n**0.5)+1, 6):  # 依序檢查 5 ~ sqrt(n)，每次加 6
        if n%i == 0 or n%(i+2) == 0:  # 如果可以被 i 或 i+2 整除，回傳 Fasle
            return False
    return True  # 最後回傳 True

print("yes" if is_prime(int(input())) else "no")

ZeroJudge 解題筆記：e470. 無窮級數之和(一)

作者：王一哲
日期：2025年9月24日


ZeroJudge 題目連結：e470. 無窮級數之和(一)

解題想法

這題考數學，當 $n$ 很大時，有近似公式 $$ \sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + \frac{1}{2n} $$ 其中 $\gamma = 5772156649$。

Python 程式碼

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

import sys, math

def harmonic_number(n):
    if n <= 20:  # 如果 n 小於等於 20，直接用迴圈計算
        isum = 0
        for i in range(1, n+1): isum += 1/i
        return isum
    gamma = 0.5772156649  # 反之，代近似公式
    return math.log(n) + gamma + 1.0 / (2 * n)

for line in sys.stdin:
    print(f"{harmonic_number(int(line)):.3f}")

ZeroJudge 解題筆記：e447. queue 練習

作者：王一哲
日期：2025年9月23日


ZeroJudge 題目連結：e447. queue 練習

解題想法

這題就是考 queue 的操作，在 Python 要引入 collections 函式庫的 deque，在 C++ 要引入 queue 或是 deque 都可以。

Python 程式碼

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

from collections import deque

n = int(input())
arr = deque()
for _ in range(n):
    line = list(map(int, input().split()))
    if len(line) == 1:
        if line[0] == 2:
            if arr: print(arr[0])
            else: print(-1)
        elif line[0] == 3 and arr: arr.popleft()
    else:
        arr.append(line[1])

ZeroJudge 解題筆記：e446. 排列生成

作者：王一哲
日期：2025年9月22日


ZeroJudge 題目連結：e446. 排列生成

解題想法

這題不論用 Python 還是 C++ 都可以用遞迴窮舉所有的排列方式。在 Python 也可以用 itertools.permutaions，在 C++ 也可以用 next_permutation。但主要的困難之處是輸出速度，要加速才能過關。

Python 程式碼

窮舉，用 print 輸出，超時。

def solve(arr, n, used):
    if len(arr) == n:
        print(*arr)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(input()), set())

窮舉，用 sys.stdout.write 輸出，超時。

import sys

def solve(arr, n, used):
    if len(arr) == n:
        s = " ".join(map(str, arr)) + "\n"
        sys.stdout.write(s)
        return
    for i in range(1, n+1):
        if i in used: continue
        used.add(i)
        arr.append(i)
        solve(arr, n, used)
        used.remove(i)
        arr.pop()
    return

solve([], int(sys.stdin.readline()), set())

用 itertools.permutations，用 sys.stdout.write 最後再一次輸出所有結果，最後一筆測資超出記憶體上限。

import sys, itertools

result = []
n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm))
    result.append(f"{s}\n")
sys.stdout.write("".join(result))

用 itertools.permutations，用 sys.stdout.write 逐行輸出結果。使用時間約為 12.3 s，記憶體約為 3.4 MB，通過測試。

import sys, itertools

n = int(sys.stdin.readline())
nums = list(range(1, n+1))
for perm in itertools.permutations(nums):
    s = " ".join(map(str, perm)) + "\n"
    sys.stdout.write(s)

ZeroJudge 解題筆記：e420. 灰姑娘的新衣

作者：王一哲
日期：2025年9月20日


ZeroJudge 題目連結：e420. 灰姑娘的新衣

解題想法

我用字典 color_idx 儲存各種顏色對應的衣服編號，另一個字典 idx_color 儲存各種衣服編號有的顏色，顔色不重複。最後再計算所有的組合數，輸出最多顔色的衣服，輸出完美搭配的顔色。

Python 程式碼

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

import sys
from collections import defaultdict

color_idx = defaultdict(list)  # 各種顏色對應的衣服編號，可重複
idx_color = defaultdict(set)  # 各種衣服編號有的顏色，不重複
cnt = 0  # 衣服編號
for line in sys.stdin:
    line = line.strip()  # 刪除最後的 \n
    cnt += 1  # 衣服編號加 1
    color_idx[line].append(cnt)  # 顏色 line 有的編號加上 cnt
    idx_color[cnt].add(line)  # 編號 cnt 有的顏色加上 line
    for s in sys.stdin:
        s = s.strip()  # 讀取一行字串，刪除最後的 \n
        if s == "@" or s == "#": break  # 讀到 # 或 @，中止迴圈
        color_idx[s].append(cnt)  # 顏色 s 有的編號加上 cnt
        idx_color[cnt].add(s)  # 編號 cnt 有的顏色加上 s，不重複
comb = 1  # 組合數
for v in idx_color.values(): comb *= len(v)
print(comb)
most_color = []
n = len(idx_color)  # 編號數量
perfect = []
imax = max([len(v) for v in color_idx.values()])
for k, v in color_idx.items():
    if len(v) == imax:
        most_color.append(k)
    if len(set(v)) == n:
        perfect.append(k)
print(",".join(sorted(most_color)))
print(",".join(sorted(perfect)))

ZeroJudge 解題筆記：e293. 花開花落，雨初臨

作者：王一哲
日期：2025年9月20日


ZeroJudge 題目連結：e293. 花開花落，雨初臨

解題想法

這題的題目敘述根本就是在寫小說，重點只有「要找出給定的數字在 100 以內的質因數」。解題時要先建表 primes，列出 0 到 100 之間的質數，只有 25 個，直接打進程式碼就好。接下來計算這些質數相乘的結果 pq，假設要檢查的數字為 $m$，如果 $s = gcd(m, pq)$ 等於 1，則 $m$ 在 0 到 100 之間沒有質因數；反之，從 primes 之中依序取出質數 prime，檢查 prime 是否為 s 的因數即可。不過這題的輸出最大會到 5000 位，要用大數運算，所以我只有用 Python 解題。

Python 程式碼

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

import sys, math

# 建表，2 ~ 100 之間的質數
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
          31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
          73, 79, 83, 89, 97}
# pq，2 ~ 100 所有的質數相乘
pq = 1
for prime in primes: pq *= prime
# 主要的解題過程
result = []  # 儲存結果用的空串列
lines = sys.stdin.readlines()
for line in lines[1:]:
    m = int(line)  # 轉成整數 m
    res = []  # 儲存 m 的答案用的空串列
    s = math.gcd(m, pq)
    if s == 1:  # m 在 0 到 100 之間沒有質因數
        result.append("Terrible Silence...\n")
    else:
        for prime in primes:  # 依序由 primes 中取出質數，檢查是否為 s 的因數
            if s%prime == 0:  # 如果 prime 是因數
                res.append(f"{prime:d}")  # prime 轉成字串加入 res
        result.append(" ".join(res) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e284. 放暑假了!!!!!

作者：王一哲
日期：2025年9月19日


ZeroJudge 題目連結：e284. 放暑假了!!!!!

解題想法

這題主要考輸入、輸出優化，因為測資數量極大，如果沒有優化輸入、輸出會超時。在 Python 我習慣用 sys.stdin.readlines() 一次讀取所有的測資，並將所有的輸出存在串列 result 之中，最後再用 sys.stdout.write("".join(result)) 一次印出所有答案。在 C++ 如果要用 cin 及 cout，必須加上 ios::sync_with_stdio(0); cin.tie(0);，不然就是改用 scanf 及 printf。事先用字典或集合建表，儲存 $2^0$ 到 $2^31$ 對應的值，讀取測資之後再判斷這個數字是否在表格之中，這樣速度會比較快。但是經過實測之後發現，C++ 的 map 及 unordered_map 都很慢，要用 set 才能過關； Python 的 dict, defaultdict, set 都能過關。

Python 程式碼

用 dict 建表，使用時間約為 4.2 s，記憶體約為 413.6 MB，通過測試。

import sys

table = dict()
x = 1
for _ in range(32):
    table[x] = True
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

用 set 建表，使用時間約為 4.1 s，記憶體約為 418.2 MB，通過測試。

import sys

table = set()
x = 1
for _ in range(32):
    table.add(x)
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：e272. gcd(Fm,Fn)

作者：王一哲
日期：2025年9月18日


ZeroJudge 題目連結：e272. gcd(Fm,Fn)

解題想法

這題考數學，必須運用費氏數列的特性 $$ gcd(F_m, F_n) = F_{gcd(m, n)} $$ 如果直接計算 $F_m, F_n$ 的數值再取 $gcd$，在 $m, n$ 極大的狀況下會超時。

Python 程式碼

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

import sys, math

fib = [0]*94
fib[1] = 1
for i in range(2, 94):
    fib[i] = fib[i-1] + fib[i-2]

for line in sys.stdin:
    a, b = map(int, line.split())
    print(fib[math.gcd(a, b)])

ZeroJudge 解題筆記：e128. 新北100-1貪食蛇

作者：王一哲
日期：2025年9月17日


ZeroJudge 題目連結：e128. 新北100-1貪食蛇

解題想法

這題要找位置的數學規律，如果模擬移動的過程一定會超時。

Python 程式碼

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

import math, sys

def find_position(t):  # 輸入目前的時刻計算位置
    if t == 1: return (1, 1)  # 特例，t 等於 1，回傳 (1, 1) 並結束函式
    
    ring = math.floor(math.sqrt(t))  # 已走完的圈數
    #ring = math.isqrt(t)    # 已走完的圈數，Python 3.8 之後才有 math.isqrt
    
    t -= ring * ring  # t 扣掉已走完的圈數平方，換成位移量
    if t == 0:  # 如果 t 等於 0，剛好在這圈結束的位置
        if ring%2: return (1, ring)  # 如果是奇數圈，回傳 (1, ring) 並結束函式
        else: return (ring, 1)  # 如果是偶數圈，回傳 (ring, 1) 並結束函式
    else: ring += 1  # 其它狀況，圈數加 1
    
    x, y = 0, 0  # 座標 (x, y)
    if ring%2:  # 奇數圈
        if t > ring:  # 在底部向左移動
            x = 2*ring - t  
            y = ring
        else:  # 在右側向下移動
            x = ring
            y = t
    else:  # 偶數圈
        if t > ring:  # 在右側向上移動
            x = ring
            y = 2*ring - t
        else:  # 在底部向右移動
            x = t
            y = ring
    
    return (x, y)

for line in sys.stdin:
    t = int(line)
    if t == 0: break
    print(*find_position(t))