ZeroJudge 解題筆記：k853. P7.直播趕場 (Live)

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



ZeroJudge 題目連結：k853. P7.直播趕場 (Live)

解題想法

採用類似〈APCS實作題2016年3月第3題：線段覆蓋長度〉計算重疊線段厚度的寫法，讀到開始直播時刻厚度加 1，讀到直播結束時刻厚度減 1；假設目前檢查的時間端點為 [start, end+1]，若厚度小於等於螢幕數量，可以觀看的時數加上厚度乘以端點距離，若厚度大於螢幕數量，可以觀看的時數加上螢幕數量乘以端點距離。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, s = map(int, line.split())  # n 個螢幕，s 個直播
    cast = []  # 直播開始、結束時刻，開始厚度加 1，結束厚度減 1
    for _ in range(s):  # 讀取 s 行資料
        start, end = map(int, input().split())
        cast += [(start, 1), (end+1, -1)]  # 結束時刻要加 1
    cast.sort()  # 排序
    last = 0  # 正在檢查的範圍開始時刻
    thick = 0  # 厚度，正在直播的頻道數量
    ans = 0  # 答案，可以觀看的直播總時數
    for p, t in cast:  # 依序讀取時刻及厚度變化
        if thick > 0:  # 如果目前直播頻道數量大於 0
            ans += min(thick, n)*(p-last)  # 更新 ans，加上 thick, n 較小值乘以 p-last
        thick += t  # 更新厚度
        last = p  # 更新 last
    print(ans)

ZeroJudge 解題筆記：k851. P5.辨識碼 (Identification)

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



ZeroJudge 題目連結：k851. P5.辨識碼 (Identification)

解題想法

我是用字串分割的方式，按照題目要求的長度分割字串，將每個子字串的數字加總存入集合 isum 之中，如果 isum 之中已經有同樣的值就是國民，不需要再檢查後面的子字串。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)  # 分組數字 x 個
    n = sys.stdin.readline().strip()  # 身分證號
    m = len(n)  # 長度
    isum = set()  # 各組的加總
    flag = False  # 是否為國民，預設為 False
    for i in range(m-x, -1, -x):  # 從最後往前取長度為 x 的子字串
        s = n[i:i+x]  # 子字串
        tot = sum([int(c) for c in s])  # 加總
        if tot in isum:  # 如果 isum 之中已經有 tot
            flag = True; break  # 是國民，中止迴圈
        isum.add(tot)  # tot 加入 isum
    print("Yes" if flag else "No")  # 印出答案

ZeroJudge 解題筆記：k849. P3.骨牌 (Domino)

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



ZeroJudge 題目連結：k849. P3.骨牌 (Domino)

解題想法

這題是有向圖，我用集合 child 儲存子節點編號，用字典 nxt 儲存每個節點的子節點編號，讀取 n 行資料存入 child 及 nxt，再掃瞄一輪找出根節點（第一張牌），最後用一個 while 迴圈第根節點開始掃過所有的節點並將節點編號存入串列 ans。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 組資料，n 張牌
    child = set()  # 不是第一張牌的編號
    nxt = dict()  # 下一張牌的編號
    for _ in range(n):  # 讀取 n 行資料，u 的下一張是 v
        u, v = map(int, input().split())
        child.add(v)
        nxt[u] = v
    start = 0  # 第一張牌
    for u in nxt.keys():  # 從 nxt 的 keys 之中找第一張牌
        if u not in child:  # 只有一個 u 不在 child 之中
            start = u; break  # 找到就可以中止迴圈
    ans = [start]  # 先將 start 加入 ans
    while nxt[ans[-1]] != -1:  # 如果 ans 最後一項的下一張不是 -1 繼續執行
        ans.append(nxt[ans[-1]])  # 將找到的牌加入 ans
    print(*ans)

ZeroJudge 解題筆記：k848. P2.卡牌評分 (Card)

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



ZeroJudge 題目連結：k848. P2.卡牌評分 (Card)

解題想法

分成兩個部分，先掃過全部的卡牌資料並找最大值，再掃一輪計算每張牌的積分。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 張卡牌
    S, A, D, H = [0]*n, [0]*n, [0]*n, [0]*n  # 積分，攻擊力，防禦力，生命力
    amax, dmax, hmax = 0, 0, 0  # 最高攻擊力，最高防禦力，最高生命力
    for i in range(n):  # 讀取 n 張牌的資料並找最大值
        a, d, h = map(int, input().split())
        A[i] = a; amax = max(amax, a)
        D[i] = d; dmax = max(dmax, d)
        H[i] = h; hmax = max(hmax, h)
    for i in range(n):  # 計算每張牌的積分
        if A[i] == amax: S[i] += 1
        if D[i] == dmax: S[i] += 1
        if H[i] == hmax: S[i] += 1
    print(S.index(max(S)) + 1)  # 印出最高積分卡牌編號

