ZeroJudge 解題筆記：e796. p3. 站牌廣告

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



ZeroJudge 題目連結：e796. p3. 站牌廣告

解題想法

因為測資範圍不太，在找人流最大值、最小值的站牌編號用線性搜尋，從頭到尾掃過一次即可，效率並不差。

Python 程式碼

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

B = int(input())  # 站牌數量，站牌編號 1 ~ B
P = int(input())  # 人數
cnt = [0]*(B+1)  # 各站牌人流，左端加上一格
for _ in range(P):  # 讀取 P 行資料
    u, v = map(int, input().split())  # 上車、下車站牌編號
    if u > v: u, v = v, u  # 如果 u 大於 v，兩者交換
    for i in range(u, v+1): cnt[i] += 1  # 更新 [u, v] 之間的人流
imax, imin = 0, P+1  # 人流最大值、最小值
pmax, pmin = 0, 0  # 人流最大值、最小值的站牌編號
for i in range(1, B+1):  # 依序檢查站牌 1 ~ B
    if cnt[i] >= imax:  # 如果 cnt[i] 大於等於 imax
        imax = cnt[i]  # 更新 imax
        pmax = i  # 更新 pmax
    if cnt[i] < imin:  # 如果 cnt[i] 小於 imin
        imin = cnt[i]  # 更新 imin
        pmin = i  # 更新 pmin
print(f"{pmin:d} {pmax:d}")  # 印出答案

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

克希荷夫定律與矩陣運算

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

原理

當電路上只有電池與電阻器，但又不是單純的串聯、並聯電路時，可以利用克希荷夫定律 (Kirchhoff's circuit laws) 求所有的分支電流。克希荷夫定律有兩個定則

1. 節點定則：對於電路上的某個節點而言，流入、流出的電流量值相等，實際上就是電荷守恆。
2. 迴路定則：對於電路上的某個迴路而言，繞一圈回到出發點時電位相等，實際上就是能量守恆。

下圖是 WikiPedia 克希荷夫定律英文版條目的例子

圖片來源：https://upload.wikimedia.org/wikipedia/commons/7/77/Kirshhoff-example.svg

由圖中右方的節點可得 $$ i_1 = i_2 + i_3 $$ 由上方的迴路可得 $$ \varepsilon_1 - i_1 R_1 - i_2 R_2 = 0 $$ 由下方的迴路可得 $$ -i_3 R_3 - \varepsilon_2 - \varepsilon_1 + i_2 R_2 = 0 $$ 整理以上3式可得 $$ \begin{cases} i_1 - i_2 - i_3 = 0 \\ i_1 R_1 - i_2 R_2 = \varepsilon_1 \\ i_2 R_2 - i_3 R_3 = \varepsilon_1 + \varepsilon_2 \end{cases} ~\Rightarrow~ \begin{cases} 1 \cdot i_1 + (-1) \cdot i_2 + (-1) \cdot i_3 = 0 \\ R_1 \cdot i_1 + (-R_2) \cdot i_2 + 0 \cdot i_3 = \varepsilon_1 \\ 0 \cdot i_1 + R_2 \cdot i_2 + (-R_3) \cdot i_3 = \varepsilon_1 + \varepsilon_2 \end{cases} $$ 如果轉換成矩陣型式 $$ \begin{bmatrix} 1 & -1 & -1 \\ R_1 & R_2 & 0 \\ 0 & R_2 & -R_3 \end{bmatrix} \begin{bmatrix} i_1 \\ i_2 \\ i_3 \end{bmatrix} = \begin{bmatrix} 0 \\ \varepsilon_1 \\ \varepsilon_1 + \varepsilon_2 \end{bmatrix} $$ 假設代入的數值分別為 $$ R_1 = 100 ~\mathrm{\Omega},~ R_2 = 200 ~\mathrm{\Omega},~ R_3 = 300 ~\mathrm{\Omega},~ \varepsilon_1 = 3 ~\mathrm{V},~ \varepsilon_2 = 4 ~\mathrm{V} $$ 電流分別為 $$ i_1 = \frac{1}{1100} ~\mathrm{A},~ i_2 = \frac{4}{275}~\mathrm{A},~ i_3 = -\frac{3}{220} ~\mathrm{A} $$

使用 Python 及 C++ 計算矩陣乘法、反矩陣

作者：王一哲
日期：2024年7月7日

前言

矩陣乘法及反矩陣的運算會出現在高中數學教材之中，同時也可以運用在物理課程之中，例如克希荷夫定律求分支電流。我之前都是直接用 NumPy 處理，為了更了解運算的過程，我再花了一些時間研究不使用 NumPy 的寫法。

矩陣乘法

運算原則

矩陣橫的部分為列 (row)、直的部分為欄 (column)，如果某個矩陣共有 $m$ 列、$n$ 欄，則這個矩陣的維度 (dimension) 為 $m \times n$。假設 $A$ 矩陣的維度為 $m \times n$，$B$ 矩陣的維度為 $n \times p$，則兩個矩陣相乘 $AB$ 的維度為 $m \times p$。如果兩個矩陣要相乘，第一個矩陣的欄與第二個矩陣的列數量必須相等。需要特別注意，矩陣乘法沒有交換性。 假設矩陣 $$ A = \begin{bmatrix} a_{0, 0} & a_{0, 1} & a_{0, 2} & \dots \\ a_{1, 0} & a_{1, 1} & a_{1, 2} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} A_1 & A_2 & \dots \end{bmatrix} $$ $$ B = \begin{bmatrix} b_{0, 0} & b_{0, 1} & b_{0, 2} & \dots \\ b_{1, 0} & b_{1, 1} & b_{1, 2} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} B_1 \\ B_2 \\ \vdots \end{bmatrix} $$ 相乘的結果 $$ AB = \begin{bmatrix} a_{0, 0} b_{0, 0} + a_{0, 1} b_{1, 0} + \dots & a_{0, 0} b_{0, 1} + a_{0, 1} b_{1, 1} + \dots & \dots \\ a_{1, 0} b_{0, 0} + a_{1, 1} b_{1, 0} + \dots & a_{1, 0} b_{1, 1} + a_{0, 1} b_{1, 1} + \dots & \dots \\ \vdots & \vdots & \ddots \end{bmatrix} = A_1 B_1 + A_2 B_2 + \dots $$

遞迴樹 Recursive Tree

定義

先由下往上畫出樹幹，如果深度為0時只有樹幹；如果深度加1，在樹幹頂端增加2根互相垂直的分枝，分枝的長度比樹幹短，以下的程式中設定為0.6倍。我原來是用 tkinter 寫的，但它的畫面原點在左上角，向右為 +x 軸、向下為 +y 軸，跟我平常慣用的座標不太一樣。今天晚上再改用 VPython 重寫，並發布在 GlowScript 網站上，網頁版連結在此。