ZeroJudge 解題筆記：d115. 數字包牌

作者：王一哲
日期：2025年8月22日


ZeroJudge 題目連結：d115. 數字包牌

解題想法

這題通常是用自訂函式及遞迴，窮舉所有的組合。如果用 Python 解題，可以使用迭代器 itertools.combinations。這題的測資不太，看起來兩者效率差不多。

Python 程式碼

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

def solve(idx, arr, maxdepth, choose):
    if len(choose) + len(arr) - idx < maxdepth:  # 如果剩下的數字不夠用，跳出函式
        return
    if len(choose) == maxdepth:  # 如果 choose 長度等於 maxdepth，印出 choose
        print(*choose); return
    for i in range(idx, len(arr)):  # 依序讀取 arr[idx] ~ arr[-1]
        choose.append(arr[i])  # arr[i] 加入 choose
        solve(i+1, arr, maxdepth, choose)  # 遞迴，idx 改成 i+1
        choose.pop()  # 移除 choose 最後一筆資料

while True:  # 無窮迴圈
    line = list(map(int, input().split()))  # 讀取一行資料
    if len(line) == 1 and line[0] == 0: break  # 如果只有一個 0，中止迴圈
    n, m = line[0], line[-1]  # n 個數取 m 個
    arr = sorted(line[1:-1])  # 可用的數字
    solve(0, arr, m, [])  # 呼叫 solve 解題
    print("")  # 最後要換行

ZeroJudge 解題筆記：c669. missing and duplicate

作者：王一哲
日期：2025年8月21日


ZeroJudge 題目連結：c669. missing and duplicate

解題想法

先讀取數列，將數列由小到大排序，取最小值 $imin$、最大值 $imax$、項數 $n$，等差數列加總理論值 $$ theory = \frac{(imin + imax) \times n}{2} $$ 如果實際上的數列加總為 $isum$，兩者相減 $$ diff = theory - isum = 缺少的項 - 重複的項 $$ 再用 set 刪除數列中重複的項，計算 set 的加總 $sum(uni)$，重複的項 $$ dup = isum - sum(uni) $$ 最後可以得到缺少的項 $$ mis = diff + dup $$

Python 程式碼

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

T = int(input())
for _ in range(T):
    arr = sorted(list(map(int, input().split())))  # 排序後的數列
    imin, imax, n = arr[0], arr[-1], len(arr)  # 最小值、最大值、數量
    isum = sum(arr)  # arr 的加總
    theory = (imin + imax) * n // 2  # 理論上的等差數量加總
    diff = theory - isum  # arr 加總與理論值的差
    uni = set(arr)  # 刪除重複的數字
    dup = isum - sum(uni)  # 重複的數字
    mis = dup + diff  # 遺失的數字
    print(mis, dup)

ZeroJudge 解題筆記：c665. 進制轉換

作者：王一哲
日期：2025年8月20日


ZeroJudge 題目連結：c665. 進制轉換

解題想法

先建立兩個對照表，table 是串列格式，用來找出 0 ~ 35 對應的字元；val 是字典格式，用來找出 0 ~ 35 字元對應的數值。用自訂函式 convert，將 a 進位制的字串 s 先轉換成 10 進位制的整數 d，再將 d 轉換成 b 進位制的字串 t。

Python 程式碼

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

import sys

# 0 ~ 35 對應的字元表格
table = [str(i) for i in range(10)]
for i in range(26): table.append(chr(i+ord('A')))

# 0 ~ 35 字元對應的數值
val = dict()
for i in range(10): val[str(i)] = i
for i in range(26): val[chr(i+ord('A'))] = i+10

# 主要的解題過程，a 進位制字串 s，轉成 b 進位制
def convert(s, a, b):
    d = 0  # 10 進位制的數字
    base = 1  # a 進位制基底
    for c in s[::-1]:  # 依序讀取 s[-1] ~ s[0]
        d += val[c]*base  # 更新 d
        base *= a  # 更新 base
    t = ""  # 儲存轉換後結果的空字串
    while d:  # 如果 d 大於 0 繼續執行
        t = table[d%b] + t  # d%b 代入 table 找出對應的字元
        d //= b  # 更新 d
    return t  # 回傳 t

for line in sys.stdin:
    n, b1, b2 = line.split()
    b1 = int(b1); b2 = int(b2)
    print(convert(n, b1, b2))

