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

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})")  # 印出答案

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

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

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

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

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

ZeroJudge 解題筆記：d117. 10924 - Prime Words

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


ZeroJudge 題目連結：d117. 10924 - Prime Words

解題想法

因為題目的字元編號最大值為 $52$，字串長度最大值為 $20$，因此只要建 $0$ 到 $1040$ 之間的質數表就可以了。需要注意，這題的 $1$ 被當作質數，因為範例測資中的 a 答案為 "It is a prime word."。接下來讀取字串，計算各字元的編號加總，查質數表，輸出對應的答案。

Python 程式碼

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

def solve():
    import sys

    maxn = 1040
    sieve = [True]*(maxn+1)
    sieve[0] = 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
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        s = data[ptr]
        ptr += 1
        total = 0
        for c in s:
            if c.isupper():
                total += ord(c) - ord('A') + 27
            elif c.islower():
                total += ord(c) - ord('a') + 1
        result.append("It is a prime word.\n" if sieve[total] else "It is not a prime word.\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

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