熱門文章

2025年10月21日 星期二

ZeroJudge 解題筆記:f716. 計算學期成績

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


ZeroJudge 題目連結:f716. 計算學期成績

解題想法


換算的公式為 $$ y = 45 \times \frac{x-a}{b} + 55 $$ 假設原始成績最高分為 $imax$、最低分為 $imin$,換算後成績最高分為 $100$、最低分為 $55$,代入上式可得 $$ 100 = 45 \times \frac{imax-a}{b} + 55 ~~~~~ 55 = 45 \times \frac{imin-a}{b} + 55 $$ 由以上2式可得 $$ b = imax - a ~~~~~ a = imin $$

Python 程式碼


使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
scores = tuple(map(int, input().split()))
a = min(scores)
b = max(scores) - a
print(a, b)


C++ 程式碼


使用時間約為 2 ms,記憶體約為 92 kB,通過測試。2025年10月15日重測,使用時間約為 0 ms,記憶體約為 48 kB,通過測試。
#include <cstdio>

int main() {
    int imin = 1E9, imax = 0, score;
    while(scanf("%d", &score) != EOF) {
        if (score < imin) imin = score;
        if (score > imax) imax = score;
    }
    printf("%d %d\n", imin, imax - imin);
    return 0;
}


2025年10月20日 星期一

ZeroJudge 解題筆記:f701. 連接字詞

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


ZeroJudge 題目連結:f701. 連接字詞

解題想法


這題沒有說明要讀取的單字數量,用 C++ 寫起來會比較麻煩,用 getline 搭配 stringstream 及 vector 會比較方便。

Python 程式碼


以前測試時使用時間約為 19 ms,記憶體約為 3.3 MB。ZeroJudge 網站好像在 2025年10月更新過,同樣的程式碼使用時間約為 6 ms,記憶體約為 3 MB。
words = list(input().split())
conjuction = input()
n = len(words)
for i in range(n-1):
    print(f"{words[i]:s} {conjuction:s} ", end="")
print(words[-1])

可以用 join 將 " 連接詞 " 與串列 words 的內容接成一個字串再輸出,使用時間約為 7 ms,記憶體約為 3 MB,通過測試。
words = list(input().split())
conjuction = input()
print(f" {conjuction} ".join(words))


2025年10月19日 星期日

ZeroJudge 解題筆記:f699. 品嘉的茶葉蛋

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


ZeroJudge 題目連結:f699. 品嘉的茶葉蛋

解題想法


標準的 BFS 題目。因為不想檢查是否出界,我在地圖周圍加上 2 作為哨兵。另外開一個陣列儲存步數。

Python 程式碼


使用時間約為 55 ms,記憶體約為 4 MB,通過測試。
from collections import deque

n, m = map(int, input().split())  # 地圖 n*m,最右側、最下方加上 2 作為哨兵
grid = [list(map(int, input().split())) + [2] for _ in range(n)]
grid.append([2]*(m+1))  # 最下方加 m+1 個 2
steps = [[0]*m for _ in range(n)]  # 記錄步數用的二維串列
ans = []  # 答案
que = deque([(0, 0)])  # 待走訪佇列
grid[0][0] = 2  # (0, 0) 設定為 2
while que:  # 如果 que 還有資料繼續執行
    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
        if grid[nr][nc] == 2: continue  # 如果此格是 2 找下一格
        steps[nr][nc] = steps[r][c] + 1  # (nr, nc) 的步數為 (r, c) 的步數加 1
        if grid[nr][nc] == 1: ans.append(steps[nr][nc])  # 如果此格是 1,將 (nr, nc) 的步數加入 ans
        grid[nr][nc] = 2  # 此格設定為 2
        que.append((nr, nc))  # (nr, nc) 加入 que
if not ans: print("嘉油!")  # 沒有找到茶葉蛋
else:  # 有找到茶葉蛋,印出 ans 的內容
    for a in ans: print(a)


2025年10月18日 星期六

ZeroJudge 解題筆記:f680. 色塊數量

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


ZeroJudge 題目連結:f680. 色塊數量

解題想法


標準的 BFS 題目。

Python 程式碼


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

