ZeroJudge 解題筆記：b367. 翻轉世界

作者：王一哲
日期：2025年7月21日


ZeroJudge 題目連結：b367. 翻轉世界

解題想法

可以用二維串列儲存圖的內容，再從上下兩端逐行檢查，下方的列前後順序對調之後內容是否與上方的列相同；如果共有奇數列，還要再單獨檢查中間的列。也可以將圖的內容接成很長的一維串列，只要從兩端往中間依序檢查數字是否相同，寫起來比較簡單。

Python 程式碼

用二維串列儲存圖的內容，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

def check(grid):  # 輸入圖，判斷是否轉 180 度之後對稱
    n, m = len(grid), len(grid[0])  # 圖的尺寸
    for i in range(n//2):  # 從上下兩端往中間檢查
        if grid[i] != grid[n-i-1][::-1]:  # 如果將底下的列翻轉之後不相等
            return False  # 回傳 False
    if n%2 == 1:  # 如果為奇數列，再檢查中間的列
        if grid[n//2] != grid[n//2][::-1]:
            return False
    return True  # 最後回傳 True

t = int(input())  # t 張圖
for _ in range(t):  # 執行 t 次
    n, m = map(int, input().split())  # 圖的尺寸 n*m
    grid = [list(map(int, input().split())) for _ in range(n)]  # 讀取圖
    print("go forward" if check(grid) else "keep defending")

ZeroJudge 解題筆記：b265. Q11286 - Conformity

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


ZeroJudge 題目連結：b265. Q11286 - Conformity

解題想法

這個題目的中文敘述很奇怪。題目的意思應該是要統計各種課程組合的選課人數，例如

3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100

第 2、4 列是一樣的課程組合，因此答案為 2。另一筆範例測資

3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444

因為 2、3、4 列是不一樣的課程組合，各有 1 個人選擇這個組合，題目是將所有最多選課人數的課程組合都加起來，所以答案為 3。

Python 程式碼

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

import sys
from collections import defaultdict

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    cnt = defaultdict(int)
    for _ in range(n):
        course = tuple(sorted(list(map(int, sys.stdin.readline().split()))))
        cnt[course] += 1
    ans = imax = 0
    for v in cnt.values():
        if v > imax:
            ans = v; imax = v
        elif v == imax:
            ans += v
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a982. 迷宮問題#1

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


ZeroJudge 題目連結：a982. 迷宮問題#1

解題想法

這題我用 BFS 解題。可以用兩個二維串列分別儲存地圖及步數，也可以用一個二維串列儲存步數，-1 代表邊界。

Python 程式碼

用兩個二維串列，分別儲存地圖及步數。使用時間約為 33 ms，記憶體約為 3.9 MB，通過測試。

from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input()) for _ in range(n)]  # 地圖資料
steps = [[0]*n for _ in range(n)]  # 步數資料
steps[1][1] = 1  # 起點為 (1, 1)，步數 1
que = deque([(1, 1)])  # 待走訪佇列，先放入 (1, 1)
while que:  # BFS
    r, c = que.popleft()  # 目前的座標 (r, c)
    for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要測試的點 (nr, nc)
        if grid[nr][nc] == '#' or steps[nr][nc] != 0:  # 如果是邊界或已走過
            continue  # 找下一個點
        steps[nr][nc] = steps[r][c] + 1  # 更新 (nr, nc) 的步數
        que.append((nr, nc))  # (nr, nc) 加到 que
### End of BFS ###
# 如果 (n-2, n-2) 此格不是 0，有解；反之無解
print(steps[n-2][n-2] if steps[n-2][n-2] != 0 else "No solution!")

ZeroJudge 解題筆記：a981. 求和問題

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


ZeroJudge 題目連結：a981. 求和問題

解題想法

這題要用遞迴窮舉所有的組合，輸出其中符合條件的組合，並且要適當地剪枝，節省運算時間。不過我在 Python 一直沒有寫出能夠過關的程式碼，最後一筆測資超時。

Python 程式碼

最後一筆測資超時。

