ZeroJudge 解題筆記：d217. 00489 - Hangman Judge

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


ZeroJudge 題目連結：d217. 00489 - Hangman Judge

解題想法

用字典 $state$ 記錄答案中每個字元是否被猜中，為了在檢查時比較好寫，我將還沒有被猜中的字元狀態標記成 True。再用另一個字典 $used$ 記錄已經猜過的字元。接下來依序讀取猜測字串的每個字元，檢查這個字元是否是答案、是否已經猜過，計算猜對的字元數量及猜錯的次數。最後依照猜對的字元數量及猜錯的次數輸出對應的答案。

Python 程式碼

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

def solve():
    import sys

    result = []  # 輸出的內容
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # 編號
        ptr += 1
        if n == -1: break  # 中止迴圈
        result.append(f"Round {n:d}\n")
        ans = data[ptr]  # 答案
        ptr += 1
        state = {c: True for c in ans}  # 答案中各字母狀態，True 為還沒有猜中
        guess = data[ptr]  # 猜測的字串
        ptr += 1
        m, cnt, fails = len(state), 0, 0  # 答案共有 m 個相異字母，猜中 cnt 個，猜錯 fails 次
        used = dict()  # 已經猜過的字母
        """ 檢查是否過關 """
        for c in guess:  # 依序由 guess 讀取字母 c
            if c not in state:  # 如果 c 不在 state 之中
                if c not in used:  # 如果 c 不在 used 之中
                    fails += 1  # 新的猜錯字母，fails 加 1
                    if fails == 7:  break  # 猜錯 7 次，失敗，中止迴圈
            elif state[c]:  # 如果 c 在 state 之中而且 c 還沒有被猜中
                state[c] = False  # 設定為 False
                cnt += 1  # 猜中數量加 1
                if cnt == m: break  # 全部猜中，過關，中止迴圈
            used[c] = True  # c 加入 used
        """ 判斷答案 """
        if fails == 7:  # 失敗
            result.append("You lose.\n")
        else:
            if cnt == m:  # 過關
                result.append("You win.\n")
            else:  # 中離
                result.append("You chickened out.\n")
    """ 輸出答案 """
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d194. 11572 - Unique Snowflakes

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


ZeroJudge 題目連結：d194. 11572 - Unique Snowflakes、d716. Unique Snowflakes(強化版)

解題想法

用滑動視窗解題，用字典 $last$ 記錄每一個編號的雪花上次出現的索引值，視窗左端點為 $left$。接下來依序讀取目前的雪花編號為 $snow$、視窗右端點為 $right$，如果 $last$ 之中有 $snow$ 而且上一次出現的索引值大於等於 $left$，要更新視窗範圍，將 $left$ 改成 $last[snow] + 1$，再將 $last[snow]$ 更新為 $right$；最後更新最大值 $imax$，取 $imax$ 及 $right - left + 1$ 較大者。

Python 程式碼

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

t = int(input())  # t 筆測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # n 片雪花
    snowflake = [int(input()) for _ in range(n)]  # 讀取雪花編號
    last = dict()  # 每一個編號的雪花上次出現的索引值
    imax = 0  # 不同編號雪花數量最大值
    left = 0  # 滑動視窗左端點
    for right, snow in enumerate(snowflake):  # 依序讀取雪花編號
        if snow in last and last[snow] >= left:  # 如果 snow 在 last 之中，而且索引值大於等於左端點
            left = last[snow] + 1  # 更新左端點為目前雪花編號前一次出現的索引值加 1
        last[snow] = right  # 更新目前雪花編號出現的索引值為 right
        imax = max(imax, right - left + 1)  # 更新最大值
    print(imax)

