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])

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())))

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

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)  # 答案是列、欄相乘

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)

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]]))

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]])

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())))