ZeroJudge 解題筆記：e795. p2.質數日

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



ZeroJudge 題目連結：e795. p2.質數日

解題想法

因為測資範圍不太，在判斷數字 $n$ 是否為質數時，只要用 for 迴圈從 2 開始測試到 $\sqrt{n}$，任何一個數可以整除 $n$ 則 $n$ 不是質數，不需要用太複雜的作法。

Python 程式碼

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

def test(s):  # 輸入日期 s，字串格式，測試其是否為質數日
    while len(s) >= 1 and int(s) >= 2:  # 如果 s 長度大於等於 1，轉成整數大於等於 2，繼續執行
        date = int(s)  # s 轉成 int
        imax = int(date**0.5)  # 測試的上限，date 開根號
        for i in range(2, imax+1):  # 依序測試 2 ~ imax 是否能整除 date
            if date%i == 0: return False  # 如果能整除，回傳 Fasle 並跳出函式
        s = s[1:]  # 刪除 s 開頭的字元
    return True  # 如果能跑完 while 迴圈，s 是質數日，回傳 True

D = int(input())  # D 個日期
for _ in range(D):  # 測試 D 次
    N = input().strip()  # 讀取日期 N
    print(N, end=" ")  # 印出答案
    print("is" if test(N) else "isn't", end="")
    print(" a Prime Day!")

ZeroJudge 解題筆記：e623. 2. PPAP

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



ZeroJudge 題目連結：e623. 2. PPAP

解題想法

這題看起來好像不難，但是編號很容易算錯，尤其是某一輪或是某一組的最後一項。

Python 程式碼

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

n = int(input())  # 編號
m = 0  # 第 m 輪
s = 0  # 第 m 輪的數量，每次加 4
while n >= s+4:  # 如果 n 的數量大於等於 s+4，還有下一輸，繼續執行
    m += 1; s += 4  # m 加 1；s 加 4
    n -= s  # n 減去 s
if n == 0:  # 剛好是第 m 輪的最後一個人
    print("Pineapple pen")  # 印出 Pineapple pen
else:  # 要再到下一輪
    m += 1  # m 加 1
    if n%m == 0: n -= 1  # 如果 n 可以被 m 整除，剛好是某一項物品的最後一個，n 要減 1
    item = n // m  # 物品編號，取 n 除以 m 的整數部分
    if item == 0: print("Pen")  # 印出對應的物品名稱
    elif item == 1: print("Pineapple")
    elif item == 2: print("Apple")
    else: print("Pineapple pen")

ZeroJudge 解題筆記：e622. 3. 虛擬寵物大師 (Master)

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



ZeroJudge 題目連結：e622. 3. 虛擬寵物大師 (Master)

解題想法

這題是迴圈的練習題，將 IV 值對應的 CP 值、升級後的 CP 值另外寫成函式，這樣程式碼比較好看。

Python 程式碼

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

# 輸入 iv 值，回傳升級時增加的 cp 值
def ivcp(iv):
    if 0 <= iv <= 29: return 10
    elif 30 <= iv <=39: return 50
    else: return 100

# 輸入原有的星塵沙子數量 star，iv 值、原來的 cp 值，計算升級後的 cp 值
def upgrade(star, iv, cp):
    while star >= 1000:
        star -= 1000
        cp += ivcp(iv)
    return cp

# 解題過程
n, s = map(int, input().split())  # 寵物數量 n，原有的星塵沙子數量 s
imax, idx = 0, 0  # 升級後最高的 cp 值及寵物編號
for i in range(1, n+1):  # 讀取 n 行資料
    c, v = map(int, input().split())  # 讀取原來的 cp 值、iv 值
    re = upgrade(s, v, c)  # 呼叫 upgrade，代入 s, v, c，計算升級後的 cp 值
    if re > imax:  # 如果 re 大於 imax
        imax = re  # 更新 imax
        idx = i  # 更新 idx
print(f"{idx:d} {imax:d}")  # 印出答案

ZeroJudge 解題筆記：e621. 1. 免費停車 (Free Parking)

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



ZeroJudge 題目連結：e621. 1. 免費停車 (Free Parking)

解題想法

這題是很單純的算數題，跑 for 迴圈除一下就好了。

