ZeroJudge 解題筆記：c089. 00389 - Basically Speaking

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


ZeroJudge 題目連結：c089. 00389 - Basically Speaking

解題想法

由於 Python 的 int 內建了用指定進位制將字串轉換成 10 進位整數的功能，這部分可以使用預設工具；但是輸出格式之中沒有對應 7 進位制的工具，需要自己寫。而 C++ 則是兩個部分都要自己寫。

Python 程式碼

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

import sys

def ntos(n, base):  # 輸入整數 n、基底 base，輸出轉換後的字串
    # 數字 0 ~ 15 對應的字元
    table = {0: '0', 1: '1', 2: '2', 3: '3',
             4: '4', 5: '5', 6: '6', 7: '7',
             8: '8', 9: '9', 10: 'A', 11: 'B',
             12: 'C', 13: 'D', 14: 'E', 15: 'F'}
    s = ""  # 儲存結果用的字串
    while n > 0:  # 如果 n 大於 0 繼續執行
        s = table[n%base] + s  # 取 n%base 對應的字元加到 s 前面
        n //= base  # n 變為 1/base 倍
    return s  # 回傳 s

for line in sys.stdin:
    arr = line.split()  # 分割後會轉為串列存到 arr
    # 先將字串用指定的基底 arr[1] 轉成 10 進位整數，再用 ntos 轉成 arr[2] 進位字串
    s = ntos(int(arr[0], int(arr[1])), int(arr[2]))
    m = len(s)  # s 的長度
    if m > 7: print("  ERROR")  # 長度大於 7，印出  ERROR
    else: print(" "*(7-m) + s)  # 反之前面補空格到長度為 7 再輸出

ZeroJudge 解題筆記：c088. 00516 - Prime Land

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


ZeroJudge 題目連結：c088. 00516 - Prime Land

解題想法

讀取一行測資，再每次讀取測資中的兩個數字，分別為底數及次方，將這個數字 $n$ 還原成 10 進位；接下來對 $n-1$ 做質因數分解，依照題目要求的格式輸出答案。

Python 程式碼

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

import sys

for line in sys.stdin:
    if line.rstrip() == "0": break
    arr = list(map(int, line.split()))  # 讀取一行資料
    n, m = 1, len(arr)  # n 儲存測資對應的整數，測資長度 m
    for i in range(0, m, 2):  # 一次讀取測資中的兩個數字
        n *= arr[i]**arr[i+1]  # 計算 n
    n -= 1  # 題目要算 n-1 的質因數分解結果
    curr = n  # 儲存 n-1，之後的計算會改變量值
    ans = []  # 答案
    for i in range(2, int(n**0.5)+1):  # 測試 2 ~ sqrt(n) 的質因數
        p = 0  # i 的次方
        while curr%i == 0:  # 如果 curr 能被 i 整除
            p += 1  # 次方加 1
            curr //= i  # curr 變為 1/i 倍
        if p > 0: ans += [p, i]  # 如果 p 大於 0，ans 加上 [p, i]
    if curr > 1: ans += [1, curr]  # 如果 curr 大於 1，ans 要加上 [1, curr]
    if not ans: print(n, 1)  # 如果 ans 是空的，n 是因數，輸出 n 1
    else: print(*ans[::-1])  # 題目要求因數由大到小輸出

ZeroJudge 解題筆記：c087. 00412 - Pi

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


ZeroJudge 題目連結：c087. 00412 - Pi

解題想法

如果測資提供 $n$ 個數字，所有的數對共有 $$ tot = C_n^2 = \frac{n(n-1)}{2} $$ 如果其中有 $cnt$ 組互質，則 $$ \frac{6}{\pi^2} = \frac{cnt}{tot} ~\Rightarrow~ \pi = \sqrt{\frac{6 \times tot}{cnt}} $$

Python 程式碼

用 itertools.combinations 産生數對組合，使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys, itertools, math

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    nums = [int(sys.stdin.readline()) for _ in range(n)]
    cnt, tot = 0, n*(n-1)//2
    for a, b in itertools.combinations(nums, 2):
        if math.gcd(a, b) == 1: cnt += 1
    if cnt == 0:
        print("No estimate for this data set.")
    else:
        print(f"{(6*tot/cnt)**0.5:.6f}")

用遞迴枚舉所有的數對組合，使用時間約為 7 ms，記憶體約為 2.9 MB，通過測試。

import sys, math

