熱門文章

2025年9月21日 星期日

ZeroJudge 解題筆記:e420. 灰姑娘的新衣

作者:王一哲
日期:2025年9月20日


ZeroJudge 題目連結:e420. 灰姑娘的新衣

解題想法


我用字典 color_idx 儲存各種顏色對應的衣服編號,另一個字典 idx_color 儲存各種衣服編號有的顏色,顔色不重複。最後再計算所有的組合數,輸出最多顔色的衣服,輸出完美搭配的顔色。

Python 程式碼


使用時間約為 22 ms,記憶體約為 3.7 MB,通過測試。
import sys
from collections import defaultdict

color_idx = defaultdict(list)  # 各種顏色對應的衣服編號,可重複
idx_color = defaultdict(set)  # 各種衣服編號有的顏色,不重複
cnt = 0  # 衣服編號
for line in sys.stdin:
    line = line.strip()  # 刪除最後的 \n
    cnt += 1  # 衣服編號加 1
    color_idx[line].append(cnt)  # 顏色 line 有的編號加上 cnt
    idx_color[cnt].add(line)  # 編號 cnt 有的顏色加上 line
    for s in sys.stdin:
        s = s.strip()  # 讀取一行字串,刪除最後的 \n
        if s == "@" or s == "#": break  # 讀到 # 或 @,中止迴圈
        color_idx[s].append(cnt)  # 顏色 s 有的編號加上 cnt
        idx_color[cnt].add(s)  # 編號 cnt 有的顏色加上 s,不重複
comb = 1  # 組合數
for v in idx_color.values(): comb *= len(v)
print(comb)
most_color = []
n = len(idx_color)  # 編號數量
perfect = []
imax = max([len(v) for v in color_idx.values()])
for k, v in color_idx.items():
    if len(v) == imax:
        most_color.append(k)
    if len(set(v)) == n:
        perfect.append(k)
print(",".join(sorted(most_color)))
print(",".join(sorted(perfect)))


2025年9月20日 星期六

ZeroJudge 解題筆記:e293. 花開花落,雨初臨

作者:王一哲
日期:2025年9月20日


ZeroJudge 題目連結:e293. 花開花落,雨初臨

解題想法


這題的題目敘述根本就是在寫小說,重點只有「要找出給定的數字在 100 以內的質因數」。解題時要先建表 primes,列出 0 到 100 之間的質數,只有 25 個,直接打進程式碼就好。接下來計算這些質數相乘的結果 pq,假設要檢查的數字為 $m$,如果 $s = gcd(m, pq)$ 等於 1,則 $m$ 在 0 到 100 之間沒有質因數;反之,從 primes 之中依序取出質數 prime,檢查 prime 是否為 s 的因數即可。不過這題的輸出最大會到 5000 位,要用大數運算,所以我只有用 Python 解題。

Python 程式碼


使用時間約為 0.7 s,記憶體約為 29.3 MB,通過測試。
import sys, math

# 建表,2 ~ 100 之間的質數
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
          31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
          73, 79, 83, 89, 97}
# pq,2 ~ 100 所有的質數相乘
pq = 1
for prime in primes: pq *= prime
# 主要的解題過程
result = []  # 儲存結果用的空串列
lines = sys.stdin.readlines()
for line in lines[1:]:
    m = int(line)  # 轉成整數 m
    res = []  # 儲存 m 的答案用的空串列
    s = math.gcd(m, pq)
    if s == 1:  # m 在 0 到 100 之間沒有質因數
        result.append("Terrible Silence...\n")
    else:
        for prime in primes:  # 依序由 primes 中取出質數,檢查是否為 s 的因數
            if s%prime == 0:  # 如果 prime 是因數
                res.append(f"{prime:d}")  # prime 轉成字串加入 res
        result.append(" ".join(res) + "\n")
sys.stdout.write("".join(result))


2025年9月19日 星期五

ZeroJudge 解題筆記:e284. 放暑假了!!!!!

作者:王一哲
日期:2025年9月19日