ZeroJudge 解題筆記：k847. P1.租車費用 (Rent)

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



ZeroJudge 題目連結：k847. P1.租車費用 (Rent)

解題想法

按照題目的計費規則寫就行了，先算租車天數，分成每租滿 10 天以及未滿 10 天兩個部分計費。

Python 程式碼

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

import sys

month = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = sum(month[m1: m2]) - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)

月份的天數改成前綴和，如果輸入的月份是 $m1, m2$，要算計算 $m2-1$ 到 $m1$ 月份的天數 $psum[m2-1] - psum[m1-1]$。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

import sys

psum = (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = psum[m2-1] - psum[m1-1] - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)

ZeroJudge 解題筆記：k520. P8.幸運基數 (Base)

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



ZeroJudge 題目連結：k520. P8.幸運基數 (Base)

解題想法

我在這題卡了很久，一直想不出比較有效率的寫法。由題目的敘述可知，如果要把10進位制的數字 $n$ 換成 $k$ 進位制表示，而且轉換後每個位數都是 $1$，一定會有的解是 $k = n-1$，轉換後為 $11$，如果 $k$ 越小，轉換後的位數越多。我有試著把 $3 \leq n \leq 1000$ 之中 $k \neq n-1$ 的數字列出來，但看不出規律。

(7, 2), (13, 3), (15, 2), (21, 4), (31, 2), (31, 5), (40, 3), (43, 6), (57, 7), (63, 2),
(73, 8), (85, 4), (91, 9), (111, 10), (121, 3), (127, 2), (133, 11), (156, 5), (157, 12), (183, 13), 
(211, 14), (241, 15), (255, 2), (259, 6), (273, 16), (307, 17), (341, 4), (343, 18), (364, 3), (381, 19),
(400, 7), (421, 20), (463, 21), (507, 22), (511, 2), (553, 23), (585, 8), (601, 24), (651, 25), (703, 26),
(757, 27), (781, 5), (813, 28), (820, 9), (871, 29), (931, 30), (993, 31)

後來想到，如果 $k$ 越小，轉換後的位數越多，那就先算出 2 進位制的位數，然後位置依序遞減到 2 為止，每次再用二分搜尋法，在 $low = 2, high = n-1$ 之間找解，雖然有很多次不必要的計算，但至少能正確地找到答案。

Python 程式碼

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

import sys, math

# 檢查以 base 為底，在指定位數 digit 的值與 num 的大小關係
def check(num, base, digit):
    power, total = 1, 0  # 目前的次方，加總
    for i in range(digit):  # 從個位數開始往左計算 
        total += power  # 更新 total
        power *= base  # 更新 power 為 base**(i+1)
        if total > num: return 1  # 如果 total 大於 num，回傳 1，跳出函式
    if total == num: return 0  # 如果最後 total 等於 num，回傳 0
    return -1  # 否則回傳 -1

for line in sys.stdin:
    n = int(line)  # 要找基底的數字 n
    ans = n-1  # 答案預設為 n-1
    digitmax = math.ceil(math.log(n, 2))  # 最多的位數
    for digit in range(digitmax, 1, -1):  # 依序檢查最多位數到 2 位數
        low, high = 2, n-1  # 下限 2，上限 n-1
        while low <= high:  # 當 low 小於等於 high，繼續執行
            mid = (high - low)//2 + low  # 取中間值
            state = check(n, mid, digit)  # 呼叫 check 檢查大小關係
            if state == 0:  # 找到解，更新 ans 為較小的值，降低 high
                ans = min(ans, mid); high = mid-1
            elif state == 1: high = mid-1 # mid 太大，降低 hight
            else: low = mid+1  # mid 太小，提高 low
    print(ans)  # 印出答案

ZeroJudge 解題筆記：k519. P7.機票 (Ticket)

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



ZeroJudge 題目連結：k519. P7.機票 (Ticket)

解題想法