def solve():
    import sys
    lines = sys.stdin.readlines()
    head = 0
    while head < len(lines):
        n, m = map(int, lines[head].split())  # 讀取數量 n，要找的加總 m
        nums = sorted(list(map(int, lines[head+1].split())))  # 讀取候選的數值
        head += 2  # 從 lines 讀取資料的索引值
        choice = [False]*n  # 是否選這個數字
        have_ans = False  # 是否有解
        ### 主要的解題過程，輸入目前檢測的 nums 索引值，加總 ###
        def backtrack(curr, total):
            nonlocal have_ans  # 這樣才能改變外層 have_ans 的值
            if total == m:  # 有解，印出選擇的數字，結束遞迴
                have_ans = True
                solution = " ".join([str(num) for i, num in enumerate(nums) if choice[i]])
                sys.stdout.write(f"{solution}\n")
                return
            if curr == n or total > m: return # 已出界或是目標為負值，結束遞迴
            choice[curr] = True  # 選此項
            backtrack(curr + 1, total + nums[curr])  # 遞迴，索引值加 1，total 加上此項的值
            choice[curr] = False  # 回溯，不選此項
            backtrack(curr + 1, total)  # 遞迴，索引值加 1，total 不變
        ### End of backtrack ###
        backtrack(0, 0)  # 從索引值 0、加總 0 開始
        if not have_ans: sys.stdout.write("-1\n")  # 如果無解，印出 -1
        
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：a915. 二维点排序

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


ZeroJudge 題目連結：a915. 二维点排序

解題想法

這題在 Python 先將座標 (x, y) 組成 tuple 再存入 list，再用 sort 將 list 排序。在 C++ 可以用 pair 或自訂 struct 儲存座標 (x, y)，再存入 array 或 vector，再用 algorithm 函式庫的 sort 排序。

Python 程式碼

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

n = int(input())
arr = sorted([tuple(map(int, input().split())) for _ in range(n)])
for a in arr: print(*a)

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

n = int(input())
for a in sorted([tuple(map(int, input().split())) for _ in range(n)]): print(*a)

ZeroJudge 解題筆記：a746. 画蛇添足

作者：王一哲
日期：2025年7月16日


ZeroJudge 題目連結：a746. 画蛇添足

解題想法

這題的測資 2 有空行，如果用 Python 需要過濾掉空行，否則會出錯。而且這題的記憶體限制很嚴格，如果用 Python 直接産生 $(n+2) \times (n+2)$ 的二維串列會超過記憶體上限。

Python 程式碼

第3行是為了濾掉測資中的空行，但是這樣測試不會過，因為本題的記憶體限制很嚴格，在第 7 行産生 $(n+2) \times (n+2)$ 的二維串列時會超過記憶體上限。

import sys

lines = [line for line in sys.stdin.readlines() if line.strip()]
idx = 0

while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    grid = [[" "]*(n+2) for _ in range(n+2)]
    for c in range(n+2):
        grid[0][c] = grid[n+1][c] = "-"
    for r in range(1, n+1):
        grid[r][0] = grid[r][n+1] = "|"
    ri, ci = map(int, lines[idx].split())
    idx += 1
    for _ in range(m-1):
        rf, cf = map(int, lines[idx].split())
        idx += 1
        if ri == rf:
            for c in range(min(ci, cf), max(ci, cf)+1):
                grid[ri][c] = "*"
        elif ci == cf:
            for r in range(min(ri, rf), max(ri, rf)+1):
                grid[r][ci] = "*"
        ri, ci = rf, cf
    for row in grid:
        sys.stdout.write("".join(row) + "\n")

ZeroJudge 解題筆記：a740. 质因数之和

作者：王一哲
日期：2025年7月15日


ZeroJudge 題目連結：a740. 质因数之和

解題想法

測試 i = 2 ~ 根號 x 是否為 x 的因數，如果 i 是因數就繼續將 x 縮小為 1/i，直到 i 不是因數為止。最後如果 x 不等於 1，代表此時 x 是某一個質數，答案再加上 x。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)
    ans = 0
    for i in range(2, int(x**0.5)+1):  # 測試 2 ~ 根號 x
        while x%i == 0:  # 如果 i 可以整除 x
            ans += i  # 加上 i
            x //= i  # x 變為 1/i
    if x != 1: ans += x  # 如果 x 不是 1，x 為質數
    sys.stdout.write(f"{ans:d}\n")

ZeroJudge 解題筆記：a694. 吞食天地二

作者：王一哲
日期：2025年7月14日


ZeroJudge 題目連結：a694. 吞食天地二

解題想法