ZeroJudge 題目連結:e284. 放暑假了!!!!!

解題想法


這題主要考輸入、輸出優化,因為測資數量極大,如果沒有優化輸入、輸出會超時。在 Python 我習慣用 sys.stdin.readlines() 一次讀取所有的測資,並將所有的輸出存在串列 result 之中,最後再用 sys.stdout.write("".join(result)) 一次印出所有答案。在 C++ 如果要用 cin 及 cout,必須加上 ios::sync_with_stdio(0); cin.tie(0);,不然就是改用 scanf 及 printf。事先用字典或集合建表,儲存 $2^0$ 到 $2^31$ 對應的值,讀取測資之後再判斷這個數字是否在表格之中,這樣速度會比較快。但是經過實測之後發現,C++ 的 map 及 unordered_map 都很慢,要用 set 才能過關; Python 的 dict, defaultdict, set 都能過關。

Python 程式碼


用 dict 建表,使用時間約為 4.2 s,記憶體約為 413.6 MB,通過測試。
import sys

table = dict()
x = 1
for _ in range(32):
    table[x] = True
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

用 set 建表,使用時間約為 4.1 s,記憶體約為 418.2 MB,通過測試。
import sys

table = set()
x = 1
for _ in range(32):
    table.add(x)
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))


2025年9月18日 星期四

ZeroJudge 解題筆記:e272. gcd(Fm,Fn)

作者:王一哲
日期:2025年9月18日


ZeroJudge 題目連結:e272. gcd(Fm,Fn)

解題想法


這題考數學,必須運用費氏數列的特性 $$ gcd(F_m, F_n) = F_{gcd(m, n)} $$ 如果直接計算 $F_m, F_n$ 的數值再取 $gcd$,在 $m, n$ 極大的狀況下會超時。

Python 程式碼


使用時間約為 0.3 s,記憶體約為 4.6 MB,通過測試。
import sys, math

fib = [0]*94
fib[1] = 1
for i in range(2, 94):
    fib[i] = fib[i-1] + fib[i-2]

for line in sys.stdin:
    a, b = map(int, line.split())
    print(fib[math.gcd(a, b)])


2025年9月17日 星期三

ZeroJudge 解題筆記:e128. 新北100-1貪食蛇

作者:王一哲
日期:2025年9月17日


ZeroJudge 題目連結:e128. 新北100-1貪食蛇

解題想法


這題要找位置的數學規律,如果模擬移動的過程一定會超時。

Python 程式碼


使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
import math, sys

def find_position(t):  # 輸入目前的時刻計算位置
    if t == 1: return (1, 1)  # 特例,t 等於 1,回傳 (1, 1) 並結束函式
    
    ring = math.floor(math.sqrt(t))  # 已走完的圈數
    #ring = math.isqrt(t)    # 已走完的圈數,Python 3.8 之後才有 math.isqrt
    
    t -= ring * ring  # t 扣掉已走完的圈數平方,換成位移量
    if t == 0:  # 如果 t 等於 0,剛好在這圈結束的位置
        if ring%2: return (1, ring)  # 如果是奇數圈,回傳 (1, ring) 並結束函式
        else: return (ring, 1)  # 如果是偶數圈,回傳 (ring, 1) 並結束函式
    else: ring += 1  # 其它狀況,圈數加 1
    
    x, y = 0, 0  # 座標 (x, y)
    if ring%2:  # 奇數圈
        if t > ring:  # 在底部向左移動
            x = 2*ring - t  
            y = ring
        else:  # 在右側向下移動
            x = ring
            y = t
    else:  # 偶數圈
        if t > ring:  # 在右側向上移動
            x = ring
            y = 2*ring - t
        else:  # 在底部向右移動
            x = t
            y = ring
    
    return (x, y)

for line in sys.stdin:
    t = int(line)
    if t == 0: break
    print(*find_position(t))


2025年9月16日 星期二

ZeroJudge 解題筆記:d985. Gran Turismo 5

作者:王一哲
日期:2025年9月16日


