一個地球人在臺北

2026年4月25日星期六

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()

2026年4月24日星期五

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))

2026年4月23日星期四

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()

2026年4月22日星期三

ZeroJudge 解題筆記：d174. 10297 - Beavergnaw

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

ZeroJudge 題目連結：d174. 10297 - Beavergnaw

解題想法

先看最右上角剩下部分的截面，相當於是一個底、高皆為 $\frac{D-d}{2}$ 的等腰直角三角形，因此上、下兩塊截面為梯形的部分，是兩個圓錐相減，兩者的底分別為 $\frac{D}{2}$ 及 $\frac{d}{2}$，圓錐相減後的體積為 $$ \frac{1}{3} \pi \cdot \left( \frac{D}{2} \right)^2 \cdot \frac{D}{2} - \frac{1}{3} \pi \cdot \left( \frac{d}{2} \right)^2 \cdot \frac{d}{2} = \frac{\pi}{24} (D^3 - d^3) $$ 中間直徑為 $d$ 的圓柱體積為 $$ \pi \cdot \left( \frac{d}{2} \right)^2 \cdot d = \frac{\pi}{4} d^3 $$ 直徑為 $D$ 的圓柱體積為 $$ \pi \cdot \left( \frac{D}{2} \right)^2 \cdot D = \frac{\pi}{4} D^3 $$ 切掉的體積為 $$ V = \frac{\pi}{4} D^3 - \frac{\pi}{4} d^3 - 2 \times \frac{\pi}{24} (D^3 - d^3) = \frac{\pi}{6} (D^3 - d^3) ~\Rightarrow~ d = \left( D^3 - \frac{6V}{\pi} \right)^{\frac{1}{3}} $$

Python 程式碼

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