def comb(nums, arr, cnt):
    if len(arr) == 2:
        if math.gcd(*arr) == 1: return cnt+1
        return cnt
    for i in range(len(nums)):
        arr.append(nums[i])
        cnt = comb(nums[i+1:], arr, cnt)
        arr.pop()
    return cnt

for line in sys.stdin:
    n = int(line)
    if n == 0: break
    nums = [int(sys.stdin.readline()) for _ in range(n)]
    tot = n*(n-1)//2
    cnt = comb(nums, [], 0)
    if cnt == 0:
        print("No estimate for this data set.")
    else:
        print(f"{(6*tot/cnt)**0.5:.6f}")

ZeroJudge 解題筆記：c086. 00402 - M*A*S*H

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


ZeroJudge 題目連結：c086. 00402 - M*A*S*H

解題想法

很像約瑟夫環的題目，但是測資不大，直接模擬淘汰的過程即可。

Python 程式碼

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

import sys

ca = 0  # 第幾筆測資
for line in sys.stdin:
    ca += 1  # 加1
    if ca > 1: print()  # 如果不是第1筆測資，換行
    arr = list(map(int, line.split()))  # 讀取一行資料
    n, x = arr[0], arr[1]  # n 個人參加，x 個人可以放假
    persons = [i for i in range(1, n+1)]  # 産生 1 ~ n 的編號
    for k in arr[2:]:  # 依序讀取 20 張牌的數字
        if n == x: break  # 如果剩下 x 個人，中止迴圈
        idx = k-1  # 淘汰者的索引值，初始值為 k-1
        while n > x and idx < n:  # 如果人數大於 x 而且 idx 還沒有出界
            persons.pop(idx)  # 淘汰索引值為 idx 的人
            n -= 1  # 人數減 1
            idx += k-1  # 下一個索引值加 k-1，因為淘汰一個人，不是加 k
    print(f"Selection #{ca:d}")  # 印出答案
    print(*persons)

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

import sys