ZeroJudge 題目連結:d985. Gran Turismo 5

解題想法


依序讀取每一圈的時間,將單位換成 s,更新最短秒數、計算總秒數,最後輸出所有圈數的最短秒數及平均。

Python 程式碼


使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
track = 0  # 圈數
N = int(input())  # N 組測資
for _ in range(N):  # 執行 N 次
    track += 1  # 圈數加 1
    print(f"Track {track:d}:")
    M = int(input())  # M 行資料
    best = float('inf')  # 最短秒數
    total = 0  # 總秒數
    for _ in range(M):  # 執行 M 次
        m, s = map(int, input().split())  # 單圈時間 m's"
        t = m*60 + s  # 換成秒數
        best = min(best, t)  # 新的最短秒數
        total += t  # 更新總秒數
    average = total // M  # 平均值
    print(f"Best Lap: {best//60:d} minute(s) {best%60:d} second(s).")
    print(f"Average: {average//60:d} minute(s) {average%60:d} second(s).")
    print()


2025年9月15日 星期一

ZeroJudge 解題筆記:d984. 棄保效應

作者:王一哲
日期:2025年9月15日


ZeroJudge 題目連結:d984. 棄保效應

解題想法


我用三層 if 解題,討論 A、B、C 三個人分別為最高票的狀況下,第一名票數減去第三名的票數之後是否仍大於第二名的票數。

Python 程式碼


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

for line in sys.stdin:
    a, b, c = map(int, line.split())  # 三個人的票數
    if a > b and a > c:  # A 最高票
        if b > c:  # B 第二名
            if a-c > b: print("A")  # A 減 C 的票數還贏
            else: print("B")  # 反之 B 贏
        else:  # C 第二名
            if a-b > c: print("A")  # A 減 B 的票數還贏
            else: print("C")  # 反之 C 贏
    elif b > a and b > c:  # B 最高票
        if a > c:  # A 第二名
            if b-c > a: print("B")  # B 減 C 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # C 第二名
            if b-a > c: print("B")  # B 減 A 的票數還贏
            else: print("C")  # 反之 C 贏
    else:  # C 最高票
        if a > b:  # A 第二名
            if c-b > a: print("C")  # C 減 B 的票數還贏
            else: print("A")  # 反之 A 贏
        else:  # B 第二名
            if c-a > b: print("C")  # C 減 A 的票數還贏
            else: print("B")  # 反之 B 贏


2025年9月14日 星期日

ZeroJudge 解題筆記:d881. 作業苦多

作者:王一哲
日期:2025年9月14日


ZeroJudge 題目連結:d881. 作業苦多

解題想法


這題可以寫迴圈直接跑,也可以先推導數學公式之後再代公式求解。

Python 程式碼


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

for line in sys.stdin:
    d = int(line)  # 公差的增量
    dp = [0]*51  # 儲存第 0 ~ 50 項的串列
    dp[1] = 1  # 第 1 項為 1
    b = 1  # 公差,預設為 1
    isum = 1  # 加總,先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        dp[i] = dp[i-1] + b  # 第 i 項為第 i-1 項加上 b
        isum += dp[i]  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

只要用到前一項,使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
import sys

for line in sys.stdin:
    d = int(line)  # 公差的增量
    last = 1  # 第 1 項為 1
    b = 1  # 公差,預設為 1
    isum = 1  # 加總,先加第 1 項
    for i in range(2, 51):  # 計算第 2 到 50 項
        last += b  # 第 i 項為第 i-1 項加上 b
        isum += last  # 更新 isum
        b += d  # 更新 b
    print(isum)  # 印出 isum

直接代公式,使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
import sys

for line in sys.stdin:
    print(1275 + int(line)*19600)


2025年9月13日 星期六

ZeroJudge 解題筆記:d732. 二分搜尋法

作者:王一哲
日期:2025年9月13日


ZeroJudge 題目連結:d732. 二分搜尋法

解題想法