使用時間約為 55 ms，記憶體約為 37.7 MB，通過測試。如果更新 $imax$ 時不呼叫 $max$，速度會更快，使用時間約為 45 ms，記憶體約為 34.9 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])  # n 片雪花
        ptr += 1
        last = dict()  # 每一個編號的雪花上次出現的索引值
        imax = 0  # 不同編號雪花數量最大值
        left = 0  # 滑動視窗左端點
        for right in range(n):  # 依序讀取雪花編號
            snow = data[ptr]
            ptr += 1
            if snow in last and last[snow] >= left:  # 如果 snow 在 last 之中，而且索引值大於等於左端點
                left = last[snow] + 1  # 更新左端點為目前雪花編號前一次出現的索引值加 1
            last[snow] = right  # 更新目前雪花編號出現的索引值為 right
            val = right - left + 1  # 更新最大值
            if val > imax: imax = val
            #imax = max(imax, right - left + 1)  
        result.append(f"{imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d192. 11351 - Last Man Standing

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


ZeroJudge 題目連結：d192. 11351 - Last Man Standing

解題想法

輸入的測資範圍應該是 $0 < n \leq 10^5$ 及 $0 < k < 10^9$，如果模擬整個淘汰的過程會超時。 從最後的贏家逆推𠩤來的編號。

1. 為了方便運算，成員的編號由0開始，最後輸出結果時再加1。
2. 先假設幸運者的編號 $idx_{0} = 0$，最後剩下 1 個人。
3. 第 $n-1$ 次（最後1次）運作時，參與的人數為 $2$，幸運者原來的編號為 $idx_{n-2} = k \% 2$。
4. 第 $n-2$ 次（倒數第2次）運作時，參與的人數為 $3$，幸運者原來的編號為 $idx_{n-3} = (idx_{n-2} + k) \% 3$。
5. 第 $n-3$ 次（倒數第3次）運作時，參與的人數為 $4$，幸運者原來的編號為 $idx_{n-4} = (idx_{n-3} + k) \% 4$。
6. 若 $i = 1、2、\dots、n$，則第 $n-i$ 次（倒數第 $i$ 次）運作時，參與的人數為 $1 + i$，幸運者原來的編號為 $idx_{i} = (idx_{i-1} + k) \% (1+ i)$。
7. 輸出幸運者的編號，由於題目的編號從 $1$ 開始，需要將 $idx$ 加 $1$。

Python 程式碼

模擬過程，超時。

t = int(input())
for i in range(1, t+1):
    n, k = map(int, input().split())
    arr = list(range(1, n+1))  # 目前還存活的人
    idx = 0  # 從 1 號、索引值 0 開始
    while n > 1:  # 人數大於 1 繼續執行
        idx = (idx+k-1) % n  # 更新淘汰者的索引值
        del arr[idx]  # 移除 arr[idx]
        n -= 1  # 人數減 1
        idx %= n  # 更新 idx，有可能歸零
    print(f"Case {i:d}: {arr[0]:d}")  # 印出答案

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

t = int(input())
for i in range(1, t+1):
    n, k = map(int, input().split())
    idx = 0  # 最後剩下的人，索引值 0
    for j in range(1, n):  # 1 到 n-1
        idx = (idx + k) % (1+j)
    print(f"Case {i:d}: {idx+1:d}")  # 印出答案

ZeroJudge 解題筆記：d191. 11352 - Crazy King

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


ZeroJudge 題目連結：d191. 11352 - Crazy King

解題想法

因為我不想要在檢查騎士可以走到的位置時，需要先檢查這一步是不會出界，我會在地圖的周圍加上兩層 $-1$ 當作哨兵，用 $-1$ 標示邊界及不能走到的格子，假設地圖尺寸原為 $m \times n$，如果用 Python 解題會改成尺寸為 $(m+2) \times (n+2)$ 的二維串列，如果用 C++ 解題會改成尺寸為 $(m+4) \times (n+4)$ 的二維陣列。地圖 $grid$ 之中實際上儲存的是步數，用 $0$ 代表起點，$-2$ 代表終點，$-3$ 代表空格及未走過的格子，$-1$ 代表邊界及不能走的格子。讀取地圖資料，依照字元標示 $grid$ 的數字，再檢查騎士的位置，將騎士可以一步走到的格子也標示成 $-1$。最後再用 BFS，找出國王從 $A$ 點走到 $B$ 點的最少步數。BFS 結束之後，如果終點對應的格子仍為 $-2$，代表無法走到終點。

Python 程式碼

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

from collections import deque

t = int(input())
for _ in range(t):
    """ 讀取地圖資料 """
    m, n = map(int, input().split())  # 棋盤 m*n，實際上儲存的是步數
    grid = [[-1]*(n+2) for _ in range(m+2)]  # 最右側、最下方加上兩層 -1 當作哨兵
    knight = []  # 騎士的位置
    sr, sc, er, ec = 0, 0, 0, 0  # 起點、終點
    for r in range(m):  # 讀取 m 行資料
        line = input()
        for c, ch in enumerate(line):  # 依序讀取 line 的字元
            if ch == 'Z': knight.append((r, c))  # 騎士
            elif ch == 'A':  # 起點
                grid[r][c] = 0; sr = r; sc = c;
            elif ch == 'B':  # 終點
                grid[r][c] = -2; er = r; ec = c;
            elif ch == '.':  # 空格
                grid[r][c] = -3
    for r, c in knight:  # 依序讀取騎士所在的位置
        # 依序檢查右上、右、右下、下、左下、左、左上、上
        for dr, dc in ((-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)):
            nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
            if grid[nr][nc] == -3:  # 空格
                grid[nr][nc] = -1  # 設定成 -1，不能走
    """ BFS 找最短路徑 """
    que = deque([(sr, sc)])  # 待走訪佇列
    end = False
    while que and not end:  # 如果 que 還有資料而且還沒有走到終點，繼續執行
        r, c = que.popleft()  # 取出 que 最前面的資料
        # 依序檢查右上、右、右下、下、左下、左、左上、上
        for dr, dc in ((-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0)):
            nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
            if grid[nr][nc] == -3:  # 走到空格
                grid[nr][nc] = grid[r][c] + 1  # 更新步數
                que.append((nr, nc))  # (nr, nc) 加到 que
            elif grid[nr][nc] == -2:  # 走到終點
                grid[nr][nc] = grid[r][c] + 1  # 更新步數
                end = True; break  # 走到終點，中止迴圈
    """ 印出答案 """
    if grid[er][ec] == -2:  # 無法走到終點
        print("King Peter, you can't go now!")
    else:  # 走到終點
        print(f"Minimal possible length of a trip is {grid[er][ec]:d}")

ZeroJudge 解題筆記：d190. 11462 - Age Sort

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


ZeroJudge 題目連結：d190. 11462 - Age Sort

解題想法

這題就是單純的排序，只是改成多組測資，以 0 結尾。如果用 Python 解題，可以先將 $n$ 個數字存入串列 arr，再用 arr.sort() 由小到大排序，最後用 print(*arr) 輸出；也可以用 sorted 將 map 轉換後的結果排序並用 print 輸出。如果想要測試一些特別的寫法，也可以用最小優先佇列解題，依序彈出佇列中的最小值，但其實這樣寫比較慢，對本題而言沒有必要。

Python 程式碼

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

while True:
    n = int(input())
    if n == 0: break
    arr = list(map(int, input().split()))
    arr.sort()
    print(*arr)

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

while True:
    n = int(input())
    if n == 0: break
    print(*sorted(map(int, input().split())))

用 sys.stdin 及 sys.stdout.write 加速，使用時間約為 0.4 s，記憶體約為 304.3 MB，通過測試。

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break
        arr = sorted(map(int, data[ptr:ptr+n]))
        ptr += n
        res = " ".join(map(str, arr))
        result.append(f"{res}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

heapq，反而更慢。使用時間約為 1.1 s，記憶體約為 157.4 MB，通過測試。

import heapq

while True:
    n = int(input())
    if n == 0: break
    pq = [i for i in map(int, input().split())]
    heapq.heapify(pq)
    while len(pq) > 1: print(heapq.heappop(pq), end=" ")
    print(heapq.heappop(pq))

ZeroJudge 解題筆記：d188. 11342 - Three-square

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


ZeroJudge 題目連結：d188. 11342 - Three-square

解題想法

用字典建表，找出 $0$ 到 $50000$ 之間，由 $3$ 個非負完全平方數字相加的字典順序最小組合，最大只要測試到 $i = \sqrt{50000}$ 就好。用 3 層 for 迴圈建表，最外層跑 $i = 0$ 到 $i = \sqrt{50000}$，第 2 層跑 $j = i$ 到 $j = \sqrt{50000}$，第 3 層跑 $k = j$ 到 $k = \sqrt{50000}$，如果加總只要記錄第一次跑出來的 $i, j, k$ 就好。接下來讀取測資，查表，輸出答案。

Python 程式碼

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

def solve():
    import sys

    """ 建表，找出 0 ~ 50000 字典順序最小的組合 """
    max_k = 50000  # 題目的測資最大值
    max_i = int(max_k**0.5) + 1  # 可能的數字
    table = dict()  # 表格
    for i in range(max_i):  # 測試 i = 0 ~ max_i-1
        x = i*i  # 儲存 i 平方的值
        for j in range(i, max_i):  # 測試 j = 0 ~ max_i-1
            y = x + j*j  # 加上 j 平方，不能寫成 x += j*j，變數值會出問題
            if y > max_k: break  # 超過 max_k，中止迴圈
            for k in range(j, max_i):  # 測試 j = 0 ~ max_i-1
                z = y + k*k  # 加上 k 平方，不能寫成 y += k*k，變數值會出問題
                if z > max_k: break  # 超過 max_k，中止迴圈
                if z not in table:  # 如果 z 不在 table 之中
                    table[z] = (i, j, k)  # 設定為 (i, j, k)

    """ 讀取測資，輸出答案 """
    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])  # 要測試的數值 n
        ptr += 1
        if n not in table:  # 如果 n 不在 table 之中，印出 -1
            result.append("-1\n")
        else: # 反之，印出 table[n] 的值
            res = " ".join(map(str, table[n])) + "\n"
            result.append(res)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d187. 11530 - SMS Typing

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