result = []
data = sys.stdin.read().split()
ptr = 0
ca = 0  # 第幾筆測資
while ptr < len(data):
    ca += 1  # 加1
    if ca > 1: result.append("\n")  # 如果不是第1筆測資，換行
    n = int(data[ptr])  # n 個人參加
    x = int(data[ptr+1])  # x 個人可以放假
    ptr += 2
    persons = list(range(1, n+1))  # 産生 1 ~ n 的編號
    cards = list(map(int, data[ptr:ptr+20]))
    ptr += 20
    for k in cards:  # 依序讀取 20 張牌的數字
        if n == x: break  # 如果剩下 x 個人，中止迴圈
        idx = k-1  # 淘汰者的索引值，初始值為 k-1
        while n > x and idx < n:  # 如果人數大於 x 而且 idx 還沒有出界
            persons.pop(idx)  # 淘汰索引值為 idx 的人
            n -= 1  # 人數減 1
            idx += k-1  # 下一個索引值加 k-1，因為淘汰一個人，不是加 k
    result.append(f"Selection #{ca:d}\n")  # 印出答案
    res = " ".join(map(str, persons))
    result.append(f"{res}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：c084. 00275 - Expanding Fractions

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


ZeroJudge 題目連結：c084. 00275 - Expanding Fractions

解題想法

這題要依序處理每個位數相除的結果，如果無法整除時要將餘數乘以 10 再繼續往下除，同時記錄每個餘出現過的位置，直到先找循環節的終點為止。最後還要依照題目要求的格式輸出答案。

Python 程式碼

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

import sys

def divid(a, b):  # a < b, 計算 a/b
    dec_part = []  # 小數部分
    repeat_start = -1  # 循環小數起點
    rem = a  # 餘數，由於題目限制 a < b，初始值為 a
    rem_pos = dict()  # 用字典儲存出現過的餘數位置
    while rem != 0:  # 如果無法整除繼續執行
        if rem in rem_pos:  # 如果這個餘數已經出現過
            repeat_start = rem_pos[rem]  # 設定循環的起點
            break  # 中止迴圈
        rem_pos[rem] = len(dec_part)  # 記錄這個餘數的位置
        rem *= 10  # 將餘數放大為 10 倍
        dec_part.append(str(rem//b))  # 小數部分加一位
        rem %= b  # 新的餘數
    ans = "." + "".join(dec_part)  # 要輸出的答案
    for i in range(0, len(ans), 50):  # 逐行輸出，每行最多 50 個字元
        print(ans[i:i+50])
    if repeat_start == -1:  # 不循環
        print("This expansion terminates.")
    else:  # 循環
        print(f"The last {len(dec_part)-repeat_start:d} digits repeat forever.")

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    divid(n, m)

如果題目改成要計算相除的小數並標示循環節，可以這樣寫。

import sys

def divid(a, b):  # a < b, 計算 a/b
    int_part = str(a//b)  # 整數部分
    rem = a%b  # 餘數
    """ 特例，可以整除，回傳整數部分 """
    if rem == 0: return int_part
    """ 繼續處理小數部分 """
    dec_part = []  # 小數部分
    repeat_start = -1  # 循環小數起點
    rem_pos = dict()  # 用字典儲存出現過的餘數位置
    while rem != 0:  # 如果無法整除繼續執行
        if rem in rem_pos:  # 如果這個餘數已經出現過
            repeat_start = rem_pos[rem]  # 設定循環的起點
            break  # 中止迴圈
        rem_pos[rem] = len(dec_part)  # 記錄這個餘數的位置
        rem *= 10  # 將餘數放大為 10 倍
        dec_part.append(str(rem//b))  # 小數部分加一位
        rem %= b  # 新的餘數
    if repeat_start == -1:  # 不循環
        return int_part + "." + "".join(dec_part)
    else:  # 循環，用 () 標示循環節
        return int_part + "." + "".join(dec_part[:repeat_start]) \
               + "(" + "".join(dec_part[repeat_start:]) + ")"

for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    print(divid(n, m))

ZeroJudge 解題筆記：c083. 00130 - Roman Roulette

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


ZeroJudge 題目連結：c083. 00130 - Roman Roulette

解題想法

這題的題目敘述很怪，試了很多種排法才弄懂題目的意思。為了簡化問題，我將人排成一列，順時鐘方向是向右，如果到了最後一位就從最左邊開始算。計算規則如下：

1. 首先是題目要找的起點位置，在計算第一個受害者的位置時，是從起點的左邊那個人開始向右算 k 個人，不是從起點開始算。
2. 計算埋葬者原來的位置時，是從受害者左邊那個人開始向右算 k 個人，將埋葬者的位置移動到受害者的位置。
3. 計算下一個受害者的位置時，是從前一個受害者，也就是埋葬者所在位置左邊那個人開始向右算 k 個人。
4. 如果 1 號死亡，可以中止迴圈，再找下一個起點。
5. 如果存活人數剩下一個，而且這個人是 1 號，找到答案，回傳起點位置。

以範例測資 $n = 5, k = 2, i = 1$ 為例，起始及每一輪的狀態如下

起始: [1, 2, 3, 4, 5]
第1輪: 起點編號 5, 受害者編號 2, 埋葬者編號 4, 目前存活的人 [1, 4, 3, 5]
第2輪: 起點編號 4, 受害者編號 5, 埋葬者編號 4, 目前存活的人 [1,  3, 4]
第3輪: 起點編號 4, 受害者編號 3, 埋葬者編號 1, 目前存活的人 [1, 4]
第4輪: 起點編號 1, 受害者編號 1, 目前存活的人 [4]

Python 程式碼

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

import sys

def solve(n, k):  # 用串列模擬過程求解
    for i in range(1, n+1):  # 依序測試起點編號 1 ~ n
        persons = [j for j in range(1, n+1)]  # 編號 1 ~ n 的人
        pos, m = (i-2+n)%n, n  # 起點位置其實是 i 的左側，轉成索引值再減 1；存活人數 m
        alive = True  # 1 號是否存活
        while m > 1 and alive:  # 如果 m 大於 1 且 1 號還活著，繼續執行
            vpos = (pos+k)%m  # 受害者索引值
            victim = persons.pop(vpos)  # 從 persons 移除受害者
            m -= 1  # 存活人數減 1
            if victim == 1: alive = False  # 如果 1 號死亡，alive 改成 False
            if m == 1: break  # 如果 m 等於 1，中止迴圈
            bpos = (vpos-1+k)%m  # 埋葬者索引值
            burier = persons.pop(bpos)  # 從 persons 移除埋葬者
            if bpos < vpos:  # 如果埋葬者在受害者左側
                persons.insert(vpos-1, burier)  # vpos 減 1，於 persons 插入埋葬者
                pos = (vpos-1+m)%m  # 更新下一輪的起點索引值
            else:  # 如果埋葬者在受害者右側
                persons.insert(vpos, burier)  # 於 persons 插入埋葬者
                pos = (vpos+m)%m  # 更新下一輪的起點索引值
        if alive: return i  # 如果 1 號存活，回傳 i
    return -1  # 無解，回傳 -1，理論上不會用到

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == 0 and k == 0: break
    print(solve(n, k))

ZeroJudge 解題筆記：c082. 00118 - Mutant Flatworld Expolrers

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


ZeroJudge 題目連結：c082. 00118 - Mutant Flatworld Expolrers

解題想法

這類走格子的題目，我通常會在地圖的周圍加上一圈地圖中原來沒有使用的字元當作邊界，如果走到的格子是這個字元就代表出界，這樣可以不需要檢查索引值的邊界值。
依照題目給的指令，依序更新位置及方向，如果碰掉邊界標示為已掉落，不需要執行之後的指令。如果指令全部執行完還沒有掉落，印出最後的位置。

Python 程式碼

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

import sys

ctod = {'N': 0, 'E': 1, 'S': 2, 'W': 3}
dtoc = ('N', 'E', 'S', 'W')
dx = (0, 1, 0, -1)  # 向東 +x，順序為 NESW
dy = (1, 0, -1, 0)  # 向北 +y，順序為 NESW

n, m = map(int, sys.stdin.readline().split())  # 地圖右上角頂點 (n, m)
# 地圖最右側、最上方加 -1 作為哨兵，0 為未標記，1 為已標記
# grid[y][x] 對應到地圖座標 (x, y)
grid = [[0]*(n+1) + [-1] for _ in range(m+1)]
grid.append([-1]*(n+2))

for line in sys.stdin:
    cmd = list(line.split())
    x, y, d = int(cmd[0]), int(cmd[1]), ctod[cmd[2]]  # 起點座標 (x, y)，方向 d
    lost = False  # 是否掉落
    for c in sys.stdin.readline().rstrip():
        if c == 'R': d = (d+1)%4  # 向右轉90度
        elif c == 'L': d = (d-1+4)%4  # 向左轉90度
        else:  # 前進1格
            nx, ny = x+dx[d], y+dy[d]  # 測試 (ny, nx)
            if grid[ny][nx] == -1:  # (ny, nx) 出界
                if grid[y][x] == 0:  # (y, x) 未標記
                    print(f"{x:d} {y:d} {dtoc[d]:s} LOST")  # 最後的位置
                    grid[y][x] = 1  # 標記 (x, y)
                    lost = True  # 已掉落
                    break  # 中止迴圈，忽略之後的指令
                else: continue  # (y, x) 已標記，執行下一個指令
            else:  # (ny, nx) 未出界
                x, y = nx, ny  # 更新 x, y
    # 執行完指令，未掉落，印出位置及方向
    if not lost: print(f"{x:d} {y:d} {dtoc[d]:s}")

ZeroJudge 解題筆記：c081. 00102 - Ecological Bin Packing

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


ZeroJudge 題目連結：c081. 00102 - Ecological Bin Packing

解題想法

只有 6 種排列方式，分別為 BCG, BGC, CBG, CGB, GBC, GCB，依照這個順序分別計算對應的移動數量，取第一個移動數量最小值。

Python 程式碼

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

import sys

for line in sys.stdin:
    b1, g1, c1, b2, g2, c2, b3, g3, c3 = map(int, line.split())
    # 測試的排列順序為 BCG, BGC, CBG, CGB, GBC, GCB
    ans, imin = "", 1E9
    cnt1 = g1+c1+b2+g2+b3+c3
    if cnt1 < imin:
        ans = "BCG"; imin = cnt1
    cnt2 = g1+c1+b2+c2+b3+g3
    if cnt2 < imin:
        ans = "BGC"; imin = cnt2
    cnt3 = b1+g1+g2+c2+b3+c3
    if cnt3 < imin:
        ans = "CBG"; imin = cnt3
    cnt4 = b1+g1+b2+c2+g3+c3
    if cnt4 < imin:
        ans = "CGB"; imin = cnt4
    cnt5 = b1+c1+g2+c2+b3+g3
    if cnt5 < imin:
        ans = "GBC"; imin = cnt5
    cnt6 = b1+c1+b2+g2+g3+c3
    if cnt6 < imin:
        ans = "GCB"; imin = cnt6
    print(ans, imin)

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

import sys

for line in sys.stdin:
    b1, g1, c1, b2, g2, c2, b3, g3, c3 = map(int, line.split())
    # BCG
    cnt1 = g1+c1+b2+g2+b3+c3
    # BGC
    cnt2 = g1+c1+b2+c2+b3+g3
    # CBG
    cnt3 = b1+g1+g2+c2+b3+c3
    # CGB
    cnt4 = b1+g1+b2+c2+g3+c3
    # GBC
    cnt5 = b1+c1+g2+c2+b3+g3 
    # GCB
    cnt6 = b1+c1+b2+g2+g3+c3
    ans = sorted([(cnt1, "BCG"), (cnt2, "BGC"), (cnt3, "CBG"), (cnt4, "CGB"), (cnt5, "GBC"), (cnt6, "GCB")])
    print(ans[0][1], ans[0][0])

ZeroJudge 解題筆記：c077. 00417 - Word Index

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


ZeroJudge 題目連結：c077. 00417 - Word Index

解題想法

這題給的條件比較寬鬆，先建表列出所有答案再查表也能通過。但如果能夠找出規律，用數學解會快很多。

Python 程式碼

建表，使用時間約為 31 ms，記憶體約為 15.6 MB，通過測試。

import sys

cnt = 0  # 編號
table = dict()  # 表格，內容為{字串: 編號}
# a ~ z 的編號
for i in range(26):
    cnt += 1
    s = chr(i+ord('a'))
    table[s] = cnt
# ab ~ yz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        cnt += 1
        table[t] = cnt
# abc ~ xyz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        for k in range(j+1, 26):
            u = t + chr(k+ord('a'))
            cnt += 1
            table[u] = cnt
# abcd ~ wxyz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        for k in range(j+1, 26):
            u = t + chr(k+ord('a'))
            for x in range(k+1, 26):
                v = u + chr(x+ord('a'))
                cnt += 1
                table[v] = cnt
# abcde ~ vwxyz 的編號
for i in range(26):
    s = chr(i+ord('a'))
    for j in range(i+1, 26):
        t = s + chr(j+ord('a'))
        for k in range(j+1, 26):
            u = t + chr(k+ord('a'))
            for x in range(k+1, 26):
                v = u + chr(x+ord('a'))
                for y in range(x+1, 26):
                    w = v + chr(y+ord('a'))
                    cnt += 1
                    table[w] = cnt
# 讀取測資並查表輸出答案，如果 key 不在 table 之中則輸出 0
for line in sys.stdin:
    print(table.get(line.rstrip(), 0))

數學解，使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

import sys

def comb(n, m):  # C n 取 m
    if m < 0 or m > n: return 0  # 不合法的算式，回傳 0
    m = min(m, n-m)  # 取 m, n-m 較小者
    ans = 1  # 組合數
    for i in range(1, m+1):
        ans = ans*(n-i+1)//i
    return ans

def calculate_code(s):  # 輸入字串，回傳編號
    n, code = len(s), 0  # 字串長度，編號
    # 檢查字符串是否合法，後面的字元大於前面的字元
    for i in range(n-1):
        if s[i+1] <= s[i]:  # 不合法，回傳 0
            return 0
    # 計算長度為 1 ~ n-1 的組合數
    for i in range(1, n):
        code += comb(26, i)
    # 計算長度 n 的排名
    for i in range(n):  # 掃過 s[0] ~ s[n-i]
        start = ord('a') if i == 0 else ord(s[i-1]) + 1  # i = 0 從 a 開始，否則從 s[i-1] 下一個開始
        end = ord(s[i])  # 到 s[i] 的編號為止
        for c in range(start, end):
            code += comb(26 - (c-ord('a')+1), n-i-1)
    # 最後要再加 1
    return code + 1

for line in sys.stdin:
    print(calculate_code(line.rstrip()))

ZeroJudge 解題筆記：c074. 00441 - Lotto

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


ZeroJudge 題目連結：c074. 00441 - Lotto

解題想法

這題可以用遞迴窮舉所有的組合。但如果用 Python 解題，可以用 itertools.combinations 枚舉所有指定數據中取出 6 個的組合，速度比遞迴還快。

Python 程式碼

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

import sys

def solve(cand, arr, depth):
    if len(arr) == depth:
        print(*arr)
        return
    for i in range(len(cand)):
        arr.append(cand[i])
        solve(cand[i+1:], arr, depth)
        arr.pop()
        
first = True
for line in sys.stdin:
    if line.rstrip() == "0": break
    if not first: print()
    first = False
    nums = list(map(int, line.split()))[1:]
    solve(nums, [], 6)

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

import sys
from itertools import combinations

result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
    n = int(data[ptr])
    ptr += 1
    if n == 0: break
    nums = sorted(map(int, data[ptr:ptr+n]))
    ptr += n
    if result: result.append("\n")
    for comb in combinations(nums, 6):
        res = " ".join(map(str, comb))
        result.append(f"{res}\n")
sys.stdout.write("".join(result))