可以自訂二分搜尋法的函式,也可以用 Python 的 bisect.bisect_left 或是 C++ algorithm 函式庫的 lower_bound 解題。注意,這題的位數是從 1 開始計算,搜尋到的索引值要加 1 才是答案。

Python 程式碼


自己寫二分搜尋法,使用時間約為 1.1 s,記憶體約為 20.9 MB,通過測試。
def binary_search(arr, target):  # 自己寫二分搜尋法,代入串列 arr 及目標 target
    low, high = 0, len(arr)-1  # 索引值的下限、上限
    while low <= high:  # 如果 low 小於等於 high 繼續執行
        mid = (high - low) // 2 + low  # 計算中間值 mid
        if arr[mid] == target: return mid+1  # 找到目標,回傳 mid,離開函式
        if arr[mid] > target:  # 目標在左半邊,降低 high
            high = mid - 1
        else:  # 目標在右半邊,提升 low
            low = mid + 1
    if arr[low] != target: return 0  # 如果沒有找到目標,回傳 0

if __name__ == "__main__":
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    for t in map(int, input().split()):
        print(binary_search(arr, t))

bisect_left,使用時間約為 0.3 s,記憶體約為 20.9 MB,通過測試。
from bisect import bisect_left

n, k = map(int, input().split())
arr = list(map(int, input().split()))
for x in map(int, input().split()):
    idx = bisect_left(arr, x)
    if arr[idx] == x: print(idx+1)
    else: print(0)


2025年9月12日 星期五

ZeroJudge 解題筆記:d710. parking lot

作者:王一哲
日期:2025年9月12日


ZeroJudge 題目連結:d710. parking lot

解題想法


這題用字典儲存資料很方便,一個儲存廠牌對應的顏色,另一個儲存顏色對應的廠牌,最後再依照測資從字典中讀取資料並輸出。

Python 程式碼


使用時間約為 23 ms,記憶體約為 3.6 MB,通過測試。
import sys
from collections import defaultdict

for line in sys.stdin:
    if not line.strip(): continue  # 跳過空行
    n, m = map(int, line.split())  # n 輛車, m 個指示
    brands = defaultdict(list)  # 廠牌對應的顏色
    colors = defaultdict(list)  # 顏色對應的廠牌
    for _ in range(n):  # 讀取 n 行資料
        b, c = input().split()  # 廠牌 b,顏色 c
        brands[b].append(c)
        colors[c].append(b)
    for _ in range(m):  # 讀取 m 個指示
        x, y = input().split()
        if x == "brand":  # 如果 x 等於 brand
            for c in brands[y]:  # 依序取出 brands[y] 的顏色
                print(f"{y:s} {c:s}")
        elif x == "color":  # 如果 x 等於 color
            for b in colors[y]:  # 依序取出 colors[y] 的廠牌
                print(f"{b:s} {y:s}")
    print()  # 空一行


2025年9月11日 星期四

ZeroJudge 解題筆記:d681. BinaryCount

作者:王一哲
日期:2025年9月11日


ZeroJudge 題目連結:d681. BinaryCount

解題想法


每次讀取一行字串,直到 EOF 為止。將字串用空格分割,如果分割後的字串為 s,在 Python 可以用 int(s, 2) 轉換成 int,在 C++ 可以用 bitset。先儲存首項的數值,接下來一次讀取一個運算符號及整數,依照運算符號計算數值,同時組合要輸出的運算式。

Python 程式碼


使用時間約為 0.1 s,記憶體約為 3.6 MB,通過測試。
import sys

for line in sys.stdin:
    arr = list(line.split())  # 分割讀到的字串
    equ = [arr[0]]  # 要輸出的算式,先放入 arr[0]
    last = int(arr[0], 2)  # 前一個計算結果,先放入 arr[0] 用 2 進位換算的整數
    n = len(arr)  # arr 的長度
    for i in range(1, n, 2):  # 依序處理 arr[1], arr[2] ~ arr[n-2], arr[n-1]
        op = arr[i]  # 運算符號
        if op == "and":  # 如果是 and
            equ.append("&&")  # 將 && 加入 equ
            last = last & int(arr[i+1], 2)  # 將 last 與 arr[i+1] 用 2 進位換算的整數取 &
        elif op == "or":  # 如果是 or
            equ.append("||")  # 將 || 加入 equ
            last = last | int(arr[i+1], 2)  # 將 last 與 arr[i+1] 用 2 進位換算的整數取 |
        equ.append(arr[i+1])  # 將 arr[i+1] 加入 equ
    print("".join(equ) + " = " + bin(last)[2:].zfill(5))  # 拼成要輸出的算式,計算結果要補 0


