ZeroJudge 解題筆記：h658. 捕魚 (Fishing)

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



ZeroJudge 題目連結：h658. 捕魚 (Fishing)

解題想法

用距離平方判斷是否在範圍內即可，不需要開根號。

Python 程式碼

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

import sys

for line in sys.stdin:
    x, y = map(int, line.split())  # 漁夫的座標
    n = int(input())  # n 筆資料
    ax, ay, d = 0, 0, float('inf')  # 最接近的魚群座標、距離的平方
    for _ in range(n):  # 執行 n 次
        xi, yi = map(int, input().split())  # 魚群座標
        di = (x - xi)**2 + (y - yi)**2  # 距離的平方
        if di < d:  # 如果距離較近，更新 ax, ay, d
            ax, ay, d = xi, yi, di
    print(ax, ay)

ZeroJudge 解題筆記：h035. 夜市 (Night Market)

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



ZeroJudge 題目連結：h035. 夜市 (Night Market)

解題想法

注意題目中的這句「但一塊板子只會採計一次得分」，不能重複計分。測資應該只有單筆輸入。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 投球 n 次
    down = [-1]*10  # 各編號的格子被打落的時刻，-1 代表沒有被打落
    hit = [False]*10  # 各編號的格子是否被打落過
    cnt, score, perfect = 0, 0, False  # 目前打落的板子數量，總分，是否全清
    for i, x in enumerate(list(map(int, input().split())), start=1):  # 依序讀取投球命中的格子
        for j in range(1, 10):  # 檢查每塊板子是否能升起
            if down[j] != -1 and i == down[j] + 12:  # 如果第 j 塊板子已被打落而且 i 等於第 j 塊板子被打落的時刻加 12
                down[j] = -1; cnt -= 1  # 升起第 j 塊板子，cnt 減 1
        if x != -1 and down[x] == -1:  # 如果 x 不等於 -1 而且 x 號板子目前沒有被打落
            cnt += 1; down[x] = i  # cnt 加 1，設定 x 被打落的時刻為 i
            if not hit[x]:  # 如果 x 號板子沒有被打落過
                score += x; hit[x] = True  # 分數加 x，x 號板子被打落過
        if cnt == 9:  # 如果 cnt 等於 9，全清，中止迴圈
            perfect = True; break
    print("perfect" if perfect else score)

ZeroJudge 解題筆記：h034. 宴會 (Banquet)

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



ZeroJudge 題目連結：h034. 宴會 (Banquet)

解題想法

這題在 Python 可以 itertools.zip_longest 會比較方便。

Python 程式碼

只使用預設工具的寫法，使用時間約為 53 ms，記憶體約為 5.9 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 餐廳總數
    food = [input().strip() for _ in range(n)]  # 儲存各餐廳的菜單
    m = max([len(f) for f in food])  # 最長的菜單數量
    for i in range(m):  # 處理 m 次
        for j in range(n):  # 印出各家餐廳的菜名
            if i < len(food[j]) and food[j][i].isupper():  # 如果 i 還沒有出界而且 food[j][i] 是大寫字母
                print(food[j][i], end="")  # 印出這個字母
    print()  # 全部跑完再換行

Python 中有一個 zip 工具，用來將數個可以迭代的物件綁在一起輸出，但是 zip 會以這些物件中最短的一個作為輸出的上限，其它較長的部分會被捨去。如果要以最長的物件作為輸出的上限，要用 itertools.zip_longest，長度不夠的部分會補 None。使用時間約為 55 ms，記憶體約為 6 MB，通過測試。

import sys
from itertools import zip_longest

for line in sys.stdin:
    n = int(line)  # 餐廳總數
    food = [input().strip() for _ in range(n)]  # 儲存各餐廳的菜單
    for f in zip_longest(*food):  # 先將 food 拆開成多個一維串列，用 zip_longest 綁在一起依序輸出
        for c in f:  # 依序由 f 讀取各家餐廳的菜名
            if c != None and c.isupper():  # 如果 c 不等於 None 而且是大寫字母
                print(c, end="")  # 印出這個字母
    print()  # 全部跑完再換行

ZeroJudge 解題筆記：h033. 雜訊移除 (Noise)

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



ZeroJudge 題目連結：h033. 雜訊移除 (Noise)

解題想法

這題在 Python 可以用 replace 將不要的字元取代成空字串。

Python 程式碼