n = int(input())  # 地圖 n*n,最右側、最下方加上 0 作為哨兵
grid = [list(map(int, input().split())) + [0] for _ in range(n)]
grid.append([0]*(n+1))
### BFS ###
cnt = 0  # 色塊數量
for i in range(n):  # 依序掃過每一格
    for j in range(n):
        if grid[i][j] == 0: continue  # 如果此格是 0 找下一格
        color = grid[i][j]  # 此格的顏色
        grid[i][j] = 0  # 此格設定為 0
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列
        cnt += 1  # 色塊數量加 1
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭讀取並移除資料
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                if grid[nr][nc] != color: continue  # 如果此格顏色不一樣,找下一格
                grid[nr][nc] = 0  # 此格設定為 0
                que.append((nr, nc))  # (nr, nr) 加入待走訪佇列
### End of BFS ###
print(cnt)  # 印出答案


2025年10月17日 星期五

ZeroJudge 解題筆記:f647. 撲克牌

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


ZeroJudge 題目連結:f647. 撲克牌

解題想法


我用串列儲存牌組,先用 for 迴圈産生按照花色、數字排列好的 52 張牌,接下來依照指令用串列切片修改內容。

Python 程式碼


使用時間約為 0.4 s,記憶體約為 3.4 MB,通過測試。
deck = [""]*52
suits = ('S', 'H', 'D', 'F')
akqj = {1: 'A', 13: 'K', 12: 'Q', 11: 'J'}
for i in range(4):
    for j in range(1, 14):
        if 2 <= j <= 10: deck[i*13 +j-1] = suits[i] + str(j)
        else: deck[i*13 + j-1] = suits[i] + akqj[j]
n = int(input())
for _ in range(n):
    line = input().split()
    if line[0] == '1':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[a:b+1] + deck[:a] + deck[b+1:]
    elif line[0] == '2':
        a, b = int(line[1])-1, int(line[2])-1
        deck = deck[:a] + deck[b+1:] + deck[a:b+1]
    elif line[0] == '3':
        k = int(line[1])
        deck = deck[52-k:] + deck[:52-k]
    else:
        k = int(line[1])
        deck = deck[k:] + deck[:k]
print(*deck[:5])


2025年10月16日 星期四

ZeroJudge 解題筆記:f634. 士兵歸來

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


ZeroJudge 題目連結:f634. 士兵歸來

解題想法


我用集合 uni 儲存存活者的姓名、軍種、階級,再用另外兩個陣列 services、ranks 儲存各軍種、階級存活者的數量,用 cnt 儲存存活者總數。讀取 m 行資料之後,再依照題目要求的格式輸出答案。

Python 程式碼


使用時間約為 3.9 s,記憶體約為 114.5 MB,通過測試。
n, m = map(int, input().split())  # 共派出 n 人,有 m 行資料
uni = set()  # (姓名 name, 軍種 service, 階級 rank)
services = [0]*4  # 海、陸、空軍存活人數,開頭有用不到的 0
ranks = [0]*4  # 軍官、士官、士兵存活人數,開頭有用不到的 0
cnt = 0  # 存活人數
for _ in range(m):  # 執行 m 次
    data = tuple(input().split())
    if data not in uni:  # 這筆資料組合不在 uni 之中,新的存活者
        uni.add(data)  # data 加入 uni
        cnt += 1  # 存活人數加 1
        services[int(data[1])] += 1  # 對應的軍種人數加 1
        ranks[int(data[2])] += 1  # 對應的階級人數加 1
print(f"navy:{services[1]:d} army:{services[2]:d} air:{services[3]:d}")
print(f"officer:{ranks[1]:d} sergeant:{ranks[2]:d} soldier:{ranks[3]:d}")
print(f"survival rate: {100.0*cnt/n:.1f}%")


2025年10月15日 星期三

ZeroJudge 解題筆記:f632. 渡船頭

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


ZeroJudge 題目連結:f632. 渡船頭

解題想法


先讀取所有的乘客資料,在結束營業之前到的人才加入串列 passenger 之中,接下來依照時間由小到大排序。另外開一個最大優先佇列,儲存目前乘客會給的小費。再用一個 for 迴圈依序産生出發時刻,讀取當時已到站的乘客資料,將乘客會給的小費存入 pq 之中;再從 pq 取出資料加到利潤 profit 之中,直到 pq 沒有資料或是這趟人數到達上限為止。