ZeroJudge 解題筆記：c658. 小新的提款卡密碼

作者：王一哲
日期：2025年8月19日


ZeroJudge 題目連結：c658. 小新的提款卡密碼

解題想法

先列出 1 ~ $10^{10}$ 之間的完全平方數 sq，將 sq 之中數字 0 ~ 9 的數量組成字串 dig，用字典儲存資料，以 dig 作為 key，以 sq 作為 value。讀取測資時，直接從表格中找出對應的答案，如果不在表格之中則印出 0。

Python 程式碼

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

import sys

def digits(num):  # 計算整數 0 ~ 9 的數量
    cnt = [0]*10  # 計數器
    for c in num: cnt[int(c)] += 1  # 從 nu 依序讀取字元 c 計算數量
    return "".join([str(i) for i in cnt])  # 取出 cnt 的資料組成字串再回傳

table = dict()  # 各種 0 ~ 9 出現數量對應的完全平方數
for i in range(1, 100000):  # 題目最大到 1E10，表格只要算 1 ~ 100000-1
    sq = i*i  # i 平方
    dig = digits(str(sq))  # 轉成 0 ~ 9 的數量字串
    if dig not in table: table[dig] = [sq]  # 如果 dig 不在 table 之中，新增 [sq]
    else: table[dig].append(sq)  # 反之，串列加入 sq

for line in sys.stdin:  # 讀取字串直到 EOF 為止
    dig = digits(line.strip())  # 計算 0 ~ 9 的數量
    if dig not in table: print(0)  # 如果 dig 不在 table 之中印出 0
    else: print(*table[dig])  # 反之印出 table[dig]

ZeroJudge 解題筆記：c657. 最長連續字母

作者：王一哲
日期：2025年8月18日


ZeroJudge 題目連結：c657. 最長連續字母

解題想法

依序讀取字串內容，如果這一個字母與前一個字母相同，連續相同字母長度加1；反之，更新最大值，重設連續相同字母長度為1。讀取完最後一個字母之後， 要再更新一次最大值。

Python 程式碼

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

import sys

for line in sys.stdin:
    line = line.strip()  # 讀取一行字串
    imax, cnt = 0, 1  # 最長連續字母長度，目前的連續字母長度
    ans = last = line[0]  # 答案對應的字母，目前的字母，預設為 line[0]
    for c in line[1:]:  # 依序讀取 line[1] ~ line[-1]
        if c == last: cnt += 1  # 如果 c 等於 last，cnt 加 1
        else:  # 如果 c 不等於 last
            if cnt > imax:  # 如果 cnt 大於 imax
                imax = cnt; ans = last  # 更新 imax, ans
            cnt = 1; last = c  # 重設 cnt, last
    if cnt > imax:  # 最後要再檢查一次
        imax = cnt; ans = last
    print(ans, imax)  # 印出答案

ZeroJudge 解題筆記：c560. SF 愛運動

作者：王一哲
日期：2025年8月17日


ZeroJudge 題目連結：c560. SF 愛運動

解題想法

用動態規畫解題，假設 $dp[i]$ 代表走到第 $i$ 階的方法數，走到第 1 階、1 種方法；走到第 2 階、1 種方法；走到第 3 階、2 種方法；走到第 4 階以上、$dp[i] = dp[i-1] + dp[i-3]$。

Python 程式碼

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

n, m = map(int, input().split())
ss = list(map(int, input().split()))
MOD = 1000000007
dp = [0]*(n+1)
dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2
for i in range(4, n+1): dp[i] = (dp[i-1] + dp[i-3]) % MOD
now, ans = 0, 1
for s in ss:
    ans = (ans * dp[s-now]) % MOD
    now = s

ans = (ans * dp[n-now]) % MOD
print(ans)

ZeroJudge 解題筆記：c440. Bert Love QQ !

作者：王一哲
日期：2025年8月16日


ZeroJudge 題目連結：c440. Bert Love QQ !

解題想法

由左向右依序讀取字元，目前讀到的 Q 總數為 tq，左側的 Q 加權後數量為 lq。讀到 Q 時答案 ans 加上 lq，並將 tq 加 1；讀到 A 時將 lq 加上 tq，相當於讀到第2個A時，第1個A左側的Q有效數量為2倍。

Python 程式碼

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