這題考 Floyd-Warshall 演算法。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個城市
    graph = [list(map(int, input().split())) for _ in range(n)]  # 讀取城市之前移動費用
    start, end = map(int, input().split())  # 起點、終點
    start -=1; end -= 1  # 配合索引值減 1
    for k in range(n):  # 以 k 為轉機地點
        for i in range(n):  # 以 i 為起點
            for j in range(n):  # 以 j 為終點
                if graph[i][k] == -1 or graph[k][j] == -1: continue  # k 等於 i 或 j，找下一組
                if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j] - 50:  # 如果 i 等於 j 或 i->j 成本大於 i->k->j -50
                    graph[i][j] = graph[i][k] + graph[k][j] - 50
    print(graph[start][end])  # 印出答案

ZeroJudge 解題筆記：k518. P6.蛋糕切塊 (Cake)

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



ZeroJudge 題目連結：k518. P6.蛋糕切塊 (Cake)

解題想法

這題考動態規畫，我同時利用 set 儲存可用的子字串，這樣程式運作速度會比較快。

Python 程式碼

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

import sys

def can_cut_cake(s, cuts):
    n = len(s)  # 字串長度
    dp = [False]*(n+1)  # 是否能走到 i，如果能走到 i+1 代表有解
    dp[0] = True  # 一定能走到開頭
    # 動態規劃遍歷
    for i in range(1, n+1):  # 依序找終點 i = 1 ~ n
        for j in range(i):  # 依序找起點 j = 0 ~ i-1
            if dp[j] and s[j:i] in cuts:  # 如果能走到 j 而且 s[j:i] 在 cuts 之中
                dp[i] = True  # 可以走到 i
                break  # 只要找到一個可行切割後就可以停止
    print("yes" if dp[n] else "no")  # 如果 dp[n] 為 True 印出 yes，反之印出 no

for s in sys.stdin:
    s = s.strip()  # 要檢查的字串
    m = int(input())  # 可用的子字串數量
    cuts = set()  # 可用的子字串
    for _ in range(m): cuts.add(input())  
    can_cut_cake(s, cuts)  # 計算並輸出結果

ZeroJudge 解題筆記：k517. P5.波動 (Wave)

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



ZeroJudge 題目連結：k517. P5.波動 (Wave)

解題想法

因為這題需要將所有的波依照傳播的時間由小到大排序，如果時間相同再依照方向 W、S、E、N 排序。如果將時間、方向組成 Python 的 tuple 或是 C++ 的 pair 再排序，但由於 W、S、E、N 不是依照字典順序，不能這樣處理。所以我先將 W、S、E、N 換成對應的數字 0、1、2、3，與時間組成 tuple 再排序，輸出結果時再將數字換回 W、S、E、N。在 C++ 則是自訂結構體，再用 lambda function 自訂排序規則。

Python 程式碼

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

import sys

c2n = {'W': 0, 'S': 1, 'E': 2, 'N': 3}
n2c = ('W', 'S', 'E', 'N')
for line in sys.stdin:
    p = int(line)  # p 道波動
    wave = []  # 傳播時間，波源方位
    for _ in range(p):  # 執行 p 次
        c, d, v = input().split()  # 波源方位，距離，波速
        d = int(d); v = int(v)  # 轉成 int
        wave.append((d/v, c2n[c]))  # (d/v, c2n[c]) 加入 wave
    wave.sort()  # 依照 (t, 方向) 由小到大排序
    print("".join([n2c[n] for _, n in wave]))  # 由 wave 取出 n，換成對應的字母，接成字串，印出

ZeroJudge 解題筆記：k516. P4.根號 (Sqrt)

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



ZeroJudge 題目連結：k516. P4.根號 (Sqrt)

解題想法

畫圖形的題目，關鍵在於找到各部位畫圖的規則。

Python 程式碼

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

import sys

for line in sys.stdin:
    k = int(line.strip())  # 短邊長度
    a, b = (k-1)//2 - 1, 2*k-1  # 左斜線、長邊長度
    n, h = k+a+k+b, k//2  # 全長，短邊於第 h 列
    grid = [[" "]*n for _ in range(k)]  # 圖形，預設為空白
    for i in range(k): grid[h][i] = "*"  # 短邊
    for i in range(a): grid[h+1+i][k+i] = "*"  # 左斜線
    for i in range(k): grid[k-1-i][k+a+i] = "*"  # 右斜線
    for i in range(2*k-1): grid[0][k+a+k+i] = "*"  # 長邊
    for i in range(k): print("".join(grid[i]))  # 印出圖形