Python 程式碼


使用時間約為 0.5 s,記憶體約為 20.9 MB,通過測試。
import sys, heapq

t1, t2, k, p = map(int, sys.stdin.readline().split())  # 營業時間,間距,每趟人數
passenger = []  # 乘客到站時間、小費
for line in sys.stdin:  # 讀取資料直到 EOF 為止
    if line.strip() == "": continue  # 如果讀到空行,找下一行
    t, m = map(int, line.split())  # 這個乘客的到站時間、小費
    if t <= t2: passenger.append((t, m))  # 在結束營業之前到的人才加入
passenger.sort()  # 依照時間排序
tot, profit, idx, n = 0, 0, 0, len(passenger)  # 總載客人數,總收入,從 passenger 讀資料的索引值,人數
pq = []  # 存入目前乘客小費的優先佇列
for dep in range(t1, t2+1, k):  # 依序産生出發時刻
    while idx < n:  # 如果 idx 還沒有出界繼續執行
        t, m = passenger[idx]  # 到站時間、小費
        if t <= dep: heapq.heappush(pq, -m)  # 如果 t 小於等於發車時刻,m 加負號再加入 pq
        else: break  # 否則中止迴圈
        idx += 1  # idx 加 1
    cnt = 0  # 這趟已載人數
    while pq and cnt < p:  # 如果 pq 還有資料而且還沒有載滿
        profit += -heapq.heappop(pq)  # 從 pq 讀取並移除首項,轉為正值加到 profit
        cnt += 1; tot += 1  # 更新人數
print(tot, profit)  # 印出答案


2025年10月14日 星期二

ZeroJudge 解題筆記:f631. 同學會

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


ZeroJudge 題目連結:f631. 同學會

解題想法


這題要用最大優先佇列儲存每個人目前有的錢,由於 Python 的 heapq 是最小優先佇列,要將每一筆資料都加上負號。

Python 程式碼


使用時間約為 2.4 s,記憶體約為 8.1 MB,通過測試。
import sys, heapq

for line in sys.stdin:  # 繼續執行直到 EOF 為止
    if line.strip() == "": continue  # 遇到空行,找下一行
    n, m = map(int, line.split())  # n 個人,m 道菜
    money = list(map(int, sys.stdin.readline().split()))  # 每個人原來的錢
    dishes = list(map(int, sys.stdin.readline().split()))  # 每道菜的價格
    if sum(money) < sum(dishes):  # 所有人帶的錢小於所有菜的總價
        print("Oh My God")  # 印出 Oh My God
        continue  # 讀下一筆資料
    pq = [-m for m in money]  # 將 money 每一筆資料加負號存入 pq
    heapq.heapify(pq)  # pq 轉成最小優先佇列
    imax = -pq[0]  # 初始金額最大值
    for dish in dishes:  # 依序讀取每道菜的價格
        while pq and dish > 0:  # 當 pq 還有資料而且 dish 大於 0 時繼續執行
            m = -heapq.heappop(pq)  # 取出 pq 第一項加負號,變回正值
            if m > dish:  # 如果付完這道菜還有錢
                heapq.heappush(pq, -(m-dish))  # 剩下的錢加負號,存入 pq
                dish = 0  # 待付金額為 0
            elif m == dish: dish = 0  # 如果這個人的錢剛好夠用,待付金額為 0
            else: dish -= m  # 如果這個人的錢不夠,更新待付金額
    print(imax, -pq[0] if pq else 0)  # 印出 imax,如果 pq 有資料印出 -pq[0],反之印出 0


2025年10月13日 星期一

ZeroJudge 解題筆記:f493. 水窪問題

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


ZeroJudge 題目連結:f493. 水窪問題

解題想法


這類型的題目我習慣用 BFS 解題,已走訪的位置改成題目給的陸地符號 #,不需要另外開一個陣列儲存已走訪的位置,可以節省一些記憶體。

Python 程式碼


使用時間約為 0.3 s,記憶體約為 11.1 MB,通過測試。
from collections import deque