def solve():
    import sys, math
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        D = int(data[ptr])
        V = int(data[ptr+1])
        ptr += 2
        if D == 0 and V == 0: break
        d = (D**3 - 6*V/math.pi)**(1/3)
        result.append(f"{d:.3f}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

2026年4月21日星期二

ZeroJudge 解題筆記：d150. 11369 - Shopaholic

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

ZeroJudge 題目連結：d150. 11369 - Shopaholic

解題想法

先將價格由大到小排序存入串列 $prices$，每次取 $3$ 項，將第 $3$ 項加入答案 $ans$。也可以用最大優先佇列，將價格全部存入最大優先佇列 $pq$，每次從 $pq$ 彈出目前的最高價格，每彈出 $3$ 個值就將第 $3$ 個值加入答案 $ans$。因為這題不需要一直將值推入 $pq$ 之中，可以用排序就好，速度比較快。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        t = int(data[ptr])
        ptr += 1
        for _ in range(t):
            n = int(data[ptr])
            ptr += 1
            prices = sorted(map(int, data[ptr:ptr+n]), reverse=True)
            ptr += n
            ans = sum(p for p in prices[2::3])
            result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

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

def solve():
    import sys, heapq

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        t = int(data[ptr])
        ptr += 1
        for _ in range(t):
            n = int(data[ptr])
            ptr += 1
            pq = []
            for __ in range(n):
                p = int(data[ptr])
                ptr += 1
                heapq.heappush(pq, -p)
            ans, cnt = 0, 0
            while pq:
                p = -heapq.heappop(pq)
                cnt += 1
                if cnt == 3:
                    ans += p
                    cnt = 0
            result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

2026年4月20日星期一

ZeroJudge 解題筆記：d133. 00357 - Let Me Count The Ways

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

ZeroJudge 題目連結：d133. 00357 - Let Me Count The Ways

解題想法

因為每種面額的硬幣數量不限，可以取任意數量組成目標金額，是無限背包問題，用動態規畫解題。假設 $dp[i]$ 代表總金額為 $i$ 的組合方式，初始值為 $dp[0] = 1$，總金額 $0$ 只有 $1$ 種組合方式。用一層 for 迴圈依序取出各種面額 $coin$，再用一層 for 迴圈，依序更新 $i = coin$ 到 $i = 30000$ 的方法數，狀態轉移方式為 $dp[i] += dp[i-coin]$。建完 $i = 0$ 到 $i = 30000$ 的方法數表格之後，依序讀取測資、查表、輸出對應的答案。由於這題的方法數有點多，如果用 C 或 C++ 解題，$dp$ 表格要用 long，如果用 int 會溢位。

Python 程式碼

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

def solve():
    import sys

    maxn = 30000
    dp = [0]*(maxn + 1)
    dp[0] = 1
    for coin in (1, 5, 10, 25, 50):
        for i in range(coin, maxn+1):
            dp[i] += dp[i - coin]

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        m = dp[n]
        if m == 1:
            result.append(f"There is only 1 way to produce {n:d} cents change.\n")
        else:
            result.append(f"There are {m:d} ways to produce {n:d} cents change.\n")

    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

2026年4月19日星期日

ZeroJudge 解題筆記：d132. 00340 - Master-Mind Hints

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

ZeroJudge 題目連結：d132. 00340 - Master-Mind Hints

解題想法

先讀取答案 $ans$，計算 $0$ 到 $9$ 的數量存入串列 $cntAns$。接下來讀取猜測的數字 $guess$，如果數字都是 $0$ 就中止迴圈；將 $cntAns$ 複製一份到串列 $cnt$，依序檢查 $ans, guess$ 的每個位數，找出位置、數字皆相等的數字並更新 $A$ 的值，如果數字對但位置錯則存入串列 $remain$，最後再從 $remain$ 的資料計算 $B$ 的值。

Python 程式碼

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

import sys

num = 0  # 計算第幾次遊戲用的計數器
for line in sys.stdin:  # 繼續執行直到沒有讀到字串為止
    if line == "0\n": break  # 如果讀到 0\n 結束 for 迴圈
    n = int(line.strip())  # 讀取答案的位數
    num += 1  # num 加 1
    print(f"Game {num:d}:")  # 印出遊戲次數
    ans = list(map(int, input().split()))  # 讀取答案
    cntAns = [0]*10  # 因為題目限制只有 1 ~ 9 的數字，用長度為 10 的串列計數即可
    for a in ans: cntAns[a] += 1  # 在外面跑一次就好
    for line2 in sys.stdin:  # 繼續讀取字串
        guess = list(map(int, line2.split()))  # 讀取猜測的數字
        if all(g == 0 for g in guess): break  # 如果猜的數字都是 0，結束這次的遊戲
        cnt = cntAns.copy()  # 等一下會被修改掉，複製一份到 cnt
        remain = []  # 用來記錄沒有對到正確位置的數字
        A, B = 0, 0  # 值及位置都正確數字數量，只有值正確但位置錯的數字數量
        for a, g in zip(ans, guess):  # 依序由 ans 及 guess 讀取資料 a, g
            if a == g:  # 如果 a 等於 g，值及位置都正確
                A += 1  # A 加 1
                cnt[a] -= 1  # a 對應的數量減 1
            elif cnt[g] > 0: remain.append(g)  # 如果值對但位置錯，將 g 加入 remain
        for r in remain:  # 依序由 remain 讀取資料 r
            if cnt[r] > 0:  # 如果 r 在 cnt 之中的數量大於 0 
                cnt[r] -= 1  # r 在 cnt 之中的數量減 1
                B += 1  # B 加 1
        print(f"    ({A:d},{B:d})")  # 印出答案

2026年4月18日星期六

ZeroJudge 解題筆記：d130. 00138 - Street Numbers

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

ZeroJudge 題目連結：d130. 00138 - Street Numbers

解題想法

這題的答案固定為

         6         8
        35        49
       204       288
      1189      1681
      6930      9800
     40391     57121
    235416    332928
   1372105   1940449
   7997214  11309768
  46611179  65918161

左側包含起點的和 $$ lsum = \frac{(1+k) \times k}{2} $$ 右側包含起點的和 $$ rsum = \frac{(k+n) \times (n-k+1)}{2} $$ 如果 $lsum = rsum$，則 $$ \begin{align*} & k(1+k) = (k+n)(n-k+1) \\ ~\Rightarrow~& k + k^2 = nk - k^2 + k + n^2 - nk + n \\ ~\Rightarrow~& n^2 + n - 2k^2 = 0 \\ ~\Rightarrow~& n = \frac{-1 \pm \sqrt{1 + 8k^2}}{2} \end{align*} $$ 因為 $n, k \in N$ 且 $n>k$，上式的答案只能取加號；$1 + 8k^2$ 是完全平方數，開根號減 1 之後是偶數。

Python 程式碼

這題我沒有寫出正常作法而且可以 AC 的 Python 程式碼，只有直接輸出答案的作弊版，使用時間約為 8 ms，記憶體約為 8.8 MB，通過測試。

import sys

result = ["         6         8\n",
          "        35        49\n",
          "       204       288\n",
          "      1189      1681\n",
          "      6930      9800\n",
          "     40391     57121\n",
          "    235416    332928\n",
          "   1372105   1940449\n",
          "   7997214  11309768\n",
          "  46611179  65918161\n"]
sys.stdout.write("".join(result))

2026年4月17日星期五

ZeroJudge 解題筆記：d131. 00160 - Factors and Factorials

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

ZeroJudge 題目連結：d131. 00160 - Factors and Factorials

解題想法

題目要計算 $1!$ 到 $100!$ 每個數字之中，所有相乘的質數次方。可以先建 $1$ 到 $100$ 之間的質數表 $primes$。接下來用一個長度為 $101$ 的串列 $dp$，儲存 $1!$ 到 $100!$ 對應的答案，用字典格式儲存，key 為質數，value 為次方。由於 $i! = i \times (i-1)!$ ，更新 $dp[i]$ 時先複製 $dp[i-1]$ 的資料，再加上 $i$ 的質因數分解結果。最後再依序讀取測資，從 $dp$ 之中找對應的答案，排列成題目要求的格式並輸出。

Python 程式碼

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

def solve():
    import sys
    
    """ 1 ~ 100 之間的質數 """
    maxn = 100
    sieve = [True]*(maxn+1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(maxn**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, maxn+1, i):
                sieve[j] = False
    primes = [i for i in range(101) if sieve[i]]
    
    """ 建表，dp 的內容是 0 ~ 100 每個質因數對應的次方，字典格式 """
    dp = [{p:0 for p in primes} for _ in range(maxn+1)]
    for i in range(2, maxn+1):  # 依序測試 2 ~ 100
        dp[i] = dp[i-1].copy()  # 複製前一組的資料
        x = i  # 暫存 i 的值
        for p in primes:  # 依序讀取質數
            y = 0  # 要增加的次方
            while x%p == 0:  # 如果 p 可以整除 x
                y += 1  # y 加 1
                x //= p  # x 除以 p
            if y > 0:  # 如果 y 大於 0
                dp[i][p] += y  # 更新 dp[i][p] 對應的次方
            if x == 1: break  # 如果 x 等於 1，不需要再測試

    """ 讀取資料，從 dp 讀取質因數的次方，組合成答案 """
    result= []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break
        cofs = list(dp[n].values())  # 取出各個質因數的次方組成 list
        while cofs[-1] == 0: cofs.pop()  # 移除最後面的 0
        res = f"{n:3d}! ="  # 答案的開頭
        for i, cof in enumerate(cofs, start=1):  # 依序讀取 cofs
            res += f"{cof:3d}"  # 每個次方佔 3 格
            if i%15 == 0 and i < len(cofs): res += "\n      "  # 每 15 個要換行並空 6 格，如果是最後一項不換行
        res += "\n"  # 最後再換行
        result.append(res)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

2026年4月16日星期四

ZeroJudge 解題筆記：d129. 00136 - Ugly Numbers

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

ZeroJudge 題目連結：d129. 00136 - Ugly Numbers

解題想法

將找到的 ugly number 存入串列 $ugly$ 之中，再用 3 個變數 $i, j, k$ 分別儲存目前串列之中最後一個 $2, 3, 5$ 的倍數索引值。用 while 迴圈，執行到串列的長度等於 1500 為止，裡面再用 3 個 while 迴圈，更新 $i, j, k$ 的值，更新完之後再取 $ugly[i]*2, ugly[j]*3, ugly[k]*5$ 的最小值，就是新的 ugly number。

Python 程式碼

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

ugly = [1]
i, j, k = 0, 0, 0  # 2, 3, 5 的倍數在 ugly 之中的索引值
while len(ugly) < 1500:
    # 更新 i, j, k，直到對應的數位分別乘以 2, 3, 5 大於 ugly 最後一項為止
    while ugly[i]*2 <= ugly[-1]: i += 1
    while ugly[j]*3 <= ugly[-1]: j += 1
    while ugly[k]*5 <= ugly[-1]: k += 1
    ugly.append(min(ugly[i]*2, ugly[j]*3, ugly[k]*5))  # 取最小一項加到 ugly
print(f"The 1500'th ugly number is {ugly[-1]:d}.")

訂閱：意見 (Atom)

熱門文章

2026年4月25日 星期六

解題想法

Python 程式碼

2026年4月24日 星期五

解題想法

Python 程式碼

2026年4月23日 星期四

解題想法

Python 程式碼

2026年4月22日 星期三

解題想法

Python 程式碼

2026年4月21日 星期二

解題想法

Python 程式碼

2026年4月20日 星期一

解題想法

Python 程式碼

2026年4月19日 星期日

解題想法

Python 程式碼

2026年4月18日 星期六

解題想法

Python 程式碼

2026年4月17日 星期五

解題想法

Python 程式碼

2026年4月16日 星期四

解題想法

Python 程式碼

2026年4月25日星期六

2026年4月24日星期五

2026年4月23日星期四

2026年4月22日星期三

2026年4月21日星期二

2026年4月20日星期一

2026年4月19日星期日

2026年4月18日星期六

2026年4月17日星期五

2026年4月16日星期四