ZeroJudge 題目連結：d187. 11530 - SMS Typing

解題想法

這題可以用字典建表，先記錄每個字元對應的次數，讀取測資後再依序取出字元，計算次數加總。

Python 程式碼

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

table = {'a': 1, 'b': 2, 'c': 3,
         'd': 1, 'e': 2, 'f': 3,
         'g': 1, 'h': 2, 'i': 3,
         'j': 1, 'k': 2, 'l': 3,
         'm': 1, 'n': 2, 'o': 3,
         'p': 1, 'q': 2, 'r': 3, 's': 4,
         't': 1, 'u': 2, 'v': 3,
         'w': 1, 'x': 2, 'y': 3, 'z': 4,
         ' ': 1}

n = int(input())
for i in range(1, n+1):
    s = input()
    cnt = sum(table[c] for c in s)
    print(f"Case #{i:d}: {cnt:d}")

ZeroJudge 解題筆記：d186. 11461 - Square Numbers

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


ZeroJudge 題目連結：d186. 11461 - Square Numbers

解題想法

先將 $a$ 開根號並向上取整，計算範圍內平方數開根根號的最小值 $low$，再對 $b$ 開根號並向下取整，計算範圍內平方數開根根號的最大值 $high$，答案就是 $high - low + 1$。

Python 程式碼

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

