一個地球人在臺北

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}.")

2026年4月15日星期三

ZeroJudge 解題筆記：d121. 00583 - Prime Factors

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

ZeroJudge 題目連結：d121. 00583 - Prime Factors

解題想法

因為 $n$ 的上限為 $2^{31}$，質因數的上限為 $\sqrt{2^{31}} \approx 46340$，可以先建 $1$ 到 $46340$ 的質數表，然後再用試除法找質因數。不過這題最麻煩的地方，反而是在於要拼出正確的輸出格式。

Python 程式碼

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

def solve():
    import sys
    
    # 建質數表，1 ~ sqrt(2^31)，大約 46340
    maxn = 46340
    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(maxn + 1) if sieve[i]]
    
    # 主要的解題過程
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break  # 停止運作的條件
        if n == 1:  # 特例
            result.append("1 = 1\n")
            continue
        factors = []  # 質因數
        m = n  # n 的質先存到 m
        if m < 0:  # 負數
            factors.append(-1)  # 先加入 -1
            m = -m  # 轉為正值
        # 找質因數，m 的值先存到 x
        x = m
        for p in primes:
            if p*p > x:  # 沒有更大的質因數，中止迴圈
                break
            while x%p == 0:
                factors.append(p)
                x //= p
        if x > 1: factors.append(x)
        # 組合答案
        res = " x ".join(map(str, factors))
        result.append(f"{n:d} = {res}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

2026年4月14日星期二

ZeroJudge 解題筆記：d120. 10699 - Count the factors

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

ZeroJudge 題目連結：d120. 10699 - Count the factors

解題想法

這題可以事先計算 1 到 1000000 對應的最小質因數，在找特定數字 $n$ 的質因數個數時會比較快，可以從目前的值跳到下一個質因數。如果直接用除的，逐一測試比目前數值 $x$ 還小的質因數，這樣也會過，只是速度慢一點。

Python 程式碼

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

def solve():
    import sys

    # 建表，1 ~ 1000000 之間每個數對應的最小質因數 smallest prime factor
    max_num = 1000000
    spf = [0]*(max_num + 1)
    for i in range(2, max_num + 1):
        if spf[i] == 0:  # i 是質數
            spf[i] = i
            if i*i <= max_num:
                for j in range(i*i, max_num + 1, i):
                    if spf[j] == 0:  # 如果 j 還沒有最小質因數，設定成 i
                        spf[j] = i
    # 主要的解題過程
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break  # 停止的條件
        if n == 1:  # 特例
            result.append("1 : 0\n")
            continue
        cnt = 0  # 質因數數量
        x = n  # n 的值存到 x
        while x > 1:  # 如果 x 還能分解繼續執行
            p = spf[x]  # 取出 x 的最小質因數
            cnt += 1
            while x%p == 0:  # 如果 p 可以整除 x 繼續執行
                x //= p  # x 除以 p
        result.append(f"{n:d} : {cnt:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

訂閱：意見 (Atom)

熱門文章

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月15日 星期三

解題想法

Python 程式碼

2026年4月14日 星期二

解題想法

Python 程式碼

2026年4月23日星期四

2026年4月22日星期三

2026年4月21日星期二

2026年4月20日星期一

2026年4月19日星期日

2026年4月18日星期六

2026年4月17日星期五

2026年4月16日星期四

2026年4月15日星期三

2026年4月14日星期二