Python 程式碼

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

import sys

for line in sys.stdin:
    N = int(line)
    for _ in range(N):
        A, B, C = map(int, input().split())
        ans = []
        for i in range(A+1, B):
            if i%C != 0: ans.append(i)
        if ans: print(*ans)
        else: print("No free parking spaces.")

ZeroJudge 解題筆記：a445. 新手訓練系列- 我的朋友很少

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



ZeroJudge 題目連結：a445. 新手訓練系列- 我的朋友很少

解題想法

先用鄰接串列儲存節點之間的連接方式，注意，這題是無向圖，而且測資中某些行可能 兩個一樣的數字，因為不能自己連到自己，要記得排除。
由於題目要問 A 和 B 是否為朋友，只要 A、B 能夠相連就是朋友，理論上可以用 BFS 從 A 開始測試，如果能夠走到 B，兩人就是朋友。但這題要測試很多次，比較有效率的作法是利用併查集及路徑壓縮，先將每個點的父節點都設定成自己，再用 BFS 或是遞迴，從某一個點 n 開始，將所有與 n 相連的點其父節點都設定成 n，檢測時只要看這兩個點的父節點是否相同，就可以知道兩個點是否相連。

Python 程式碼

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

from collections import deque

def rfind(n, r):  # 自訂函式，輸入節點 n，根節點 r，路徑壓縮
    que = deque([n])  # 待走訪佇列，先放入 n
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 最前面讀取並移除資料
        for v in adj[u]:  # 依序讀取與 u 相連的節點 v
            if parent[v] == v:  # 如果 v 還沒有找到父節點
                parent[v] = r  # 將 v 的父節點設定成 r
                que.append(v)  # 將 v 加入 que
# 讀取資料
N, M, Q = map(int, input().split())  # N 個人，M 筆朋友關係，Q 筆詢問
adj = [[] for _ in range(N+1)]  # 人之間的關係，無向圖，人的編號為 1 ~ N
for _ in range(M):  # 讀取 M 行資料
    A, B = map(int, input().split())  # A 和 B 有朋友關係
    if A == B: continue  # 如果 A、B 是同一個人，找下一筆資料
    adj[A].append(B)
    adj[B].append(A)
# 找每個節點的父節點
parent = list(i for i in range(N+1))  # 每個節點的父節點，先設定成自己的編號
for i in range(1, N+1):  # 依序掃過 1 ~ N 號
    if parent[i] == i and adj[i]:  # 如果 i 還沒有找到父節點而且 i 有相連的點
        rfind(i, i)  # 呼叫 rfind，將與 i 相連的點其父節點都設定成 i
# Q 行待測資料
for _ in range(Q):
    A, B = map(int, input().split())  # 要測試的 A 和 B
    print(":)" if parent[A] == parent[B] else ":(")

ZeroJudge 解題筆記：a290. 新手訓練系列 ~ 圖論

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



ZeroJudge 題目連結：a290. 新手訓練系列 ~ 圖論

解題想法

先用鄰接串列儲存節點之間的連接方式，注意，這題是有向圖。由於題目要問城市 A 是否能走到城市 B，用 BFS 從 A 開始測試，如果能夠走到 B，就可以跳出 BFS 並且印出 Yes!!!，如果跑完 BFS 還是沒有走到 B 就印出 No!!!。

Python 程式碼

這題的測資大到 Python 連用 BFS 都過不了。

import sys
from collections import deque

for line in sys.stdin:
    N, M = map(int, line.split())  # N 個城市，M 條道路
    adj = [[] for _ in range(N+1)]  # 有向圖
    for _ in range(M):  # 讀取 M 行資料
        a, b = map(int, input().split())  # 城市 a、b
        adj[a].append(b)  # a 可以走到 b
    A, B = map(int, input().split())  # 起點A、終點 B
    que = deque([A])  # 待走訪佇列，先放入 A
    flag = False  # 是否能走到終點，假設為 False
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 最前面讀取並移除資料
        if u == B:  # 可以走到終點
            flag = True  # flag 設定為 True
            break  # 中止 while 迴圈
        for v in adj[u]: que.append(v)  # 將 u 可以走到的點都加入 que
    print("Yes!!!" if flag else "No!!!")  # 印出答案