def solve():
    import sys, math
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        a, b = map(int, data[ptr:ptr+2])
        ptr += 2
        if a == 0 and b == 0: break
        low = math.ceil(math.sqrt(a))
        high = math.floor(math.sqrt(b))
        result.append(f"{high - low + 1:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d183. 00725 - Division

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


ZeroJudge 題目連結：d183. 00725 - Division

解題想法

題目要求將 $0$ 到 $9$ 分配成兩個 $5$ 位數 $a, b$，而且開頭可以為 $0$，代表可能的數字下限為 $1234$、上限為 $98765$，而且 $a$ 可以整除 $b$，商為 $2$ 到 $79$，所以 $a$ 的範圍大約是 $1234$ 到 $49876$， $b$ 的範圍大約是 $49876$ 到 $98765$。另外再寫兩個自訂函式，檢查兩個數是否有重覆的數字。建表，計算商為 $2$ 到 $79$ 可能的除數、被除數組合，再查表找答案。 用 Python 的 itertools.permutations 也可以窮舉所有數字的組合，但這樣會多跑很多不可能的數字，速度會比較慢。

Python 程式碼

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

import sys

def check_self(s):
    """ 代入字串，檢查是否有重複的數字 """
    used = set()  # 已經出現的數字
    for c in s:  # 依序讀取字元 c
        if c in used:  # 如果 c 已經出現過
            return False  # 回傳 False
        used.add(c)  # c 加入 used
    return True  # 如果可以跑到這行，回傳 True

def check_other(s, t):
    """ 代入字串 s, t，檢查是否有重複的數字 """
    used = set(list(s))  # s 已經檢查過，直接轉成 set
    for c in t:  # 依序讀取字元 c
        if c in used:  # 如果 c 已經出現過
            return False  # 回傳 False
        used.add(c)  # c 加入 used
    return True  # 如果可以跑到這行，回傳 True

""" 建表 """
low, mid, high = 1234, 49876, 98765  # 除數下限、上限，被除數上限
table = [[] for _ in range(80)]  # 表格，各種商的組合
for a in range(low, mid+1):  # 依序測試可能的除數 a
    n = str(a).zfill(5)  # 轉成字串，前面補 0 至 5 位數
    if not check_self(n): continue  # 如果 n 有重複的數字，找下一個
    for i in range(2, 80):  # 依序測試可能的倍數 i
        b = a*i  # 被除數 b
        if b >= high: break  # 如果 b 超過上限，不可能再有解，中止迴圈
        m = str(b).zfill(5)  # 轉成字串，前面補 0 至 5 位數
        if check_self(m) and check_other(n, m):  # 如果 m 本身、m 與 n 沒有重複的數字
            table[i].append((m, n))  # (m, n) 加到 table[i]

""" 讀取測資，組合答案 """
result = []
for line in sys.stdin:
    N = int(line)
    if N == 0: break
    if result: result.append("\n")  # 如果 result 已經有內容，先換行
    if not table[N]:  # 如果 table[N] 是空的，無解
        result.append(f"There are no solutions for {N:d}.\n")
    else:  # 反之，依序讀取 table[N] 的內容組成答案
        for t in table[N]:
            result.append(f"{t[0]} / {t[1]} = {N:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d182. 00256 - Quirksome Squares

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


ZeroJudge 題目連結：d182. 00256 - Quirksome Squares

解題想法

假設位數為 $n$，題目要找的答案只有可能是 $i = 0, 1, 2, \dots, 98, 10^{n/2} - 1$ 的平方，將 $i^2$ 的左、右兩半加起來，再檢查組合後的數平方是否等於 $i^2$，就可以找到答案。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        m = 10**(n//2)  # 上限，10 的 n/2 次方
        for i in range(m):
            square = i*i  # 平方
            num = square//m + square%m  # 左、右兩半相加
            if num**2 == square:  # 符合條件
                ans = str(square).zfill(n)  # 前方補 0 至 n 位數
                result.append(f"{ans}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()