Processing math: 100%

熱門文章

2025年4月4日 星期五

ZeroJudge 解題筆記:h660. 躲避球 (DodgeBall)

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



ZeroJudge 題目連結:h660. 躲避球 (DodgeBall)

解題想法


按照題目敘述計算位置即可,不需要複雜的寫法。

Python 程式碼


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

for line in sys.stdin:
    x, r, v = map(int, line.split())  # 阿茂的位置、接球的左右延伸長度、可接球的球速上限
    for _ in range(int(input())):  # 執行 n 次
        p, s = map(int, input().split())  # 球的落點、速度
        if x-r <= p <= x+r:  # 球在可以接到的範圍內
            if s <= v: x = p  # 球速夠慢,可以接球,移動到 p
            else:  # 球速太快,不能接球
                if p >= x: x -= 15  # 球在右邊或朝人過去,向左移 15
                else: x += 15  # 球在左邊,向右移 15
    print(x)  # 印出最後的位置


2025年4月3日 星期四

ZeroJudge 解題筆記:h659. 計程車 (Taxi)

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



ZeroJudge 題目連結:h659. 計程車 (Taxi)

解題想法


按照題目敘述的標準計算費用即可,不需要複雜的寫法。

Python 程式碼


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

for line in sys.stdin:
    # 行駛總公里數、車輛延滯時間 (min)、上車及下車的時刻 (hr)
    k, w, s, e = map(int, line.split())
    fee = 0  # 費用
    # 計算行駛總公里數産生的費用
    if k <= 2: fee += 20  # 2 km 以內 20 元
    else: fee += 20 + (k-2)*5  # 超過 2 km 加錢 5 元/km
    # 計算車輛延滯時間産生的費用
    fee += w//2*5  # 每滿 2 min 加 5 元
    # 計算夜間加成産生的費用
    if s <= 18 and e >= 19: fee += 185  # 橫跨 18 ~ 19 時,加 185 元
    if s <= 19 and e >= 20: fee += 195  # 橫跨 19 ~ 20 時,加 195 元
    if s <= 20 and e >= 21: fee += 205  # 橫跨 20 ~ 21 時,加 205 元
    if s <= 21 and e >= 22: fee += 215  # 橫跨 21 ~ 22 時,加 215 元
    if s <= 22 and e >= 23: fee += 225  # 橫跨 22 ~ 23 時,加 225 元
    print(fee)  # 印出答案


2025年4月2日 星期三

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)


2025年4月1日 星期二

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)


2025年3月31日 星期一

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()  # 全部跑完再換行


2025年3月30日 星期日

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


2025年3月29日 星期六

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


2025年3月28日 星期五

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


2025年3月27日 星期四

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

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



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

解題想法


雖然看起來是g498. 兔子跳躍 (Rabbit)的加強版,但其實用相同的寫法跑迴圈測試是否能走到 d 一定會超時,即使用字典儲存已經跑過的值還是會超時,需要從數學上分析題目才行。如果兩種步數 mn 的最大公因數為 G、最小公倍數為 L,則所有 L+kG,k=0,1,2,3, 的數皆可以用大於等於 0 個 mn 組合而成,若以 m=9n=12 為例,G=3L=36,則
  1. 36=4×9=3×12
  2. 39=3×9+1×12
  3. 42=2×9+2×12
  4. 45=1×9+3×12
  5. 48=0×9+4×12
  6. 51=3×9+2×12
  7. 54=2×9+3×12
  8. 57=1×9+4×12
  9. 60=0×9+5×12=4×9+2×12
  10. 63=3×9+3×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")  # 印出答案

2025年3月26日 星期三

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;
}