n, m = map(int, input().split())  # 地圖 n*m
grid = [list(input() + "#") for _ in range(n)]  # 讀取地圖資料,右側加上 #
grid.append(["#"]*(n+1))  # 最下方加上 n+1 個 #
cnt, imin, imax = 0, float('inf'), 0  # 數量,最小面積、最大面積
### BFS ###
for i in range(n):  # 依序掃過每一格
    for j in range(m):
        if grid[i][j] == "#": continue  # 如果是 #,找下一格
        grid[i][j] = "#"  # 此格改成 #
        cnt += 1  # 數量加 1
        area = 0  # 這個水漥的面積
        que = deque([(i, j)])  # (i, j) 加入待走訪佇列 que
        while que:  # 如果 que 還有資料繼續執行
            r, c = que.popleft()  # 從 que 開頭取出座標 (r, c)
            area += 1  # 面積加 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] = "#"  # 此格改成 #
                que.append((nr, nc))  # (nr, nc) 加入 que
        imin = min(imin, area)  # 更新 imin
        imax = max(imax, area)  # 更新 imax
### 結束 BFS ###
if cnt == 0:  # 如果 cnt 等於 0,印出 0 0 0
    print("0 0 0")
else:  # 反之印出 imax, imin, cnt
    print(imax, imin, cnt)


2025年10月12日 星期日

ZeroJudge 解題筆記:f455. 詠竣的哀鳳12

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


ZeroJudge 題目連結:f455. 詠竣的哀鳳12

解題想法


這題是背包問題,用動態規畫處理,但是用 Python 好像沒辦法通過。

Python 程式碼


只能通過 60% 的測資。
t, n = map(int, input().split())  # 總時數 t,工作數量 n
dp = [0]*(t+1)  # 總時數 0 ~ t 對應的最大收入
work = ""  # 最高時薪的工作名稱
imax = 0.0  # 最高時薪
for _ in range(n):  # 執行 n 次
    s, m, h = input().split()  # 工作名稱,收入,需要的時間
    m = int(m); h = int(h)  # m, h 轉為 int
    mph = 1.0*m/h  # 時薪
    if mph > imax:  # 如果時薪較高,更新 imax, work
        imax = mph; work = s
    if h > t: continue  # 如時需要的時間大於 t,不能接工作,找下一筆
    for i in range(t, h-1, -1):  # 倒著更新 dp[t] ~ dp[h]
        dp[i] = max(dp[i], dp[i-h] + m)  # 如果接這個工作總收入變高則更新 dp[i]
print(dp[-1])  # 最高總收入在 dp[t-1], dp[-1]
print(work)  # 印出最高時薪的工作名稱


2025年10月11日 星期六

ZeroJudge 解題筆記:f418. Word Search Puzzle

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


ZeroJudge 題目連結:f418. Word Search Puzzle

解題想法


這題我用二維陣列儲存英文字謎資料,再依照測資給的 r1, c1 及 r2, c2 判斷要向右、向下或是向右下方找答案。

Python 程式碼


使用時間約為 23 ms,記憶體約為 3.3 MB,通過測試。
h, w, r1, c1, r2, c2 = map(int, input().split())
r1 -= 1; c1 -= 1; r2 -=1; c2 -= 1  # 題目的座標從 1 開始
grid = [list(input()) for _ in range(h)]
if r1 == r2:  # 同一列,向右找
    print("".join(grid[r1][c1:c2+1]))
elif c1 == c2:  # 同一欄,向下找
    print("".join([grid[i][c1] for i in range(r1, r2+1)]))
else:  # 向右下方找
    print("".join([grid[r1+i][c1+i] for i in range(r2-r1+1)]))


2025年10月10日 星期五

ZeroJudge 解題筆記:f410. 芝麻街的郵件投遞

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


ZeroJudge 題目連結:f410. 芝麻街的郵件投遞

解題想法


這題考排序,自訂比較式,先排單、雙號,雙號放前面、單號放後面,雙號門牌再由小到大排序,單號門牌再由大到小排序。

Python 程式碼


使用時間約為 51 ms,記憶體約為 4.1 MB,通過測試。
from functools import cmp_to_key