2025年9月10日 星期三

ZeroJudge 解題筆記:d643. 勞動的符咒

作者:王一哲
日期:2025年9月10日


ZeroJudge 題目連結:d643. 勞動的符咒

解題想法


如果輸入的字串 s 長度為 n,先找 n 的所有因數,再用字串切片,將 s 切成因數長度的子字串,將子字串排序後連接成新的字串 t。用集合 spells 儲存新的咒語,如果 t 不在 spells 之中才輸出。

Python 程式碼


使用時間約為 0.1 s,記憶體約為 14.4 MB,通過測試。
s = input().strip()  # 讀取字串
n = len(s)  # 字串長度
factors = {1}  # n 的因數,先放入 1
for i in range(2, int(n**0.5)+1):  # 找 2 ~ sqrt(n)+1 之間的因數
    if n%i == 0:
        factors.add(i)
        factors.add(n//i)
spells = {s}  # 可能的咒語,先放入 s
for factor in sorted(factors):  # 測試由小到大的所有因數
    # 取因數長度的子字串,排序後接成新的字串 t
    t = "".join(sorted([s[i:i+factor] for i in range(0, n, factor)]))
    if t not in spells:  # 如果 t 不在 spells 之中
        spells.add(t)  # t 加入 spells
        print(t)  # 印出 t
if len(spells) == 1: print("bomb!")  # 如果 spells 只有一項,印出 bomb!


2025年9月9日 星期二

ZeroJudge 解題筆記:d637. 路過的鴨duck

作者:王一哲
日期:2025年9月9日


ZeroJudge 題目連結:d637. 路過的鴨duck

解題想法


這題考 0/1 背包問題,我習慣的寫法是先建立一個一維陣列 dp,分別對應食量為 0 ~ 上限 imax 對應的最大飽足感總和。依序讀取每個食物的體積 a 及飽足感 b,從 dp[imax] 往回更新總和至 dp[a] 為止,取 dp[i] 與 dp[i-a] + b 較大者,最後答案在 dp[imax] 。

Python 程式碼


使用時間約為 0.4 s,記憶體約為 3.3 MB,通過測試。
n = int(input())  # n 顆飼料
imax = 100  # 食量上限
dp = [0]*(imax + 1)  # 吃 0 ~ 100 分別對應的最大飽足感
for _ in range(n):  # 依序讀取 n 行資料
    a, b = map(int, input().split())  # 飼料的體積 a、飽足感 b
    for i in range(imax, a-1, -1):  # 倒序檢查飽足感 imax ~ a
        dp[i] = max(dp[i], dp[i-a] + b)  # dp[i-a] + b 可能更大
print(dp[imax])  # 印出最大值


2025年9月8日 星期一

ZeroJudge 解題筆記:d636. 大爆炸bomb

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


ZeroJudge 題目連結:d636. 大爆炸bomb

解題想法


這題考快速冪、平方求冪 (exponentiating by squaring)

Python 程式碼


使用時間約為 19 ms,記憶體約為 3.3 MB,通過測試。
def exp(x, y, p):  # x 的 y 次方,取除以 p 的餘數
    t = 1  # 儲存結果用的變數
    while y:  # 如果 y 不等於 0 繼續執行
        if y&1: t = t*x%p  # 若 y 與 1 取 and 為 1,更新 t,乘上 x 再取 mod p
        y >>= 1  # y 除以 2
        x = x*x%p  # 更新 x,乘上 x 再取 mod p
    return t  # 回傳 t

print(exp(*map(int, input().split()), 10007))  # 印出 exp(a, b, p)

用 pow 作弊,使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
print(pow(*map(int, input().split()), 10007))


2025年9月7日 星期日

ZeroJudge 解題筆記:d626. 小畫家真好用

作者:王一哲
日期:2025年9月7日


ZeroJudge 題目連結:d626. 小畫家真好用

解題想法


用 BFS 及四方位檢查解題,由於我比較懶得檢查邊界值,我會在周圍加上 + 當作哨兵避免出界。

Python 程式碼


使用時間約為 24 ms,記憶體約為 3.5 MB,通過測試。
n = int(input())  # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)]  # 讀取地圖資料,最右側加上 + 作為哨兵
grid.append(list("+"*(n+1)))  # 最下方加 n+1 個 + 作為哨兵
que = [tuple(map(int, input().split()))]  # 待走訪佇列,先放入起點
head = 0  # 從 que 讀取資料用的索引值
while head < len(que):  # BFS,當 head 還沒有出界繼續執行
    r, c = que[head]; head += 1  # 從 que 讀取要走訪的點 (r, c),head 加 1
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
        nr, nc = r+dr, c+dc  # 要檢查的點 (nr, nc)
        if grid[nr][nc] == "+": continue  # 如果 grid[nr][nc] 是 +,找下一個點
        grid[nr][nc] = "+"  # grid[nr][nc] 改成 +
        que.append((nr, nc))  # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n]))  # 依序讀取 grid[:n][:n],接成字串再輸出

改用 deque 儲存待走訪節點,使用時間約為 25 ms,記憶體約為 3.7 MB,通過測試。
from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input().strip()) + ["+"] for _ in range(n)]  # 讀取地圖資料,最右側加上 + 作為哨兵
grid.append(list("+"*(n+1)))  # 最下方加 n+1 個 + 作為哨兵
que = deque([tuple(map(int, input().split()))])  # 待走訪佇列,先放入起點
while que:  # BFS,當 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除要走訪的點 (r, c)
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
        nr, nc = r+dr, c+dc  # 要檢查的點 (nr, nc)
        if grid[nr][nc] == "+": continue  # 如果 grid[nr][nc] 是 +,找下一個點
        grid[nr][nc] = "+"  # grid[nr][nc] 改成 +
        que.append((nr, nc))  # (nr, nc) 加入 que