用 replace 可以取代字串中指定的字元，取代為空字串就可以移除特定字元。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def is_palindrome(s):  # 檢查 s 是否為迴文字串
    n = len(s)  # s 的長度 n
    for i in range(n//2):  # 依序檢查從頭尾兩端往中間檢查
        if s[i] != s[n-i-1]: return False  # 如果字元不相同回傳 False
    return True  # 如果可以跑完 for loop，回傳 True

for line in sys.stdin:
    s, n = line.split()  # 要分析的字串 s，要移除的字元 n
    s = s.replace(n, "")  # 將 s 之中的 n 取代為空字串
    print("Yes" if is_palindrome(s) else "No")  # 印出答案

如果不使用 replace，也可以遍歷字串，將要留下來的字元存到另一個空字串裡。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def is_palindrome(s):  # 檢查 s 是否為迴文字串
    n = len(s)  # s 的長度 n
    for i in range(n//2):  # 依序檢查從頭尾兩端往中間檢查
        if s[i] != s[n-i-1]: return False  # 如果字元不相同回傳 False
    return True  # 如果可以跑完 for loop，回傳 True

for line in sys.stdin:
    s, n = line.split()  # 要分析的字串 s，要移除的字元 n
    t = ""  # 儲存 s 移除 n 之後的空字串
    for c in s:  # 依序由 s 讀取字元 c
        if c != n: t += c  # 如果 c 不等於 n，接到 t 之後
    print("Yes" if is_palindrome(t) else "No")  # 印出答案

ZeroJudge 解題筆記：g798. 帶動商機 (Business)

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



ZeroJudge 題目連結：g798. 帶動商機 (Business)

解題想法

這題按照題目敘述操作陣列即可，不需要用複雜的寫法。

Python 程式碼

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

import sys

for line in sys.stdin:
    arr = list(map(int, line.split()))[:-1]  # 讀取一開始的人數，刪掉最後的 0
    m = len(arr)  # 店家數量
    n = int(input())  # 更新 n 天
    for _ in range(n):  # 執行 n 次
        tmp = arr.copy()  # 暫存更新後的人數
        for i in range(m):  # 依序掃過 0 ~ m-1 家店
            if i == 0:  # 最左邊的店家
                if arr[i] > arr[i+1]:  # 如果人數大於右邊的店家
                    tmp[i+1] += arr[i]//10  # 右邊的店家人數增加量
            elif i == m-1:  # 最右邊的店家
                if arr[i] > arr[i-1]:  # 如果人數大於左邊的店家
                    tmp[i-1] += arr[i]//10  # 左邊的店家人數增加量
            else:  # 中間的店家
                if arr[i] > arr[i-1]:  # 如果人數大於左邊的店家
                    tmp[i-1] += arr[i]//20  # 左邊的店家人數增加量
                if arr[i] > arr[i+1]:  # 如果人數大於右邊的店家
                    tmp[i+1] += arr[i]//20  # 右邊的店家人數增加量
        arr, tmp = tmp, arr  # 交換 arr、tmp
    print(*arr)  # 印出答案

ZeroJudge 解題筆記：g797. 洗牌 (Cards)

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



ZeroJudge 題目連結：g797. 洗牌 (Cards)

解題想法

這題考陣列操作，可以將陣列先拆開成上、下兩半再合併，或是用另一個陣列儲存洗牌後的資料。

Python 程式碼

寫法1，用串列切片先找出上、下兩半的內容，再合併資料。使用時間約為 26 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    upp, bot = deck[:n//2], deck[n//2:]  # 分成上、下兩半
    for _ in range(m):  # 執行 m 次
        for i in range(n//2):  # 執行 n//2 次
            deck[2*i] = upp[i]  # 從 upp 及 bot 依序取值放入 deck
            deck[2*i+1] = bot[i]
        upp, bot = deck[:n//2], deck[n//2:]  # 更新 upp、bot
    print(*deck)  # 印出答案

寫法2，滾動串列，將洗牌後的資料先存入另一個串列。使用時間約為 28 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 張牌，洗牌 m 次
    deck = list(map(int, input().split()))  # 讀取牌面數值
    for _ in range(m):  # 執行 m 次
        tmp = [0]*n  # 暫存洗牌後的資料
        for i in range(n//2):  # 執行 n//2 次
            tmp[2*i] = deck[i]  # 從 deck 前半取值放入 tmp
            tmp[2*i+1] = deck[n//2 + i]  # 從 deck 後半取值放入 tmp
        deck, tmp = tmp, deck  # 交換 deck、tmp
    print(*deck)  # 印出答案

ZeroJudge 解題筆記：g541. 類題:兔子跳躍(TOIP)

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



ZeroJudge 題目連結：g541. 類題:兔子跳躍(TOIP)

解題想法

雖然看起來是g498. 兔子跳躍 (Rabbit)的加強版，但其實用相同的寫法跑迴圈測試是否能走到 $d$ 一定會超時，即使用字典儲存已經跑過的值還是會超時，需要從數學上分析題目才行。如果兩種步數 $m$、$n$ 的最大公因數為 $G$、最小公倍數為 $L$，則所有 $L + kG, k = 0, 1, 2, 3, \dots$ 的數皆可以用大於等於 0 個 $m$、$n$ 組合而成，若以 $m = 9$、$n = 12$ 為例，$G = 3$、$L = 36$，則

1. $36 = 4 \times 9 = 3 \times 12$
2. $39 = 3 \times 9 + 1 \times 12$
3. $42 = 2 \times 9 + 2 \times 12$
4. $45 = 1 \times 9 + 3 \times 12$
5. $48 = 0 \times 9 + 4 \times 12$
6. $51 = 3 \times 9 + 2 \times 12$
7. $54 = 2 \times 9 + 3 \times 12$
8. $57 = 1 \times 9 + 4 \times 12$
9. $60 = 0 \times 9 + 5 \times 12 = 4 \times 9 + 2 \times 12$
10. $63 = 3 \times 9 + 3 \times 12$

Python 程式碼

寫法1，根據g498. 兔子跳躍 (Rabbit)的寫法改寫而成，第2筆測資開始超時。

import sys

def solve(m, n, d):  # 自訂函式，測是是否能走到 d
    for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
        if (d-i)%n == 0: return True  # 如果 d-i 可以被 n 整除，能走到 d
    return False  # 如果能跑完 for 迴圈，走不到 d

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(m, n, d) else "NO")  # 印出答案

寫法2，根據以上的寫法並改用 map 儲存已經測試過的值，第2筆測資開始超時。

import sys

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    memo = dict()  # 記憶已經算過的數據
    def solve(d):  # 自訂函式，測是是否能走到 d
        if d in memo: return memo[d]
        for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
            if (d-i)%n == 0:
                memo[d] = True
                return True  # 如果 d-i 可以被 n 整除，能走到 d
        memo[d] = False
        return False  # 如果能跑完 for 迴圈，走不到 d
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(d) else "NO")  # 印出答案

ZeroJudge 解題筆記：g498. 兔子跳躍 (Rabbit)

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



ZeroJudge 題目連結：g498. 兔子跳躍 (Rabbit)

解題想法

這題測資不大，用 for 迴圈依序檢測每一個值就能過關。

Python 程式碼

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

import sys

for line in sys.stdin:
    m, n, d = map(int, line.split())  # 可跳距離 m、n，目標距離 d
    def solve():  # 自訂函式，測是是否能走到 d
        for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
            if (d-i)%n == 0: return True  # 如果 d-i 可以被 n 整除，能走到 d
        return False  # 如果能跑完 for 迴圈，走不到 d
    print("YES" if solve() else "NO")  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 84 kB，通過測試。

#include <cstdio>
using namespace std;

bool solve(int m, int n, int d) {  // 自訂函式，測是是否能走到 d
    for(int i=0; i<=d; i+=m) {  // 依序測試 0, m, 2m, 3m, ...
        if ((d-i)%n == 0) return true;  // 如果 d-i 可以被 n 整除，能走到 d
    }
    return false;  // 如果能跑完 for 迴圈，走不到 d
}

int main() {
    int m, n, d;  // 可跳距離 m、n，目標距離 d
    while(scanf("%d %d %d", &m, &n, &d) != EOF) {
        if (solve(m, n, d)) printf("YES\n");  // 印出答案
        else printf("NO\n");
    }
    return 0;
}

ZeroJudge 解題筆記：g497. 電梯 (Elevator)

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



ZeroJudge 題目連結：g497. 電梯 (Elevator)

解題想法

注意：電梯一開始在 1 樓。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 升降次數
    arr = [1] + list(map(int, input().split()))  # 停留的樓層，開頭加上 1
    tot = 0  # 耗電量
    for i in range(n):  # 依序掃過 0 ~ n-1
        d = arr[i+1] - arr[i]  # 樓層變化
        if d > 0: tot += 3*d  # 上升一層耗 3 度電
        else: tot -= 2*d  # 下降一層耗 2 度電
    print(tot)  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 96 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n;  // 升降次數
    while(scanf("%d", &n) != EOF) {
        int pre = 1, now, tot = 0;  // 原來的樓層，預設值為 1；現在的樓層；耗電量
        for(int i=0; i<n; i++) {  // 執行 n 次
            scanf("%d", &now);  // 讀取現在的樓層
            int d = now - pre;  // 樓層變化
            if (d > 0) tot += 3*d;  // 上升一層耗 3 度電
            else tot -= 2*d;  // 下降一層耗 2 度電
            pre = now;  // 更新 pre
        }
        printf("%d\n", tot);  // 印出答案
    }
    return 0;
}

ZeroJudge 解題筆記：g496. 彗星列車 (Comet)

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



ZeroJudge 題目連結：g496. 彗星列車 (Comet)

解題想法

注意：這題每組測資有多筆測試資料，而且每筆測試資料之間似乎有空行，如果用 Python 解題要忽略空行，否則會出錯。

Python 程式碼

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

import sys

for line in sys.stdin:
    if len(line.strip()) == 0: continue  # 忽略空行
    a, s = map(int, line.split())
    if s%a == 0: print(s//a)
    else: print(s//a + 1)

C++ 程式碼

用 cmath 函式庫的 ceil，先計算 s/a 的值再取 ceil，計算時及回傳值是浮點數，要再轉回整數，但是這樣無法通過第8筆測資。

#include <cstdio>
#include <cmath>  // for ceil
using namespace std;

int main() {
    int a, s;
    while(scanf("%d %d", &a, &s) != EOF) {
        printf("%d\n", int(ceil((float)s/(float)a)));
    }
    return 0;
}

還是回來用標準寫法，使用時間約為 6 ms，記憶體約為 96 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int a, s;
    while(scanf("%d %d", &a, &s) != EOF) {
        if (s%a == 0) printf("%d\n", s/a);
        else printf("%d\n", s/a + 1);
    }
    return 0;
}