def mycmp(a, b):
    if a%2 == 0 and b%2 == 0:
        if a < b: return -1
        elif a > b: return 1
        else: return 0
    elif a%2 == 1 and b%2 == 1:
        if a > b: return -1
        elif a < b: return 1
        else: return 0
    elif a%2 == 0 and b%2 == 1: return -1
    elif a%2 == 1 and b%2 == 0: return 1
    else: return 0

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = cmp_to_key(mycmp))
print(*arr)


2025年10月9日 星期四

ZeroJudge 解題筆記:f408. 迷你蘋菓鎮

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


ZeroJudge 題目連結:f408. 迷你蘋菓鎮

解題想法


將所有的門牌依照絕對值排序,再依序掃過每一個門牌,如果跟相鄰的門牌相乘小於 0 則答案加 1。

Python 程式碼


使用時間約為 19 ms,記憶體約為 3.4 MB,通過測試。
n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = lambda x : abs(x))
cnt = 0
for i in range(1, n):
    if arr[i-1] * arr[i] < 0:
        cnt += 1
print(cnt)


2025年10月8日 星期三

ZeroJudge 解題筆記:f376. 芝麻街的團購

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


ZeroJudge 題目連結:f376. 芝麻街的團購

解題想法


這題的測資不大,可以真的計算以每個點為中心的總距離,再找其中的最小值。實際上答案就是取中位數。

Python 程式碼


使用時間約為 0.3 s,記憶體約為 19 MB,通過測試。
n = int(input())
psum = [0] + list(map(int, input().split()))
psum.sort()
for i in range(1, n+1): psum[i] += psum[i-1]
imin = float('inf')
ans = 0
for i in range(1, n+1):
    dis = (2*i-n-1)*(psum[i] - psum[i-1]) - psum[i-1] + psum[n] - psum[i]
    if dis < imin:
        imin = dis
        ans = psum[i] - psum[i-1]
print(ans)

