ZeroJudge 解題筆記：d111. 10110 - Light, more light

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


ZeroJudge 題目連結：d111. 10110 - Light, more light

解題想法

這題考數學。第 $1$ 趟及第 $n$ 趟都會改變第 $n$ 盞燈的開關，效果抵消。只要找第 $2$ 趟到第 $(n-1)$ 趟之間改變第 $n$ 盞燈的開關次數 $cnt$，也就是找因數的數量，如果 $cnt$ 是奇數輸出 $yes$，反之輸出 $no$。可以用 for 迴圈找 $i = 2$ 到 $i = \sqrt{n}$ 之間有幾個 $n$ 的因數，如果 $i^2 \neq n$ 增加 $2$ 個因數，如果 $i^2 = n$ 增加 $1$ 個因數。所以這題可以直接用 $n$ 是否為完全平方數找答案。

Python 程式碼

找 $n$ 的因數數量，使用時間約為 14 ms，記憶體約為 8.1 MB，通過測試。

import sys

result = []
for line in sys.stdin:
    n = int(line)
    if n == 0: break
    factors = {1, n}
    for i in range(2, int(n**0.5)+1):
        if n%i == 0:
            factors.add(i)
            factors.add(n//i)
    result.append("yes\n" if len(factors)%2 == 1 else "no\n")
sys.stdout.write("".join(result))

檢查 $n$ 是否為完全平方數，使用時間約為 7 ms，記憶體約為 8.2 MB，通過測試。

import sys

result = []
for line in sys.stdin:
    n = int(line)
    if n == 0: break
    r = int(n**0.5)
    result.append("yes\n" if r*r == n else "no\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d096. 00913 - Joana and the Odd Numbers

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


ZeroJudge 題目連結：d096. 00913 - Joana and the Odd Numbers

解題想法

這題考數學。假設最後一項有 $n$ 項，則題目問的是第 $i$ 列（$i = \frac{n+1}{2}$），此列最後一項 $$ a = \frac{[1 + 1 + 2 \times(i-1)] \times i}{2} $$ 最後 $3$ 項相加為 $(2a -1) \times 3 - 6$。 這題的測資 $n$ 有點大，用 C++ 解題時用 int 會溢位。

Python 程式碼

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

import sys

result = []
for line in sys.stdin:
    n = int(line)  # 最後一列有 n 項
    i = (n+1) // 2  # 第 i 列
    a = (1 + 1 + 2*(i-1)) * i // 2  # 第 i 列的最後 1 項
    result.append(f"{(a*2 - 1)*3 - 6:d}\n")  # 第 i 列最後 3 項相加
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d095. 00579 - ClockHands

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


ZeroJudge 題目連結：d095. 00579 - ClockHands

解題想法

先計算時針與12點的夾角，由於時針每12小時轉360度，1小時轉30度，1分鐘轉0.5度，計算角度前先將小時 h 對 12 取餘數。再計算分針與12點的夾角，分針每60分鐘轉360時，1分鐘轉6度。再將兩個角度相減、取絕對值，如果絕對值大於180度，再將答案改成360度減掉絕對值。

Python 程式碼

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

import sys

result = []
for line in sys.stdin:
    if line.strip() == "0:00": break
    h, m = map(int, line.split(":"))
    a = h%12*30 + m/2
    b = m*6
    c = abs(a-b)
    if c > 180: c = 360 - c
    result.append(f"{c:.3f}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d094. 00478 - Points in Figures: Rectangles and Circles, and Triangles

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


ZeroJudge 題目連結：d094. 00478 - Points in Figures: Rectangles and Circles, and Triangles

解題想法

這題是 d093. 00477 - Points in Figures: Rectangles and Circles 的加強版，除了長方形、圓形之外還多了三角形，可以用上一題的程式碼為基礎，再加上檢查點是否在三角形內的自訂函式。 假設平面上的三角形 ABC 頂點座標分別為 $(x_A, y_A), (x_B, y_B), (x_C, y_C)$，如果要判斷平面上的點 P $(x_P, y_P)$ 是否在三角形之中，P 點座標可以表示為 $$ P = uA + vB + wC $$ 解聯立後可得 $$ \begin{align*} u &= \frac{(x_B - x_A)(y_P - y_A) - (y_B - y_A)(x_P - x_A)}{(x_B - x_A)(y_C - y_A) - (y_B - y_A)(x_C - x_A)}\\ v &= \frac{(x_C - x_A)(y_P - y_A) - (y_C - y_A)(x_P - x_A)}{(x_C - x_A)(y_B - y_A) - (y_C - y_A)(x_B - x_A)} \\ w &= 1 - u - v & \end{align*} $$ 係數符合的條件為

• $0 \leq u \leq 1$
• $0 \leq v \leq 1$
• $0 \leq w \leq 1$

Python 程式碼

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

import sys

def in_rectangle(x, y, x1, y1, x2, y2):
    """
    代入要測試的點座標 (x, y)
    長方形左上頂點座標 (x1, y1)
    長方形右下頂點座標 (x2, y2)
    判斷點是否在長方形內
    """
    if x1 < x < x2 and y1 > y > y2: return True
    return False

def in_circle(x, y, xc, yc, r):
    """
    代入要測試的點座標 (x, y)
    圓心座標 (xc, yc)、半徑 r
    判斷點是否在圓形內
    """
    if (x-xc)**2 + (y-yc)**2 < r**2: return True
    return False

def in_triangle(x, y, xA, yA, xB, yB, xC, yC):
    """
    代入要測試的點座標 (x, y)
    三角形頂點座標 (xA, yA), (xB, yB), (xC, yC)
    判斷點是否在三角形內
    """
    u = ((xB - xA)*(y - yA) - (yB - yA)*(x - xA)) / ((xB - xA)*(yC - yA) - (yB - yA)*(xC - xA))
    v = ((xC - xA)*(y - yA) - (yC - yA)*(x - xA)) / ((xC - xA)*(yB - yA) - (yC - yA)*(xB - xA))
    w = 1 - u - v
    if 0 <= u <= 1 and 0 <= v <= 1 and 0 <= w <= 1: return True
    return False

""" 讀取形狀 """
figures = [[]]
for line in sys.stdin:
    if line.strip() == "*": break
    data = line.split()
    if data[0] == "r":
        figures.append([0] + list(map(float, data[1:])))
    elif data[0] == "c":
        figures.append([1] + list(map(float, data[1:])))
    else:
        figures.append([2] + list(map(float, data[1:])))

""" 判斷點是否在圖形內並組合答案 """
result = []
i = 0
n = len(figures)
for line in sys.stdin:
    if line.strip() == "9999.9 9999.9": break
    i += 1
    state = False
    x, y = map(float, line.split())
    for j in range(1, n):
        if figures[j][0] == 0:
            if in_rectangle(x, y, figures[j][1], figures[j][2], figures[j][3], figures[j][4]):
                result.append(f"Point {i:d} is contained in figure {j:d}\n")
                state = True
        elif figures[j][0] == 1:
            if in_circle(x, y, figures[j][1], figures[j][2], figures[j][3]):
                result.append(f"Point {i:d} is contained in figure {j:d}\n")
                state = True
        else:
            if in_triangle(x, y, figures[j][1], figures[j][2], figures[j][3], figures[j][4], figures[j][5], figures[j][6]):
                result.append(f"Point {i:d} is contained in figure {j:d}\n")
                state = True
    if not state:
        result.append(f"Point {i:d} is not contained in any figure\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d093. 00477 - Points in Figures: Rectangles and Circles

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


ZeroJudge 題目連結：d093. 00477 - Points in Figures: Rectangles and Circles

解題想法

另外寫兩個自訂函式 in_rectangle 及 in_circle，分別用來檢查指定的座標是否在長方形或圓形之中。先儲存所有形狀的資料，讀取到檢查的點之後，依序檢查這個點在哪些編號的圖形之中並輸出答案。

Python 程式碼

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

import sys

def in_rectangle(x, y, x1, y1, x2, y2):
    """
    代入要測試的點座標 (x, y)
    長方形左上頂點座標 (x1, y1)
    長方形右下頂點座標 (x2, y2)
    判斷點是否在長方形內
    """
    if x1 < x < x2 and y1 > y > y2: return True
    return False

def in_circle(x, y, xc, yc, r):
    """
    代入要測試的點座標 (x, y)
    圓心座標 (xc, yc)、半徑 r
    判斷點是否在圓形內
    """
    if (x-xc)**2 + (y-yc)**2 < r**2: return True
    return False

""" 讀取形狀 """
figures = [[]]
for line in sys.stdin:
    if line.strip() == "*": break
    data = line.split()
    if data[0] == "r":
        figures.append([0] + list(map(float, data[1:])))
    elif data[0] == "c":
        figures.append([1] + list(map(float, data[1:])))

""" 判斷點是否在圖形內並組合答案 """
result = []
i = 0
n = len(figures)
for line in sys.stdin:
    if line.strip() == "9999.9 9999.9": break
    i += 1
    state = False
    x, y = map(float, line.split())
    for j in range(1, n):
        if figures[j][0] == 0:
            if in_rectangle(x, y, figures[j][1], figures[j][2], figures[j][3], figures[j][4]):
                result.append(f"Point {i:d} is contained in figure {j:d}\n")
                state = True
        elif figures[j][0] == 1:
            if in_circle(x, y, figures[j][1], figures[j][2], figures[j][3]):
                result.append(f"Point {i:d} is contained in figure {j:d}\n")
                state = True
    if not state:
        result.append(f"Point {i:d} is not contained in any figure\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：k652. 二元搜尋樹復原 (BST)

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


ZeroJudge 題目連結：k652. 二元搜尋樹復原 (BST)
原題連結

解題想法

自訂類別 Node 及 BST，在 BST 之中用遞迴從根節點開始往下找插入新節點的位置，題目的輸出方式是中序走訪，但是同時要印出父節點的值。詳細的說明已經寫在程式碼的註解之中。

Python 程式碼

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

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val, node = None):
        # 如果 node 為 None，設為 self.root，如果 self.root 是空的，新增 self.root
        if node is None:
            node = self.root
            if self.root is None:
                self.root = Node(val)
                return
        # 如果 val 較小，放到 node.left，如果 node.left 是空的，新增 node.left
        # 如果已經有 node.left，遞迴，試著放到 node.left 之下
        if val < node.val:
            if not node.left:
                node.left = Node(val)
            else:
                self.insert(val, node.left)
        # 如果 val 較大，放到 node.right，如果 node.right 是空的，新增 node.right
        # 如果已經有 node.right，遞迴，試著放到 node.right 之下
        else:
            if not node.right:
                node.right = Node(val)
            else:
                self.insert(val, node.right)

    def inorder(self, node = None, parent = -1):
        # 中序走訪，順序為 left, root, right
        # 如果 node 為 None，設為 self.root
        if node is None:
            node = self.root
        # 如果有 node.left，遞迴，代入 node.left 及 node.val
        if node.left:
            self.inorder(node.left, node.val)
        # 印出 node.val 及父節點的值；如果是根節點，parent 的值為 -1
        print(node.val, parent)
        # 如果有 node.right，遞迴，代入 node.right 及 node.val
        if node.right:
            self.inorder(node.right, node.val)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        # 測資給的順序是後序走訪，最後一個是根節點，倒序加入 bst 之中
        arr = list(map(int, data[ptr:ptr+n]))
        ptr += n
        bst = BST()
        for u in arr[::-1]:
            bst.insert(u)
        bst.inorder()

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d088. 00127 - "Accordian" Patience

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


ZeroJudge 題目連結：d088. 00127 - "Accordian" Patience

解題想法

這題的測資格式比較特別，如果用 Python 解題，最好用 sys.stdin.read().split() 一次讀取所有的測資，再用索引值分割，這樣會比較方便。儲存所有牌堆資料時，用可以改變長度、刪除資料的 list 及 vector 比較方便。用 while 迴圈檢查是否有可以合併的牌堆，直到沒有可以合併的牌堆為止。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 停止條件
        if data[ptr] == "#": break
        # 讀取兩行測資組成牌堆
        piles = [[card] for card in data[ptr:ptr+52]]
        ptr += 52
        # 移動過程
        changed = True  # 是否有交換牌
        while changed:  # 如果有交換繼續執行
            changed = False  # 先設定為 False
            i = 1  # 從牌堆 1 開始檢查
            while i < len(piles):  # 如果 i 還沒有出界繼續執行
                # 先檢查牌堆 i 與 i-3 最上面的牌是否同花色或同數字
                if i >= 3 and (piles[i][-1][0] == piles[i-3][-1][0] or \
                               piles[i][-1][1] == piles[i-3][-1][1]):
                    piles[i-3].append(piles[i].pop())  # 牌堆 i 最上面移到牌堆 i-3
                    if not piles[i]: del piles[i]  # 如果牌堆 i 是空的，刪除
                    changed = True  # 有交換牌
                    break  # 中止迴圈
                # 檢查牌堆 i 與 i-1 最上面的牌是否同花色或同數字
                elif i >= 1 and (piles[i][-1][0] == piles[i-1][-1][0] or \
                                 piles[i][-1][1] == piles[i-1][-1][1]):
                    piles[i-1].append(piles[i].pop())  # 牌堆 i 最上面移到牌堆 i-1
                    if not piles[i]: del piles[i]  # 如果牌堆 i 是空的，刪除
                    changed = True  # 有交換牌
                    break  # 中止迴圈
                # 牌堆 i 不能交換，檢查下一張
                i += 1
        # 組合答案
        n = len(piles)  # 牌堆數量
        nums = [len(pile) for pile in piles]  # 各牌堆張數
        if n == 1:  # 只有一堆
            result.append(f"1 pile remaining: {nums[0]:d}\n")
        else:  # 不只一堆
            result.append(f"{n:d} piles remaining: " + " ".join(map(str, nums)) + "\n")
    # 輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d087. 00107 - The Cat in the Hat

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


ZeroJudge 題目連結：d087. 00107 - The Cat in the Hat

解題想法

寫一個自訂函式 check，輸入起始高度 h、倍率 n，計算總數、高度為 1 的數量、總高度。用 for 迴圈依序測試倍率 1 ~ H-1，用 check 檢查代入的倍率高度為1的貓的數目是否符合測資。

Python 程式碼

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

import sys

def check(h, n):  # 輸入起始高度、倍率
    total, curr, hsum = 1, 1, h  # 總數，目前的數量，總高度
    h //= 1+n  # 新的高度
    while h >= 1:  # 如果 h 大於等於 1 繼續執行
        curr *= n  # 更新數量為 n 倍
        total += curr  # 更新總數
        hsum += curr*h  # 更新總高度
        h //= 1+n  # 更新高度
    return total, curr, hsum  # 回傳總數、高度為 1 的數量、總高度
    
result = []
lines = sys.stdin.readlines()
for line in lines:
    H, M = map(int, line.split())  # 起始高度、高度為 1 的數量
    if H == 0 and M == 0: break  # 如果 H 與 M 皆等於 0，中止迴圈
    total, imin, hsum = H, 1, H  # 試算結果，總數、高度為 1 的數量、總高度
    for i in range(1, H):  # 測試倍率 1 ~ H-1
        total, imin, hsum = check(H, i)  # 回傳測試結果
        if imin == M: break  # 如果 imin 等於 M，找到答案，中止迴圈
    result.append(f"{total-imin:d} {hsum:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d057. 11494 - Queen

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


ZeroJudge 題目連結：d057. 11494 - Queen

解題想法

可能的步數有 3 種：

1. 不需要移動，回傳 0。
2. 在同一列、同一欄、斜直線上，回傳 1。
3. 其它狀況，走 2 步一定會走到，回傳 2。

Python 程式碼

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

import sys

def find_step(x1, y1, x2, y2):  # 輸入起點、終點找步數
    if x1 == x2 and y1 == y2: return 0  # 不需要移動，回傳 0
    if x1 == x2 or y1 == y2: return 1  # 在同一欄或列，回傳 1
    if x2 - x1 == y2 - y1:  # 右上、左下斜直線
        dx = x2 - x1  # x 方向位移
        dy = y2 - y1  # y 方向位移
        if 1 <= x1 + dy <= 8 and 1 <= y1 + dx <= 8:  # 沒出界
            return 1  # 回傳 1
    if x2 - x1 == y1 - y2:  # 左上、右下斜直線
        dx = x2 - x1  # x 方向位移
        dy = y2 - y1  # y 方向位移
        if 1 <= x1 - dy <= 8 and 1 <= y1 - dx <= 8:  # 沒出界
            return 1  # 回傳 1
    # 其它狀況，最多只要水平、垂直各走一步，回傳 2
    return 2

result = []
lines = sys.stdin.readlines()
for line in lines:
    if line.strip() == "0 0 0 0": break
    step = find_step(*map(int, line.split()))
    result.append(f"{step:d}\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d056. 10013 - Super long sums

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


ZeroJudge 題目連結：d056. 10013 - Super long sums

解題想法

這題如果用 Python 解題，最好用串列 a、b 儲存超長整數，再用另一個串列 ans 儲存計算結，串列資料格式為字串。運算時由 a、b 最後面住前讀取資料，將計算結果用字串格式存入 ans，輸出答案時將 ans 反序輸出。如果用 C++ 解題，可以用字串或 vector 儲存超長整數，用字串格式好像速度快一點。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        for _ in range(n):
            m = int(data[ptr])
            ptr += 1
            a, b = [], []
            for _ in range(m):
                c, d = map(int, data[ptr:ptr+2])
                ptr += 2
                a.append(c)
                b.append(d)
            ans = []
            carry = 0
            for i, j in zip(a[::-1], b[::-1]):
                k = int(i) + int(j) + carry
                if k >= 10:
                    carry = 1
                    ans.append(f"{k%10}")
                else:
                    carry = 0
                    ans.append(f"{k}")
            if carry == 1: ans.append("1")
            res = "".join(ans[::-1])
            if not result: result.append(f"{res}\n")
            else: result.append(f"\n{res}\n")
        sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()