for i in range(n): print("".join(grid[i][:n]))  # 依序讀取 grid[:n][:n],接成字串再輸出


2025年9月6日 星期六

ZeroJudge 解題筆記:d623. 反方陣

作者:王一哲
日期:2025年9月6日


ZeroJudge 題目連結:d623. 反方陣

解題想法


假設矩陣 $$ M = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} $$ 其行列式值 $det(M) = ad - bc$。如果 $det(M) \neq 0$,$M$ 是可逆的,其反矩陣 $$ M^{-1} = \frac{1}{det(M)} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix} $$ 另外要注意,題目的說明是4個0表示結束實際測資以一個零表示結束

Python 程式碼


使用時間約為 28 ms,記憶體約為 3.3 MB,通過測試。
while True:
    line = list(map(int, input().split()))
    if len(line) == 1 and line[0] == 0: break  # 只有一個 0,中止迴圈
    a, b = line  # 方陣 [[a, b], [c, d]]
    c, d = map(int, input().split())
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        print("cheat!")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        print(f"{d/det:.5f} {-b/det:.5f}")
        print(f"{-c/det:.5f} {a/det:.5f}")

使用時間約為 24 ms,記憶體約為 3.6 MB,通過測試。
import sys

result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    if lines[idx].strip() == "0": break  # 只有一個 0,中止迴圈
    a, b = map(int, lines[idx].split())  # 方陣 [[a, b], [c, d]]
    idx += 1
    c, d = map(int, lines[idx].split())
    idx += 1
    det = a*d - b*c  # 行列式值
    if det == 0:  # 沒有反方陣
        result.append("cheat!\n")
    else:  # 反方陣 (1/det)*[[d, -b], [-c, a]]
        result.append(f"{d/det:.5f} {-b/det:.5f}\n")
        result.append(f"{-c/det:.5f} {a/det:.5f}\n")