s = input()  # 要測試的字串
n = len(s)  # 字串長度
ans, lq, tq = 0, 0, 0  # 答案ans，左側Q的數量lq，Q的總數tq 
for c in s:  # 依序取出字元
    if c == 'Q':  # 如果讀到 Q
        ans += lq  # ans 加上 lq
        tq += 1  # tq 加 1
    elif c == 'A':  # 如果讀到 A
        lq += tq  # lq 加上 tq
# end of for loop
print(ans)  # 印出答案

ZeroJudge 解題筆記：c435. MAX ! MAX ! MAX !

作者：王一哲
日期：2025年8月15日


ZeroJudge 題目連結：c435. MAX ! MAX ! MAX !

解題想法

假設陣列 d 共有 n 項，用變數 small 記錄目前的最小值，變數 large 記錄目前的最大值，兩者預設值皆為 d[0]。由左向右掃過 d[1] ~ d[n-1]，如果 d[i] 小於 small，找到新的最小值，可能有新的答案；如果 d[i] 大於 large，重設 small 及 large。

Python 程式碼

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

n = int(input())  # 數量 n
d = list(map(int, input().split()))  # 要檢測的資料 d
small = large = d[0]  # 目前的最小值 small、最大值 large，先預設為 d[0]
ans = tmp = 0  # 答案 ans，暫存差距用的 tmp，先預設為 0
for i in range(1, n):  # 依序檢測 d[1] ~ d[n-1]
    if d[i] < small:  # 如果 d[i] 小於 small
        small = d[i]  # 更新 small 為 d[i]
        ans = max(large - small, tmp)  # ans 更新為 large - small 及 tmp 較大者
    elif d[i] > large:  # 如果 d[i] 大於 large
        tmp = ans  # 先將 ans 暫存到 tmp
        small = large = d[i]  # 更新 small、large 為 d[i]
# end of for loop
print(ans)  # 印出答案

ZeroJudge 解題筆記：c364. 我鄙視你

作者：王一哲
日期：2025年8月14日


ZeroJudge 題目連結：c364. 我鄙視你

解題想法

從每個人開始，向左、向右各找一次遞減序列。

Python 程式碼

從第9筆測資開始超過記憶體上限。

n = int(input())  # 人數
hs = [1000000001] + list(map(int, input().split())) + [1000000001]  # 身高，兩端加上很大的值
pre = [0]*(n+2)  # 前綴和
st = [0]  # 左側較高的人編號，先放入0
ans = [0]*(n+2)  # 每個人對應的答案，先預設為0
for i in range(1, n+1):  # 依序掃過第 1 ~ n 個人
    pre[i] = pre[i-1] + hs[i]  # 計算前綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] = pre[i-1] - pre[st[-1]]  # 更新答案為第 i-1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

post = [0]*(n+2)  # 後綴和
st = [n+1]  # 右側較高的人編號，先放入n+1
for i in range(n, 0, -1):  # 依序掃過第 n ~ 1 個人
    post[i] = post[i+1] + hs[i]  # 計算後綴和
    while hs[i] > hs[st[-1]]: st.pop()  # 如果第 i 個人身高高於 st 中最後一個人的身高，不斷移除 st 最後一項
    ans[i] += post[i+1] - post[st[-1]]  # 更新答案為第 i+1 ~ st[-1]+1 個人的身高總合
    st.append(i)  # 放入 i

for i in range(1, n+1): print(ans[i])  # 印出答案

ZeroJudge 解題筆記：c356. Justin 愛加密

作者：王一哲
日期：2025年8月13日


ZeroJudge 題目連結：c356. Justin 愛加密

解題想法

這題記憶體只有 16 MB，據說 Python 至少要用 32MB，如果記憶體太少一定會遇到 RE: code 127。要用 cstdio 函式庫中的 fgets，每次讀取指定長度的字元，這樣才能過關。

Python 程式碼

超過記憶體上限。

n = int(input())
s = input()
m = len(s)
d = -1
w = m//n
for i in range(0, m, n):
    d = (d+1)%w
    print(s[i+d], end="")
print()

ZeroJudge 解題筆記：c317. 硬幣問題！前傳

作者：王一哲
日期：2025年8月12日


ZeroJudge 題目連結：c317. 硬幣問題！前傳

解題想法

原則上盡量用面額最大的硬幣，這樣使用的硬幣總數會越少。

Python 程式碼

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