題目中的 x 軸應該是對應到列，y 軸對應到欄，有點奇怪。解題技巧主要利用的是二維前綴和，産生前綴和的原則

psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1]

因為 $psum[i-1][j-1]$ 會被多加一次，最後要扣掉。用前綴和取範圍 $[r1, c1]$ 到 $[r2, c2]$ 區間和的原則

isum = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]

因為 $psum[r1-1][c1-1]$ 會被多扣一次，最後要加回來。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    psum = [[0]*(n+1) for _ in range(n+1)]  # 最上面、最左邊補 0
    for i in range(1, n+1):  # 讀取 n 行資料
        row = [0] + list(map(int, sys.stdin.readline().split()))
        for j in range(1, n+1):  # 處理前綴和
            psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + row[j]
    for _ in range(m):  # 讀取 m 行
        r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
        isum = psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]
        sys.stdout.write(f"{isum:d}\n")

ZeroJudge 解題筆記：a693. 吞食天地

作者：王一哲
日期：2025年7月13日


ZeroJudge 題目連結：a693. 吞食天地

解題想法

用前綴和解題，如果要求陣列中索引值 [left, right] 的區間和，即為前綴和 psum[right] - psum[left-1]。

Python 程式碼

逐行讀取測資、輸出結果，使用時間約為 0.5 s，記憶體約為 11.8 MB，通過測試。如果改用 print 輸出答案，使用時間約為 1.2 s，記憶體約為 11.7 MB。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    psum = [0] + list(map(int, sys.stdin.readline().split()))
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, sys.stdin.readline().split())
        isum = psum[right] - psum[left-1]
        sys.stdout.write(f"{isum:d}\n")