sys.stdout.write("".join(result))


2025年9月5日 星期五

ZeroJudge 解題筆記:d586. 哈密瓜美語

作者:王一哲
日期:2025年9月5日


ZeroJudge 題目連結:d586. 哈密瓜美語

解題想法


這題用兩個字典建立數字轉英文、英文轉數字的對照表,再依照讀取到的測資開頭是數字或字母,判斷要從哪一個表格找答案。

Python 程式碼


使用時間約為 49 ms,記憶體約為 5.5 MB,通過測試。
s1 = "mjqhofawcpnsexdkvgtzblryui"  # 數字轉英文用的字串
s2 = "uzrmatifxopnhwvbslekycqjgd"  # 英文轉數字用的字串
ntoc, cton = dict(), dict()  # 數字轉英文、英文轉數字的對照表
for i, c in enumerate(s1, start=1): ntoc[str(i)] = c
for i, c in enumerate(s2, start=1): cton[c] = i
n = int(input())  # n 道謎題
for _ in range(n):  # 執行 n 次
    line = list(input().split())  # 讀取一行資料分割後存入串列
    m = int(line[0])  # 資料長度為 m
    if line[1].isalpha():  # 如果 line[1] 是字母
        print(sum(cton[c] for c in line[1:]))  # 依序讀取 line[1] ~ line[-1] 代入表中找數字求加總
    else:  # 如果 line[1] 是數字
        print("".join([ntoc[i] for i in line[1:]]))  # 依序讀取 line[1] ~ line[-1] 代入表中找字母組成字串


2025年9月4日 星期四

ZeroJudge 解題筆記:d584. 技能點數skill

作者:王一哲
日期:2025年9月4日


ZeroJudge 題目連結:d584. 技能點數skill

解題想法


依照職業及當時的等級更新技能點數即可。

Python 程式碼


使用時間約為 20 ms,記憶體約為 3.4 MB,通過測試。
import sys

result = []
lines = sys.stdin.readlines()
for line in lines:
    job, level = map(int, line.split())
    tot = 0
    if job == 2 and level >= 8:  # 如果是法師,8 級一轉
        tot += 1 + (level-8)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    elif (job == 1 or job == 3 or job == 4) and level >= 10:  # 如果是劍士、弓箭手、盜賊,10 級一轉
        tot += 1 + (level-10)*3  # 點數加上轉職的 1 及每升一級加的 3 點
    if job != 0 and level >= 30: tot += 1  # 如果不是初心者,30 級二轉,點數加 1
    if job != 0 and level >= 70: tot += 1  # 如果不是初心者,70 級三轉,點數加 1
    if job != 0 and level >= 120: tot += 3  # 如果不是初心者,120 級四轉,點數加 3
    result.append(f"{tot:d}\n")
sys.stdout.write("".join(result))


2025年9月3日 星期三

ZeroJudge 解題筆記:d575. 末日審判

作者:王一哲
日期:2025年9月3日


ZeroJudge 題目連結:d575. 末日審判

解題想法


這題看起來很簡單,只要計算兩個點之間的距離是否小於、等於半徑即可,但是用 Python 解題時需要用 sys.stdin.readlines() 及 sys.stdour.write() 加速,否則會超時;用 C++ 解題要使用 long long,否則會溢位。

Python 程式碼


第8筆測資超時。
import sys

for line in sys.stdin:
    x0, y0, x1, y1, r = map(int, line.split())
    if abs(x0-x1) + abs(y0-y1) <= r: print("die")
    else: print("alive")

使用時間約為 2.7 s,記憶體約為 113.6 MB,通過測試。
import sys