n = int(input())
for _ in range(n):
    x, a, b = map(int, input().split())
    na = x//a  # 硬幣 a 的數量
    x %= a  # x 剩下的數值
    nb = x//b  # 硬幣 b 的數量
    if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
        print(na+nb)  # 找到答案，印出 na+nb
    else:  # 否則要測試將硬幣 a 換回來的狀況
        while na > 0:  # 如果還有硬幣 a
            na -= 1  # na 減 1
            x += a  # x 加 a
            if x%b == 0:  # 如果硬幣 b 剛好可以整除 x
                nb = x//b  # 找到硬幣 b 正確的數量
                break  # 中止 while 迴圈
        # 如果 x 可以被 b 整除印出 na+nb，否則印出 -1
        print(na+nb if x%b == 0 else "-1")

ZeroJudge 解題筆記：c315. I, ROBOT 前傳

作者：王一哲
日期：2025年8月11日


ZeroJudge 題目連結：c315. I, ROBOT 前傳

解題想法

依序讀取測資並更新位置即可。

Python 程式碼

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

n = int(input())
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
x, y = 0, 0
for _ in range(n):
    a, b = map(int, input().split())
    x += dirs[a][0]*b
    y += dirs[a][1]*b
print(f"{x:d} {y:d}")

C++ 程式碼

使用時間約為 2 ms，記憶體約為 364 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int x = 0, y = 0;
    for(int i=0; i<n; i++) {
        int a, b; cin >> a >> b;
        x += dirs[a][0]*b;
        y += dirs[a][1]*b;
    }
    cout << x << " " << y << "\n";
    return 0;
}

使用時間約為 2 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int x = 0, y = 0;
    for(int i=0; i<n; i++) {
        int a, b; scanf("%d %d", &a, &b);
        x += dirs[a][0]*b;
        y += dirs[a][1]*b;
    }
    printf("%d %d\n", x, y);
    return 0;
}

ZeroJudge 解題筆記：c276. 沒有手機的下課時間

作者：王一哲
日期：2025年8月10日


ZeroJudge 題目連結：c276. 沒有手機的下課時間

解題想法

其實就是猜數字。先掃過一次，找出位置、數字皆正確的部分，再掃過一次，找出數字對、位置錯的部分。

Python 程式碼

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

ans = input()  # 答案
n = int(input())  # 猜測次數
for _ in range(n):  # 執行 n 次
    guess = input()  # 猜測的數字
    a, b = 0, 0  # 位置數字皆正確的個數 a，只有數字正確的個數 b
    ar, gr = [], []  # ans 及 guess 中檢測完位置及數字後剩下的部分
    for i in range(4):  # 先掃過一次
        if guess[i] == ans[i]:  # 位置數字皆正確
            a += 1  # a 加 1
        else:  # 否則將此位數加入 ar 及 gr
            ar.append(ans[i])
            gr.append(guess[i])
    for g in gr:  # 由 gr 依序取出數字
        if g in ar:  # 如果 ar 之中有 g 
            b += 1  # b 加 1
            ar.pop(ar.index(g))  # 將 ar 之中的 g 移除一個
    print(f"{a:d}A{b:d}B")  # 印出答案

ZeroJudge 解題筆記：c184. 盈虧互補

作者：王一哲
日期：2025年8月9日


ZeroJudge 題目連結：c184. 盈虧互補

解題想法

先找出 n 包含 1 的因數 fac 及加總 facSum，如果 facSum 等於 n，n 是完全數；如果 facSum 不等於 n，還要再找 facSum 的因數 fac2 及加總 facSum2，如果 facSum2 等於 n，則兩者是友好數。

Python 程式碼

用 set 儲存因數，用 join 組合要輸出的因數加總算式。使用時間約為 39 ms，記憶體約為 3.5 MB，通過測試。