一次讀取所有測資，最後再一次輸出所有結果，使用時間約為 0.5 s，記憶體約為 36.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    n, m = map(int, lines[idx].split())
    idx += 1
    psum = [0] + list(map(int, lines[idx].split()))
    idx += 1
    for i in range(1, n+1):  # 轉成前綴和
        psum[i] += psum[i-1]
    for _ in range(m):  # 讀取 m 行
        left, right = map(int, lines[idx].split())
        idx += 1
        isum = psum[right] - psum[left-1]
        result.append(f"{isum:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a248. 新手訓練 ~ 陣列應用

作者：王一哲
日期：2025年7月12日


ZeroJudge 題目連結：a248. 新手訓練 ~ 陣列應用

解題想法

理論上這題是要先計算 a, b 相除的商，接著再取 a %= b，每次將 a 乘以 10 倍之後除以 b，計算小數的部分直到 n 位數為止，但是這個作法在 Python 會太慢。反而可以利用 Python 支援大數運算的特性，直接將 a%b 乘以 $10^n$ 再除以 b 計算小數的部分，但是要記得在小數部分前面補 0 到 n 位數。

Python 程式碼

寫法1，超時。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.rstrip(): continue
    a, b, n = map(int, line.split())
    int_part = a//b
    a %= b
    res = [f"{int_part:d}."]
    for _ in range(n):
        a *= 10
        c = a//b
        res.append(f"{c:d}")
        a %= b
    result.append("".join(res) + "\n")
sys.stdout.write("".join(result))

寫法2，大數運算，使用時間約為 0.5 s，記憶體約為 17.2 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.rstrip(): continue
    a, b, n = map(int, line.split())
    int_part = a//b
    dec_part = str(a%b*(10**n) // b).zfill(n)
    result.append(f"{int_part:d}.{dec_part}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a528. 大數排序

作者：王一哲
日期：2025年7月11日


ZeroJudge 題目連結：a528. 大數排序

解題想法

因為 Python 支援大數運算，可以直接排序。C++ 則要用字串格式，分成兩個字串 a、b 開頭都是 +，開頭都是 -，a 正 b 負、a 負 b 正，共 4 種狀況排序。

Python 程式碼

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

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    nums = sorted([int(sys.stdin.readline()) for _ in range(n)])
    result = [f"{num:d}\n" for num in nums]
    sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a524. 手機之謎

作者：王一哲
日期：2025年7月10日


ZeroJudge 題目連結：a524. 手機之謎

解題想法

這題在 Python 可以用 itertools.permutations，在 C++ 可以用 algorithm 函式庫的 prev_permutation 産生所有的排列，速度很快。也可以用函式遞迴産生所有的排列方式。由於測資有空行，用 Python 解題時要記得跳過空行，否則會吃 RE。

Python 程式碼

寫法1，用 itertools.permutations 産生所有的排列，使用時間約為 0.2 s，記憶體約為 7.5 MB，通過測試。

import sys
from itertools import permutations

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    for arr in permutations(range(n, 0, -1), n):  # 從 n ~ 1 的數字取 n 個排列
        res = [f"{a:d}" for a in arr]  # arr 的內容轉成字串存入 res
        result.append("".join(res) + "\n")  # res 接成一個字串加入 result
sys.stdout.write("".join(result))  # 一次輸出所有的結果

寫法2，用函式遞迴窮舉所有的排列，使用時間約為 0.4 s，記憶體約為 7.5 MB，通過測試。

import sys

result = []
def perm(arr, nums, used, depth):
    # 代入已選數字串列 arr, 可用數字串列 nums，已選數字的集合 used，目標長度 depth
    if len(arr) == depth:  # 遞迴出口，如果 arr 長度等於 depth
        result.append("".join([f"{a:d}" for a in arr]) + "\n")  # 接成字串加入 result
        return
    for num in nums:  # 依序由 nums 讀取數字
        if num in used: continue  # 如果 num 已用過，找下一個數字
        arr.append(num)  # num 接到 arr 最後面
        used.add(num)  # num 加入 used
        perm(arr, nums, used, depth)  # 遞迴
        arr.pop()  # 從 arr 最後面移除數字
        used.remove(num)  # 從 used 移除 num

lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    perm([], list(range(n, 0, -1)), set(), n)
sys.stdout.write("".join(result))  # 一次輸出所有的結果

ZeroJudge 解題筆記：a417. 螺旋矩陣

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


ZeroJudge 題目連結：a417. 螺旋矩陣

解題想法

我是先填完矩陣的值再輸出，速度會慢一點。

Python 程式碼

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

def draw(n, m):
    ### 填格子 ###
    if m == 1:  # 方向順序是右、下、左、上
        dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)
    else:  # 方向順序是下、右、上、左
        dr, dc = (1, 0, -1, 0), (0, 1, 0, -1)
    matrix = [[0]*n for _ in range(n)]  # n*n 矩陣，預設值皆為 0
    r, c, v = 0, 0, 1  # 座標 (r, c)，值為 1
    d = 0  # 一開始朝右方或下
    while v < n*n:  # 還沒有填完
        matrix[r][c] = v  # 設定此格的值
        nr, nc = r+dr[d], c+dc[d]  # 要走的格子
        if nr < 0 or nr >= n or nc < 0 or nc >= n or matrix[nr][nc] != 0:  # 出界或已經填過了
            d = (d+1)%4  # 轉向
            nr, nc = r+dr[d], c+dc[d]  # 更新 (nr, nc)
        r, c = nr, nc  # 走到 (nr, nc)
        v += 1  # 值加 1
    matrix[r][c] = v  # 設定最後一格的值
    ### 輸出 ###
    for row in matrix:
        for c, v in enumerate(row):
            print(f"{v:5d}", end="\n" if c == n-1 else "")

T = int(input())
for t in range(T):
    if t > 1: print()
    draw(*map(int, input().split()))

ZeroJudge 解題筆記：a414. 位元運算之進位篇

作者：王一哲
日期：2025年7月8日


ZeroJudge 題目連結：a414. 位元運算之進位篇

解題想法

假設二進位制數字 $n$ 要加 1，其進位次數等於 $n$ 從最右側向左算共有幾個連續的 1。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 65.9 MB，通過測試。這題的測資量很大，用 print 輸出會很慢，大約要 2 s。

import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n == 0: break
    cnt = 0
    while n&1:
        n >>= 1
        cnt += 1
    result.append(f"{cnt:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a410. 解方程

作者：王一哲
日期：2025年7月7日


ZeroJudge 題目連結：a410. 解方程

解題想法

這題用克拉瑪公式，假設二元一次方程式為 $$ \left\{\begin{matrix} a_1 x + b_1 y &= c_1 \\ a_2 x + b_2 y &= c_2 \end{matrix}\right. $$ 令 $$ \Delta = \begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{vmatrix} ~~~~~\Delta_x = \begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \end{vmatrix} ~~~~~\Delta_y = \begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \end{vmatrix} $$ 有以下三種狀況

1. 如果 $\Delta \neq 0$，方程式恰有一組解，其解為 $x = \frac{\Delta_x}{\Delta}, ~ y = \frac{\Delta_y}{\Delta}$
2. 如果 $\Delta = 0$，但 $\Delta_x, \Delta_y$ 至少有一個不為 0，無解。
3. 如果 $\Delta = \Delta_x = \Delta_y = 0$，無限多組解。

Python 程式碼

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

a1, b1, c1, a2, b2, c2 = map(int, input().split())
delta = a1*b2 - a2*b1
deltax = c1*b2 - c2*b1
deltay = a1*c2 - a2*c1
if delta != 0:  # 恰有一組解
    print(f"x={deltax/delta:.2f}")
    print(f"y={deltay/delta:.2f}")
else:
    if deltax != 0 or deltay != 0: print("No answer")   # 無解
    elif deltax == 0 and deltay == 0: print("Too many") # 無窮多組解

ZeroJudge 解題筆記：a291. nAnB problem

作者：王一哲
日期：2025年7月6日


ZeroJudge 題目連結：a291. nAnB problem

解題想法

先掃過一次答案與猜測的數字，計算位置、數字都對的數量 A，如果不是位置、數字都對，則用兩個串列記錄 0 ~ 9 各個數字的數量。接下來再掃過這兩個串列，計算位置不對、數字對的數量 B。但是這一題我在 Python 上遇到很大的困難，換了好幾種寫法都超時，用 C++ 會過關但是速度還不夠快，需要改變寫法。

Python 程式碼

超時。

import sys
   
result = []
for line in sys.stdin:
    if not line.rstrip(): continue
    ans = list(map(int, line.split()))
    n = int(sys.stdin.readline())
    for _ in range(n):
        guess = list(map(int, sys.stdin.readline().split()))
        A, B = 0, 0  # 位置、數字都對的數量 A，位置不對、數字對的數量 B
        cnt_a, cnt_g = [0]*10, [0]*10  # 0 ~ 9 各個數字的數量
        for a, g in zip(ans, guess):  # 先掃一輪
            if a == g: A += 1  # 位置、數字都對，A 加 1
            else:  # 反之，記錄數字對應的數量
                cnt_a[a] += 1
                cnt_g[g] += 1
        for a, g in zip(cnt_a, cnt_g):  # 計算 B 的數量
            if a >= g: B += g
            else: B += a
        result.append(f"{A:d}A{B:d}B\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：a229. 括號匹配問題

作者：王一哲
日期：2025年7月5日


ZeroJudge 題目連結：a229. 括號匹配問題

解題想法

我用函式遞迴枚舉所有可能的組合，但是 Python 的部分一直超時，C++ 的部分用 string 儲存字串會超時，要用字元陣列才能過關。

Python 程式碼

寫法1，用字串儲存答案，超時。

import sys

def solve(n):
    """
    輸入括號對數 n，枚舉所有合法的組合
    """
    if n == 0: return [""]  # 特例，回傳只有空字串的串列
    result = []  # 儲存組合用的串列
    def backtrack(curr, left, right):
        """
        回溯，輸入現在的字串 curr、左括號數量 left、右括號數量 right
        """
        if left == n and right == n:  # 找到新的組合，加到 result
            result.append(f"{curr}\n")
            return
        if left < n:  # 如果左括號數量不夠，回溯，加上 (
            backtrack(curr+"(", left+1, right)
        if right < left:  # 如果右括號比左括號少，回溯，加上 )
            backtrack(curr+")", left, right+1)
    ### End of backtrack ###
    backtrack("", 0, 0)  # 呼叫 backtrack
    return result

ca = 0
for line in sys.stdin:
    if not line.rstrip(): continue
    ca += 1
    if ca > 1: sys.stdout.write("\n")
    sys.stdout.write("".join(solve(int(line))))

ZeroJudge 解題筆記：a225. 明明愛排列

作者：王一哲
日期：2025年7月4日


ZeroJudge 題目連結：a225. 明明愛排列

解題想法

這題在 Python 可以用內建的排序工具 sort，搭配 functools.cmp_to_key 與自訂比較式；在 C++ 可以用 algorithm 函式庫的 sort，搭配 lambda function 自訂比較式，寫起來會快很多。

Python 程式碼

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

import sys
from functools import cmp_to_key

def mycmp(a, b):
    if a%10 == b%10:
        if a > b: return -1
        elif a < b: return 1
        else: return 0
    elif a%10 < b%10: return -1
    else: return 1

for line in sys.stdin:
    n = int(line)
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort(key = cmp_to_key(mycmp))
    print(*arr)

ZeroJudge 解題筆記：a224. 明明愛明明

作者：王一哲
日期：2025年7月3日


ZeroJudge 題目連結：a224. 明明愛明明

解題想法

先將所有字母轉成小寫，再用字典或表格計數，計算每個字母出現的次數，同時計算所有字母的數量 n。如果 n 是奇數，只能有一個字母的數量是奇數；如果 n 是偶數，所有的字母數量都必須是偶數。

Python 程式碼

寫法1，字典計數，使用時間約為 22 ms，記憶體約為 3.6 MB，通過測試。

import sys
from collections import defaultdict

def check(s):
    n = 0
    cnt = defaultdict(int)
    for c in s.lower():
        n += 1
        if c.isalpha():
            cnt[c] += 1
    even = sum(v%2 for v in cnt.values())
    if n%2 == 1:
        return even <= 1
    else:
        return even == 0

for line in sys.stdin:
    print("yes !" if check(line.rstrip()) else "no...")

ZeroJudge 解題筆記：a216. 數數愛明明

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


ZeroJudge 題目連結：a216. 數數愛明明

解題想法

方法1，使用函式遞迴，但是可能會因為遞迴次數太多而超時。方法2，找一般式，例如 $$ \begin{align*} f(1) &= 1\\ f(2) &= 2 + f(1)\\ f(3) &= 3 + f(3)\\ & \vdots \\ f(n) &= n + f(n-1) \end{align*} $$ 將以上式子相加可得 $$ f(n) = 1 + 2 + 3 + \dots + n = \frac{1}{2} \cdot n(n+1) $$ 接下來求 $g(n)$，先列出幾行 $$ \begin{align*} g(1) &= 1\\ g(2) &= f(2) + g(1)\\ g(3) &= f(3) + g(2)\\ & \vdots \\ g(n) &= f(n) + g(n-1) \end{align*} $$ 將以上式子相加可得 \begin{align*} g(n) &= f(1) + f(2) + f(3) + \dots + f(n)\\ &= \frac{1}{2} \sum_{i=1}^n (i^2 + i)\\ &= \frac{1}{2} \cdot \left [ \frac{1}{6} \cdot n(n+1)(2n+1) + \frac{1}{2} \cdot n(n+1) \right ]\\ &= \frac{1}{12} \cdot n(n+1) \left [ (2n+1) + 3 \right ] \\ &= \frac{1}{6} \cdot n(n+1)(n+2)\\ \end{align*}

Python 程式碼

方法1，使用函式遞迴，果然不意外地在測試題會超時。

import sys

def f(n):
    if n == 1: return 1
    else: return n + f(n-1)

def g(n):
    if n == 1: return 1
    else: return f(n) + g(n-1)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

方法2，找出一般式直接代入 n 求答案，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def f(n):
    return int(n*(n+1)/2)

def g(n):
    return int(n*(n+1)*(n+2)/6)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

ZeroJudge 解題筆記：a054. 電話客服中心

作者：王一哲
日期：2025年7月1日


ZeroJudge 題目連結：a054. 電話客服中心

解題想法

先取英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起，存到一個對應的陣列之中。依照規則計算數字部分的編碼 code，加上英文字母對應的值要能被 10 整除，因此答案就是 (10 - code%10) % 10 對應的字母。

Python 程式碼

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

# 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
letters = ("BNZ", "AMW", "KLY", "JVX", "HU", "GT", "FS", "ER", "DOQ", "CIP")
s = input()  # 身分證字號
# 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
code = sum(int(c)*(8-i) for i, c in enumerate(s[:9])) + int(s[-1])
print(letters[(10 - code%10) % 10])

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
    string letters[10] = {"BNZ", "AMW", "KLY", "JVX", "HU", 
                          "GT", "FS", "ER", "DOQ", "CIP"};
    string s; cin >> s;  // 身分證字號
    // 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
    int code = 0;
    for(int i=0; i<9; i++) code += (s[i]-'0')*(8-i);
    code += s.back() - '0';
    cout << letters[(10 - code%10) % 10] << "\n";
    return 0;
}