lines = sys.stdin.read().splitlines()  # 一次讀取所有資料,減少讀取次數
results = []  # 儲存要輸出的結果
for line in lines:  # 從 lines 依序讀取資料 line
    x0, y0, x1, y1, r = map(int, line.split())  # 用 split 拆開 line,轉成 int,存入變數
    if abs(x0-x1) + abs(y0-y1) <= r: results.append("die\n")  # 先將要輸出的字串加到 results
    else: results.append("alive\n")
sys.stdout.write("".join(results))  # 將 results 合併成一個很長的字串再一次輸出


2025年9月2日 星期二

ZeroJudge 解題筆記:d574. 節約符咒

作者:王一哲
日期:2025年9月2日


ZeroJudge 題目連結:d574. 節約符咒

解題想法


第4筆測資只有一行,用空格分隔數量與字串,用 Python 解題需要特別處理。依序讀取字串中每個字母,計算連續出現的相同字母數量,將數量與對應的字母組成字串。

Python 程式碼


使用時間約為 1.9 s,記憶體約為 21 MB,通過測試。
line = list(input().split())  # 讀取一行資料並用空格分隔存成串列
n = int(line[0])  # 字串長度
if len(line) == 1: s = input().strip()  # 如果 line 只有一項,再讀取一行字串
else: s = line[1]  # 反之,字串在 line[1]
t = ""  # 儲存答案用的空字串
cnt = 1  # 連續相同字母的數量,預設為 1
last = s[0]  # 前一個字母,預設為 s[0]
for c in s[1:]:  # 依序讀取 s[1] ~ s[n-1]
    if c == last: cnt += 1  # 如果 c 等於 last,cnt 加 1
    else:  # 反之,結算之的連續相同字母數量
        t += str(cnt) + last  # cnt 轉成字串加上 last,接到 t 之後
        cnt = 1  # cnt 重置為 1
        last = c  # last 重置為 c
t += str(cnt) + last  # 最後要再結算一次 cnt 與 last
if len(t) < n: print(t)  # 如果 t 較短,印出 t
else: print(s)  # 反之,印出 s


2025年9月1日 星期一

ZeroJudge 解題筆記:d566. 秒殺率

作者:王一哲
日期:2025年9月1日


ZeroJudge 題目連結:d566. 秒殺率

解題想法


這題要注意:
  1. 此處的解題紀錄排在前面的資料代表時間越晚
  2. 第 4 筆測資格式有問題,全部塞在同一行,用 Python 解題需要特別處理這筆測資。


Python 程式碼


理論上這樣寫應該要過關,但是第 4 筆測資格式有問題,全部塞在同一行,要再修改程式碼。
cnt = dict()  # 計數器,是否 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # AC 人數
n = int(input())  # n 筆資料
data = [input().split() for _ in range(n)]  # 先讀完所有的資料
for name, state in data[::-1]:  # 反向讀取資料,先讀取時間較早的資料
    if name not in cnt:  # 如果 name 不在 cnt 之中
        if state == "AC":  # 如果第一次就 AC
            fir += 1  # fir 加 1
            ac += 1  # ac 加 1
            cnt[name] = True  # cnt[name] 為 True
        else:  # 第一次沒有 AC
            cnt[name] = False  # cnt[name] 為 False
    elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過,而且這次過了
        ac += 1  # ac 加 1
        cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

使用時間約為 45 ms,記憶體約為 6.2 MB,通過測試。
import sys

cnt = dict()  # 計數器,是否第一次就 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # 全部 AC 的人數
for line in sys.stdin:  # 讀資料直到 EOF 為止
    data = line.split()  # 先試著分割資料
    if len(data) == 1:  # 如果只有一筆,是 n
        n = int(data[0])
        data = [input().split() for _ in range(n)]  # 先讀完所有的資料
        for name, state in data[::-1]:  # 反向讀取資料,先讀取時間較早的資料
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過,而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
    else:  # 為了測資 4 全部塞在一行的狀況
        n = int(data[0])
        for i in range(2*n, 0, -2):  # 反向讀取資料,先讀取時間較早的資料
            name, state = data[i-1], data[i]
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過,而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")