n = int(input())  # 要測試數字 n
fac = {1}  # 儲存 n 的因數，先放入 1
for i in range(2, int(n**0.5)+1):
    if n%i == 0:
        fac.add(i)
        fac.add(n//i)
facSum = sum(fac)  # n 的因數加總
print("+".join(map(str, sorted(fac))) + "=" + f"{facSum:d}")  # 印出 n 的因數及加總
if n == facSum:  # 如果 n 等於 facSum
    print(f"{n:d} is perfect.")  # n 是完全數
elif len(fac) == 1:  # 如果 fac 只有 1
    print("=0")  # 印出 =0
    print(f"{n:d} has no friends.")  # 不可能有友好數
else:  # 其它狀況
    n2 = facSum  # 要檢測 facSum 是否為友好數
    fac2 = {1}  # 儲存 n2 的因數，先放入 1
    for i in range(2, int(n2**0.5)+1):
        if n2%i == 0:
            fac2.add(i)
            fac2.add(n2//i)
    facSum2 = sum(fac2)  # n2 的因數加總
    print("+".join(map(str, sorted(fac2))) + "=" + f"{facSum2:d}")  # 印出 n2 的因數及加總
    if facSum2 == n:  # 如果 facSum2 等於 n，兩者是友好數
        print(f"{n:d} and {n2:d} are friends.")
    else:  # 否則 n 沒有友好數
        print(f"{n:d} has no friends.")

ZeroJudge 解題筆記：b911. 我想跟Kevin借筷子系列4

作者：王一哲
日期：2025年8月8日


ZeroJudge 題目連結：b911. 我想跟Kevin借筷子系列4

解題想法

先列出幾種可能性

1. n = 0, data = [0], ans = 0
2. n = 1, data = [1], ans = 1
3. n = 2, data = [1, 2] => [0, 1] => [0, 0], ans = 2
4. n = 3, data = [1, 2, 3] => [1, 0, 1] => [0, 0, 0], ans = 2
5. n = 4, data = [1, 2, 3, 4] => [1, 0, 1, 2] => [0, 0, 0, 1] => [0, 0, 0, 0], ans = 3
6. n = 5, data = [1, 2, 3, 4, 5] => [1, 2, 0, 1, 2] => n = 2 的狀況，ans = 1 + 2 = 3
7. n = 6, data = [1, 2, 3, 4, 5, 6] => [1, 2, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
8. n = 7, data = [1, 2, 3, 4, 5, 6, 7] => [1, 2, 3, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
9. n = 8, data = [1, 2, 3, 4, 5, 6, 7, 8] => [1, 2, 3, 0, 1, 2, 3, 4] => n = 4 的狀況，ans = 1 + 3 = 4

找出規律，數量 n 如果可以除以 2 則 ans 加 1，直到 n = 1 時 ans 加 1 或是 n = 2 時 ans 加 2。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)
    ans = 0
    while n >= 1:
        if n == 1:
            ans += 1
            break
        elif n == 2:
            ans += 2
            break
        else:
            ans += 1
            n //= 2
    print(ans)

與上方的寫法邏輯相同，但改用遞迴，使用時間約為 24 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    def solve(x, a=0):
        if x == 1: return 1
        if x == 2: return 2
        return 1 + solve(x//2, a)
    # end of def
    print(solve(n))

ZeroJudge 解題筆記：b897. 10219 - Find the ways !

作者：王一哲
日期：2025年8月7日


ZeroJudge 題目連結：b897. 10219 - Find the ways !

解題想法

這題就是在計算組合數 $$ C^n_k = \frac{n!}{(n-k)! k!} = \frac{n(n-1)(n-2) \dots (n-k+1)}{k(k-1)(k-2) \dots \times 2 \times 1} $$ 取 $\log_{10}$ $$ \begin{align*} ans &= \log_{10} n + \log_{10} (n-1) + \log_{10} (n-2) + \dots + \log_{10} (n-k+1) \\ & ~~~~- (\log_{10} k + \log_{10} (k-1) + \log_{10} (k-2) + \dots + 0) \end{align*} $$ 最後再無條件進位到整數即為答案。
改用史特靈公式取近似，由其中一個表達式史特靈級數 $$ \ln n! = n \ln n - n + \frac{1}{2} \ln (2 \pi n) + \frac{1}{12n} - \frac{1}{360n^3} + \dots $$ 若忽略高次項並用換底公式換成以10為底的對數 $$ \begin{align*} \frac{\log_{10} n!}{\log_{10} e} &= n \cdot \frac{\log_{10} n}{\log_{10} e} - n + \frac{1}{2} \cdot \frac{\log_{10} (2 \pi n)}{\log_{10} e} \\ \log_{10} n! &= n \log_{10} n - n \log_{10} e + \frac{1}{2} \log_{10} (2 \pi) + \frac{1}{2} \log_{10} n \\ \log_{10} n! &\approx (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \end{align*} $$ 因此 $C^n_k$ 取 $\log_{10}$ $$ \begin{align*} & \\ \log_{10} C^n_k \approx & (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \\ & - [(n-k + 0.5) \log_{10} (n-k) - 0.4343 (n-k) + 0.39909] \\ & - [(k + 0.5) \log_{10} k - 0.4343 k + 0.39909] \end{align*} $$ 但是上式的第二行中有 $\log_{10}(n-k)$，當 $n=k$ 時會出問題，程式碼之中需要排除這個特例。

Python 程式碼

理論上用 math 函式庫中的 comb 可以很方便地計算組合數，但是這個函式在 Python 3.8 才加入，ZeroJudge 網站的 Python 版本為 3.6.9，不能用。

from math import comb, log10, ceil
import sys

for line in sys.stdin:
    n, k = map(int, line.split())
    print(ceil(log10(comb(n, k))))

改成不使用 comb，直接取 log10 ，還是會超時。

from math import log10, ceil
import sys

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == k: print("1")
    else:
        ans = 0
        for i in range(n, n-k, -1): ans += log10(i)
        for i in range(k, 1, -1): ans -= log10(i)
        print(ceil(ans))

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

from math import log10, ceil
import sys

def fac(x):
    return (x+0.5)*log10(x) - 0.4343*x + 0.39909

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == k: print("1")
    else: print(ceil(fac(n) - fac(n-k) - fac(k)))

ZeroJudge 解題筆記：b893. 勘根定理

作者：王一哲
日期：2025年8月6日


ZeroJudge 題目連結：b893. 勘根定理

解題想法

因為 $-2147483647 \leq x^6 \leq 2147483647 ~\Rightarrow -36 \leq x \leq 36$，只要一路由 $-36$ 每次加 1 檢測到 $36$ 即可。 這題的敘述有問題，題目中說無解時輸出 N0THING! >\\<，但實際上是 N0THING! >\\\<。

Python 程式碼

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

def func(x):
    return a*x**5 + b*x**4 + c*x**3 + d*x**2 + e*x + f

a, b, c, d, e, f = map(int, input().split())
if a == b == c == d == e == f == 0:
    print("Too many... = =\"")
else:
    real = False
    for i in range(-36, 36):
        if func(i) == 0:
            print(f"{i:d} {i:d}")
            real = True
        elif func(i)*func(i+1) < 0:
            print(f"{i:d} {i+1:d}")
            real = True
    if not real: print("N0THING! >\\\\\\<")

ZeroJudge 解題筆記：b877. 我是電視迷

作者：王一哲
日期：2025年8月5日


ZeroJudge 題目連結：b877. 我是電視迷

解題想法

這題可以用 if 判斷頻道號碼是否已經超過上限，從最前面繞回來；也可以取餘數找下一個頻道號碼。

Python 程式碼

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

a, b = map(int, input().split())
if b > a: print(b-a)
else: print(100-a+b)

將第2、3行合併。使用時間約為 17 ms，記憶體約為 3.3 MB，通過測試。

a, b = map(int, input().split())
print(b-a if b > a else 100-a+b)

取餘數，因為 Python 的取餘數若遇到被除數是負值，會先將被除數加上除數之後再取餘數，餘數和除數同號，不需要像 C++ 要在程式碼中自己加上除數量值。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

a, b = map(int, input().split())
print((b-a)%100)

ZeroJudge 解題筆記：b860. 獨角蟲進化計算器

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


ZeroJudge 題目連結：b860. 獨角蟲進化計算器

解題想法

用 while 迴圈不斷更新糖果、獨角蟲、鐵殼蛹的數量，直到獨角蟲的數量歸零為止。

Python 程式碼

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

c, w = map(int, input().split())  # 讀取糖果數量 c，獨角蟲數量 w
k = 0  # 鐵殼蛹數量 k

while w > 0:  # 如果 w 大於 0 繼續執行
    if c >= 12 and w >= 1:  # 如果 c 大於等於 12 而且 w 大於等於 1 才能進化
        c -= 10  # c 減 10，先用掉 12 顆，進化得 1 顆，再將鐵殼蛹送給博士得 1 顆
        w -= 1  # 進化，獨角蟲數量 w 減 1
        k += 1  # 鐵殼蛹數量 k 加 1
    else:  # 否則將獨角蟲送給博士換糖果
        w -= 1
        c += 1
# end of while loop
print(k)  # 印出答案

ZeroJudge 解題筆記：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

作者：王一哲
日期：2025年8月3日


ZeroJudge 題目連結：b836. kevin戀愛攻略系列題-2 說好的霸王花呢??

解題想法

共有 $n$ 片花瓣，第一次拔1片，接下來每次比上一次多拔 $m$ 片，假設共拔 $k$ 次，拔掉的花瓣總數為 $$ t = k + [m + 2m + 3m + \dots + (k-1)m] = k + \frac{(k-1)km}{2} = \frac{1}{2} [m k^2 + (2-m) k] $$ 若要剛好拔完，則 $t = n$，且 $k \in N$ 才能符合條件，因此 $$ mk^2 + (2-m)k - 2n = 0 $$ 若有正整數的根，輸出 "Go Kevin!!"，否則輸出 "No Stop!!"。

Python 程式碼

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

import sys, math

for line in sys.stdin:  # 讀取多行測資直到 EOF 為止
    n, m = map(int, line.split())  # 花瓣數量 n，每次多拔的花瓣數量 m
    if m == 0:  # 如果 m 等於 0 一定有解
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    a, b, c = m, 2-m, -2*n  # 一元二次方程式的係數
    D = b*b - 4*a*c  # 判別式
    if D < 0:  # 判別式小於 0 無實數解
        print("No Stop!!")  # 印出 No Stop!!，繼續檢測下一行
        continue
    x1 = (-b + math.sqrt(D)) / (2*a)  # 較大的根
    x2 = (-b - math.sqrt(D)) / (2*a)  # 較小的根
    if x1 > 0 and int(x1) == math.ceil(x1):  # 如果 x1 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    elif x2 > 0 and int(x2) == math.ceil(x2):  # 如果 x2 是正整數
        print("Go Kevin!!")  # 印出 Go Kevin!!，繼續檢測下一行
        continue
    else: print("No Stop!!")  # 否則印出 No Stop!!

ZeroJudge 解題筆記：b762. 英國聯蒙

作者：王一哲
日期：2025年8月2日


ZeroJudge 題目連結：b762. 英國聯蒙

解題想法

這題用字典或串列儲存對應的訊息，寫起來會比較簡潔。

Python 程式碼

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

act = {"Get_Kill": 1, "Get_Assist": 2, "Die": 3}  # 輸入的狀態
# 連續擊殺數對應的訊息
kill_mess = ["",
             "You have slain an enemie.",
             "You have slain an enemie.",
             "KILLING SPREE!",
             "RAMPAGE~",
             "UNSTOPPABLE!",
             "DOMINATING!",
             "GUALIKE!",
             "LEGENDARY!"]
# 陣亡時連續擊殺數對應的訊息
die_mess = [ "You have been slained.",
             "SHUTDOWN."]

N = int(input())  # 指令數量
cont = 0  # 連續擊殺數
kill = 0  # 總擊殺數
ast = 0  # 助攻次數
die = 0  # 陣亡次數
for _ in range(N):
    a = act[input().strip()]  # 讀取 N 行指令，要用 strip() 刪除某些測資後方多的 \t 或空白
    if a == 1:  # 如果是 Get_Kill
        cont += 1  # 連續擊殺數加 1
        if cont >= 8: print(kill_mess[8])  # 如果連續擊殺數大於等於 8，印出 kill_mess[8]
        else: print(kill_mess[cont])  # 否則印出 kill_mess[cont]
    elif a == 2: ast += 1  # 如果是 Get_Assist 助攻數加 1
    elif a == 3:  # 如果是 Die
        if cont < 3: print(die_mess[0])  # 如果連續擊殺數小於 3，印出 die_mess[0]
        else: print(die_mess[1])  # 否則印出 die_mess[1]
        die += 1  # 陣亡次數加 1
        kill += cont  # 更新擊殺總數
        cont = 0  # 連續擊殺數歸零
kill += cont  # 最後要再加上一次連續擊殺數
print(f"{kill:d}/{die:d}/{ast:d}")  # 印出答案

ZeroJudge 解題筆記：b759. 我明明就有說過= =

作者：王一哲
日期：2025年8月1日


ZeroJudge 題目連結：b759. 我明明就有說過= =

解題想法

這題可以只用字串切片或是索引值組合出每次要印出的內容，也可以每次都更新字串的內容，兩種方法的速度都很快。

Python 程式碼

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

X = input()
for i in range(len(X)):
    print(X[i:]+X[:i])

每次印出字串後，重新組合字串。使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

X = input()
for i in range(len(X)):
    print(X)
    X = X[1:] + X[0]