使用時間約為 0.1 s,記憶體約為 16.6 MB,通過測試。
n = int(input())
arr = sorted(list(map(int, input().split())))
print(arr[n//2] if n%2 else arr[n//2 - 1])


2025年10月7日 星期二

ZeroJudge 解題筆記:f348. 完全偶數

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


ZeroJudge 題目連結:f348. 完全偶數

解題想法


我先寫一個函式 check 判斷輸入的整數 n 是否每一位都是偶數;再寫另一個函式 solve,找最接近 n 的完全偶數距離。

Python 程式碼


簡單但較慢的寫法,循序搜尋,使用時間約為 30 ms,記憶體約為 3 MB,通過測試。
def check(n):  # 檢查輸入的整數是否每一位都是偶數
    while n:
        if n%10%2 == 1:
            return False
        n //= 10
    return True

def solve(n):  # 輸入整數,找最接近的完全偶數距離
    if check(n): return 0  # 特例,n 是完全偶數,回傳 0
    lower, upper, cnt = n-1, n+1, 0  # 往下找、往上找、次數
    while True:  # 找到答案為止
        cnt += 1  # 次數加 1
        if check(lower): return cnt  # 如果 lower 是完全偶數,回傳 cnt
        if check(upper): return cnt  # 如果 uper 是完全偶數,回傳 cnt
        lower -= 1; upper += 1  # lower 減 1,upper 加 1
    return -1  # 預設的回傳值,用不到

print(solve(int(input())))


2025年10月6日 星期一

ZeroJudge 解題筆記:f332. 貝瑞的鐵線體積

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


ZeroJudge 題目連結:f332. 貝瑞的鐵線體積

解題想法


如果函數為 $y = f(x)$,將此函數曲線以 $x$ 軸為轉軸旋轉,旋轉體體積為 $$ V = \pi \int_a^b y^2 dx $$

Python 程式碼


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

t = int(input())  # 共 t 筆測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 多項式最高次方
    poly = list(map(int, input().split()))  # 多項式由高到低次方各項係數
    square = [0]*(2*n + 1)  # 多項式平方各項係數
    for i in range(n+1):
        for j in range(n+1):
            square[i+j] += poly[i]*poly[j]
    integral = [0]*(2*n + 1)  # 平方後積分結果,忽略常數項
    for i in range(2*n + 1):  # 計算積分式
        integral[i] = 1.0 * square[i] / (2*n + 1 - i)
    ans = 0.0  # 積分結果
    a, b = map(int, input().split())  # 積分下限、上限
    for i, c in enumerate(integral):  # 代入積分下限、上限
        ans += c * (b**(2*n + 1 - i) - a**(2*n + 1 - i))
    print(f"{math.pi*ans:.2f}")  # 印出答案時再乘以 pi


2025年10月5日 星期日

ZeroJudge 解題筆記:f291. 試算表大小

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


ZeroJudge 題目連結:f291. 試算表大小

解題想法


先將讀到的字串拆成左側字母、右側數字兩個部分,再從字母最後面往回讀取,計算是第幾欄,再將欄數乘以列數就是答案。

Python 程式碼


使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
s = input()  # 輸入的儲存格編號
left = ""  # 左半邊的欄位
row = 0  # 列數
for i, c in enumerate(s):  # 依序讀取 s 的字元
    if c.isdigit():  # 如果 c 是數字,取出左半邊,中止迴圈
        left = s[:i]
        row = int(s[i:])
        break
b = 1  # 計算欄位的基底
col = 0  # 欄位編號
for c in left[::-1]:  # 從 left 最後面讀取字元
    col += b*(ord(c) - ord('A') + 1)  # 計算欄位
    b *= 26  # 基底乘以 26
print(row*col)  # 答案是列、欄相乘


2025年10月4日 星期六

ZeroJudge 解題筆記:f260. 愛八卦的同學

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


ZeroJudge 題目連結:f260. 愛八卦的同學

解題想法


我用 BFS 找連通區塊數量,不過用 Python 的速度太慢,用 C++ 解題也要 0.3 s。

Python 程式碼


速度太慢,只能通過一筆測資。
import sys
from collections import deque

for line in sys.stdin:
    n, k = map(int, line.split())  # n 個人,k 組關係
    adj = [[] for _ in range(n)]  # 每個人與其它人的關係
    for _ in range(k):  # 讀取 k 行資料
        u, v = map(int, sys.stdin.readline().split())  # u, v 是朋友
        adj[u].append(v)
        adj[v].append(u)
    cnt = 0  # 小團體數量
    visited = [False]*n  # 是否已經檢查過
    for i in range(n):  # 依序讀取每一個人
        if visited[i]: continue  # 如果 i 已經檢查過,找下一個人
        visited[i] = True  # 設定為 True
        cnt += 1
        que = deque([i])
        while que:
            v = que.popleft()
            for u in adj[v]:
                if visited[u]: continue
                que.append(u)
                visited[u] = True
    print(cnt)


2025年10月3日 星期五

ZeroJudge 解題筆記:f257. 君王的處刑遊戲

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


ZeroJudge 題目連結:f257. 君王的處刑遊戲

解題想法


我是用二維陣列儲存每一個人的驚恐值,預設值為 0,-1 代表已淘汰,Python 的最右側、最下方加上 -1 當作哨兵,C++ 周圍加上 -1 當作哨兵。每次檢查位置 (x, y) 的人,如果還沒有淘汰就設定成 -1,再檢查周圍 8 格,遇到還沒有被淘汰的人就將驚恐值加 1。

Python 程式碼


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

for line in sys.stdin:
    n = int(line)  # 二維陣列 n*n
    grid = [[0]*n + [-1] for _ in range(n)]  # 最右側、最下方加 -1 當作哨兵
    grid.append([-1]*(n+1))
    k = int(sys.stdin.readline())  # 要淘汰的人數
    for _ in range(k):  # 執行 k 次
        x, y = map(int, sys.stdin.readline().split())  # 要淘汰的人位置 (y, x)
        if grid[y][x] == -1: continue  # 已淘汰,找下一個
        grid[y][x] = -1  # 已淘汰,設定成 -1
        # 搜尋四周的 8 格
        for dy, dx in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
            ny, nx = y+dy, x+dx  # 檢查 grid[ny][nx]
            if grid[ny][nx] == -1: continue  # 已淘汰,找下一個
            grid[ny][nx] += 1  # 周圍的人驚恐值加 1
    # 執行完畢,要印出答案,不能印出最右側、最下方的哨兵,-1 要換成 x
    for row in grid[:n]:
        print("".join([str(i) if i != -1 else "x" for i in row[:n]]))


2025年10月2日 星期四

ZeroJudge 解題筆記:f164. 萬球同心移位之章

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


ZeroJudge 題目連結:f164. 萬球同心移位之章

解題想法


這題絕對不要真的用鏈結串列解題,因為要找到鏈結串列中指定的值只能從頭開始依序往下找,一定會超時。用兩個陣列儲存每一個節點的左、右節點編號,移動節點時只要修改對應的節點編號即可。

Python 程式碼


最後一筆測資記憶體爆掉。
n, m, q = map(int, input().split())  # n 顆球,m 次操作,q 次查詢
pre = [(i-1+n)%n for i in range(n)]  # 每顆球的前一顆球
nxt = [(i+1)%n for i in range(n)]  # 每顆球的後一顆球
for _ in range(m):  # 執行 m 次
    d, a, b = input().split()  # 方向 d,a 球移到 b 球旁邊
    if a == b: continue  # 如果 a 等於 b,不移動
    a = int(a); b = int(b)  # 轉成整數
    nxt[pre[a]] = nxt[a]  # a 原來左側的球接到 a 原來右側的球
    pre[nxt[a]] = pre[a]  # a 原來右側的球接到 a 原來左側的球
    if d == 'R':  # 逆向
        le = pre[b]  # 暫存 b 原來左側的球
        nxt[le] = a  # b 原來左側的球接到 a
        pre[b] = a  # b 的左側接到 a
        pre[a] = le  # a 左側接到 le
        nxt[a] = b  # a 右側接到 b
    else:  # 順向
        ri = nxt[b]  # 暫存 b 原來右側的球
        pre[ri] = a  # b 原來右側的球接到 a
        nxt[b] = a  # b 的右側接到 a
        pre[a] = b  # a 的左側接到 b
        nxt[a] = ri  # a 的右側接到 ri
arr = tuple(map(int, input().split()))
for a in arr[:-1]: print(pre[a], nxt[a], end=" ")
print(pre[arr[-1]], nxt[arr[-1]])


2025年10月1日 星期三

ZeroJudge 解題筆記:e984. 連假時在做什麼?有沒有空?可以來打code嗎?

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


ZeroJudge 題目連結:e984. 連假時在做什麼?有沒有空?可以來打code嗎?

解題想法


用一個自訂函式 find_lln 找第 k 項的 LunlunNumber。在函式中用一個 deque 儲存待處理的數字,先放入 1 ~ 9,再用一個 while 迴圈,當 que 還有資料繼續執行;在迴圈中每次取出 que 開頭的數字存入 num,計數器 cnt 數量加 1,如果 cnt 等於 k,已經找到答案,回傳 num;如果 cnt 小於 k,取出 num 的個位數 last_digit,計算 last_digit 加減 1、不變、加 1 的數值 next_digit,如果 next_digit 在 1 到 9 之中,將新的數值加入 que 之中。

Python 程式碼


單筆測資,使用時間約為 2 s,記憶體約為 93.2 MB,通過測試。
from collections import deque

def find_lln(k):  # 找第 k 位的 Lunlun Number
    que = deque([i for i in range(1, 10)])  # 待處理的數字,先放入 1 ~ 9
    cnt = 0  # 計數器
    while que:  # 當 que 還有資料繼續執行
        num = que.popleft()  # 取出 que 開頭的數字
        cnt += 1  # 計數器加 1
        if cnt == k:  # 如果是第 k 位
            return num  # 回傳 num 並離開函式
        last_digit = num%10  # 取出個位數
        for delta in (-1, 0, 1):  # 個位數的差值 -1, 0, 1
            next_digit = last_digit + delta  # 下一個個位數值
            if 0 <= next_digit <= 9:  # 如果在 0 ~ 9 之間
                que.append(num*10 + next_digit)  # 新的數值加入 que
    return 0  # 預設的回傳值,理論上不會用到

print(find_lln(int(input())))