ZeroJudge 解題筆記：f147. 1. 點餐系統 (Ordering System)

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



ZeroJudge 題目連結：f147. 1. 點餐系統 (Ordering System)

解題想法

如果使用 Python，可以把套餐、單點的名稱、價格，分別儲存在一個二維數組之中，也可以全部儲存在一個三維數組之中。但是 C++ 的陣列只能儲存相同格式的資料，如果想要全部儲存在同一個陣列之中，要自訂結構體才行。

Python 程式碼

把套餐、單點的名稱、價格，分別儲存在一個二維數組之中。使用時間約為 39 ms，記憶體約為 3.4 MB，通過測試。

combo = (("", 0), ("Medium Wac", 4), ("WChicken Nugget", 8),
         ("Geez Burger", 7), ("ButtMilk Crispy Chicken", 6), ("Plastic Toy", 3))
dish = (("", 0), ("German Fries", 2), ("Durian Slices", 3),
        ("WcFurry", 5), ("Chocolate Sunday", 7))
tot = 0  # 總金額
while True:
    order = int(input())  # 讀取指令
    if order == 0:  # 當指令等於 0，印出總金額，中止迴圈
        print(f"Total: {tot:d}")
        break
    num = int(input())  # 套餐或單點號碼
    if order == 1:
        print(f"{combo[num][0]:s} {combo[num][1]:d}")
        tot += combo[num][1]
    elif order == 2:
        print(f"{dish[num][0]:s} {dish[num][1]:d}")
        tot += dish[num][1]

ZeroJudge 解題筆記：f072. 3. 家裡的後花園 (Garden)

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



ZeroJudge 題目連結：f072. 3. 家裡的後花園 (Garden)

解題想法

因為某一塊地上面或四周可能有好幾隻害蟲，如果用 list 儲存不能種花的位置可能會重複儲存到同一塊地，所以我改用 set 儲存資料。

Python 程式碼

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

n = int(input())  # 有 n 塊地
arr = list(map(int, input().split()))  # 地形
fence = []  # 柵欄位置
bug = set()  # 因為害蟲不能種花的位置
for i in range(n):  # 依序掃過每一塊地
    if arr[i] == 1: fence.append(i)  # 如果是柵欄，加入 fence
    elif arr[i] == 9:  # 如果是害蟲
        bug.add(i)  # i 加入 bug
        if 0 <= i-1 < n and arr[i-1] == 0: bug.add(i-1)  # 如果 i-1 沒有出界且是空地，加入 bug
        if 0 <= i+1 < n and arr[i+1] == 0: bug.add(i+1)  # 如果 i+1 沒有出界且是空地，加入 bug
tot = 0  # 可以種花的空地總數
for i in range(len(fence)-1):  # 計算可以種花的空地總數
    le, ri = fence[i], fence[i+1]  # 相鄰兩片柵欄的位置
    for j in range(le+1, ri):  # 依序掃過兩片柵欄之間的位置
        if j not in bug: tot += 1  # 如果沒有害蟲，tot 加 1
print(tot)

ZeroJudge 解題筆記：f071. 2. 刮刮樂 (Lottery)

作者：王一哲
Ver. 1: 2025年2月26日
Ver. 2: 2025年5月24日


ZeroJudge 題目連結：f071. 2. 刮刮樂 (Lottery)

解題想法

注意：同一個號碼可能出現不只一次，金額可能會有好幾個。因為號碼可能不連續，所以我用字典儲存號碼與對應的金額。

Python 程式碼

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

a, b, c = map(int, input().split())  # 幸運數字
key = list(map(int, input().split()))  # 號碼
val = list(map(int, input().split()))  # 金額
lottery = dict()  # {號碼: [金額]}，同一個號碼可能出現不只一次，金額可能會有好幾個
for k, v in zip(key, val):  # 依序讀取 key 及 val
    if k not in lottery: lottery[k] = [v]  # 如果 k 不在 lottery 之中，對應的值為 [v]
    else: lottery[k].append(v)  # 如果 k 在 lottery 之中，對應的值加上 v
tot = 0  # 奬金
if a in lottery:  # 如果 a 在 lottery 之中，加上對應的金額
    for v in lottery[a]:
        tot += v
if b in lottery:  # 如果 b 在 lottery 之中，加上對應的金額
    for v in lottery[b]:
        tot += v
if c in lottery:  # 如果 c 在 lottery 之中，減去對應的金額
    for v in lottery[c]:
        tot -= v
else: tot *= 2  # 如果 c 不在 lottery 之中，tot 加倍
if tot < 0: tot = 0  # 如果 tot 為負值，歸零
print(tot)  # 印出答案

後來想到只要更新同一個號碼的總金額就好，不需要像上面的寫法那麼複雜。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

a, b, c = map(int, input().split())  # 幸運數字
key = list(map(int, input().split()))  # 號碼
val = list(map(int, input().split()))  # 金額
lottery = dict()  # {號碼: 金額}，同一個號碼可能出現不只一次，金額可能會有好幾個，要加起來
for k, v in zip(key, val):  # 依序讀取 key 及 val
    if k not in lottery: lottery[k] = v  # 如果 k 不在 lottery 之中，對應的值為 v
    else: lottery[k] += v  # 如果 k 在 lottery 之中，對應的值加上 v
tot = 0  # 奬金
if a in lottery: tot += lottery[a]  # 如果 a 在 lottery 之中，加上對應的金額
if b in lottery: tot += lottery[b]  # 如果 b 在 lottery 之中，加上對應的金額
if c in lottery: tot -= lottery[c]  # 如果 c 在 lottery 之中，減去對應的金額
else: tot *= 2  # 如果 c 不在 lottery 之中，tot 加倍
if tot < 0: tot = 0  # 如果 tot 為負值，歸零
print(tot)  # 印出答案

ZeroJudge 解題筆記：f070. 1. 韓信點兵 (HanXin)

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



ZeroJudge 題目連結：f070. 1. 韓信點兵 (HanXin)

解題想法

這題考數學，比較不像考演算法。

Python 程式碼

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

nums = sorted([list(map(int, input().split())) for _ in range(3)], reverse=True)
i = 1  # 倍數
while True:
    n = nums[0][0]*i + nums[0][1]  # 用最大的因數乘以 i 再加上餘數
    # 檢查 n 是否符合另外兩個因數，如果皆符合，印出 n 並中止迴圈
    if (n - nums[1][1])%nums[1][0] == 0 and (n - nums[2][1])%nums[2][0] == 0:
        print(n); break
    i += 1  # i 加 1

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<pair<int, int>> nums (3);
    for(int i=0; i<3; i++) cin >> nums[i].first >> nums[i].second;
    sort(nums.begin(), nums.end(), greater<pair<int, int>> ());
    int i = 1;  // 倍數
    while(true) {
        int n = nums[0].first*i + nums[0].second;  // 用最大的因數乘以 i 再加上餘數
        // 檢查 n 是否符合另外兩個因數，如果皆符合，印出 n 並中止迴圈
        if ((n - nums[1].second)%nums[1].first == 0 && (n - nums[2].second)%nums[2].first == 0) {
            cout << n << "\n"; break;
        }
        i++;  // i 加 1
    }
    return 0;
}

ZeroJudge 解題筆記：f045. 3. 身分驗證機制 (Verification)

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



ZeroJudge 題目連結：f045. 3. 身分驗證機制 (Verification)

解題想法

因為輸入的編號可能會以 0 開頭，要用字串儲存資料，不能用整數。

Python 程式碼

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

s = input().strip()  # 代號
a, b = 0, 0  # 最大的兩個數字
for c in s:  # 由 s 依序讀取字元 c
    c = int(c)  # 轉成整數
    if c >= a:  # 如果 c 大於等於 a，c 是最大值，b 改為原來的 a
        b = a; a = c
    elif c > b: b = c # 如果 c 小於 a 且 c 大於 b，b 改為 c
if a*a + b*b == int(s[-3:]): print("Good Morning!")
else: print("SPY!")

C++ 程式碼

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;  // 代號
    int a = 0, b = 0;  // 最大的兩個數字
    for(char c : s) {  // 由 s 依序讀取字元 c
        int d = c - '0';  // 轉成整數
        if (d >= a) {  // 如果 d 大於等於 a，d 是最大值，b 改為原來的 a
            b = a; a = d;
        } else if (d > b) b = d;  // 如果 d 小於 a 且 d 大於 b，b 改為 d
    }
    if (a*a + b*b == stoi(s.substr(s.size()-3))) cout << "Good Morning!\n";
    else cout << "SPY!\n";
    return 0;
}

ZeroJudge 解題筆記：f044. 2. 史萊姆生態區 (Slime)

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



ZeroJudge 題目連結：f044. 2. 史萊姆生態區 (Slime)

解題想法

要先找到數據的規律，列出前 5 天的數據應該就能寫出數量與天數的關係式。

day	big	small	total
0	1	0	1 = 20
1	1	1	2 = 21
2	1	1 + 2 = 3	1 + 3 = 4 = 22
3	1	3 + 7 = 7	1 + 7 = 8 = 23
4	1	7 + 8 = 15	1 + 15 = 16 = 24
5	1	15 + 16 = 31	1 + 31 = 32 = 25

Python 程式碼

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

n, t = map(int, input().split())  # 史萊姆王、小史萊姆的數量比例
if n > 1:  # 如果 n 大於 1，約分
    t //= n; n = 1
d, s = 0, 1  # 天數，總數
while s < n+t:  # 當 s 小於 n+t
    d += 1  # 天數加 1
    s *= 2  # s 變成 2 倍
print(d)

直接取 $\log_2$，使用時間約為 39 ms，記憶體約為 3.3 MB，通過測試。

import math
n, t = map(int, input().split())  # 史萊姆王、小史萊姆的數量比例
if n > 1:  # 如果 n 大於 1，約分
    t //= n; n = 1
print(int(math.log(n+t, 2)))

ZeroJudge 解題筆記：e975. 3. 情書解密 (Love)

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



ZeroJudge 題目連結：e975. 3. 情書解密 (Love)

解題想法

Python 可以用 find 在字串中找特定的子字串，如果有找到會回傳子字串開頭字元的索引值，沒有找到會回傳 -1；如果用 index 在沒有找到時會跳出錯誤訊息，所以用 find 比較好。

Python 程式碼

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

def test(s):
    for i in range(26):  # 依序測試偏移量 0 ~ 25
        t = ""  # 移動後的字串
        for c in s:  # 依序由 s 讀取字元 c，將 c 的編號 +i 轉成字元存入 t
            if 'A' <= c <= 'Z': t += chr((ord(c)-ord('A')+i)%26 + ord('A'))
            elif 'a' <= c <= 'z': t += chr((ord(c)-ord('a')+i)%26 + ord('a'))
        j = t.find("love")  # 在字串 t 中找 love，回傳索引值 j
        k = t.find("Love")  # 在字串 t 中找 Love，回傳索引值 k
        if j != -1 or k != -1: return i  # 如果 j 或 k 不等 -1，有找到 love 或 Love，回傳 i
    return -1  # 如果跑完以上的 for loop 都沒有回傳值，則回傳 -1 代表沒有找到 love

line = input().strip()  # 讀取一行字串，刪除最後面的 \n
ans = test(line)  # 呼叫 test
if ans >= 0: print(ans)
else: print("-1")

ZeroJudge 解題筆記：e974. 座位安排 (Seats)

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



ZeroJudge 題目連結：e974. 座位安排 (Seats)

解題想法

這題在 Python 用 list 切片比較用索引值好寫，而且速度也快很多。

Python 程式碼

用 list 切片比較好寫，使用時間約為 38 ms，記憶體約為 4.5 MB，通過測試。

r, c, n = map(int, input().split())  # 列數 r，行數 c，週數 n
seat = [list(range(i*c+1, (i+1)*c+1)) for i in range(r)]  # 原來的座位表
for i in range(2, n+1):  # 依序處理第 2 ~ n 週
    if i%2 == 1:  # 單數週，所有人往後移一個座位，原本最後一排的人換到第一排
        seat = [seat[-1]] + seat[:-1]
    else:  # 雙數週，所有人往右橫移一個座位，原本最右邊的人則換到最左邊
        for j in range(r):  # 依序處理第 0 ~ r-1 列
            seat[j] = [seat[j][-1]] + seat[j][:-1]
for row in seat: print(*row)

用索引值設定串列中的值，速度會比用切片慢很多。使用時間約為 0.5 s，記憶體約為 4.5 MB，通過測試。

r, c, n = map(int, input().split())  # 列數 r，行數 c，週數 n
seat = [list(range(i*c+1, (i+1)*c+1)) for i in range(r)]  # 原來的座位表
for i in range(2, n+1):  # 依序處理第 2 ~ n 週
    if i%2 == 1:  # 單數週，所有人往後移一個座位，原本最後一排的人換到第一排
        tmp = seat[-1].copy()  # 第 r-1 列的編號先存到 tmp
        for j in range(r-1, -1, -1):  # 依序處理第 r-1 ~ 0 列
            for k in range(c):  # 依序處理第 0 ~ c-1 行
                if j == 0: seat[j][k] = tmp[k]  # 第 0 列，設定為 tmp
                else: seat[j][k] = seat[j-1][k]  # 其它列，向後移一行
    else:  # 雙數週，所有人往右橫移一個座位，原本最右邊的人則換到最左邊
        for j in range(r):  # 依序處理第 0 ~ r-1 列
            tmp = seat[j][-1]  # 每列第 c-1 行的編號先存到 tmp
            for k in range(c-1, -1, -1):  # 依序處理第 c-1 ~ 0 行
                if k == 0: seat[j][k] = tmp  # 第 j 列第 0 行，設定為 tmp
                else: seat[j][k] = seat[j][k-1]  # 其它行，向右移一行
for row in seat: print(*row)

ZeroJudge 解題筆記：e973. 3. 滿意度調查 (Survey of Satisfaction)

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



ZeroJudge 題目連結：e973. 3. 滿意度調查 (Survey of Satisfaction)

解題想法

這題用 map 和自訂排序用的比較式，寫起來會很方便。

Python 程式碼

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

from collections import Counter
from functools import cmp_to_key

def mycmp(a, b):
    if a[0] > b[0]: return -1  # 如果 a[0] 大於 b[0]，a 往前放
    elif a[0] < b[0]: return 1  # 如果 a[0] nc 於 b[0]，a 往後放
    else:  # 如果 a[0] 等於 b[0]
        if a[1] < b[1]: return -1  # 如果 a[0] 小於 b[0]，a 往前放
        elif a[1] > b[1]: return 1  # 如果 a[0] 大於 b[0]，a 往後放
        else: return 0

cnt = Counter(list(input().strip()))  # 讀取字串，去掉結尾的 \n，轉成 list，傳入計數器
output = sorted([(val, key) for key, val in cnt.items()], key=cmp_to_key(mycmp))  # 讀取 cnt 的資料並排序
for i in range(len(output)):  # 印出答案
    print(output[i][1], end='\n' if i == len(output)-1 else ' ')

ZeroJudge 解題筆記：e972. 1. 貨幣轉換 (Currency)

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



ZeroJudge 題目連結：e972. 1. 貨幣轉換 (Currency)

解題想法

這題的第三筆測資是用 \r 換行，用 Python 解題反而很麻煩。

Python 程式碼

因為第3筆測資是用 \r 分隔資料，這樣寫過不了。

import re
ori = int(input())  # 原有的金額
rem = 0  # 剩下的金額
data = re.split(r"\s+", input())
cost = int(data[0])
if data[1] == 'T': rem = ori - cost  # 台幣
elif data[1] == 'U': rem = ori / 30.9 - cost  # 美金
elif data[1] == 'J': rem = ori / 0.28 - cost  # 日幣
elif data[1] == 'E': rem = ori / 34.5 - cost  # 歐元
if 0 < rem < 0.05: rem = 0.00  # 若 rem 為正數且小於 0.05，改成 0.00 
if rem < 0: print("No Money")  # 如果 rem 小於 0，印出 No Money
else: print(f"{data[1]:s} {rem:.2f}")  # 剩出幣制及餘額

改成這樣才能通過。使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

data = input().replace('\r', ' ')  # 將 \r 換成空格
try:
    n = input()
except:  # 為了處理第 3 筆測資，\r 會使游標在換行後移到上一行
    data, a, b = data.split()  # 目的地幣值 b
else:
    a, b = n.split()
    
ori = int(data)  # 原有的金額
cost = int(a)  # 花費
rem = 0  # 剩下的金額

if b == 'T': rem = ori - cost  # 台幣
elif b == 'U': rem = ori / 30.9 - cost  # 美金
elif b == 'J': rem = ori / 0.28 - cost  # 日幣
elif b == 'E': rem = ori / 34.5 - cost  # 歐元
if 0 < rem < 0.05: rem = 0.00  # 若 rem 為正數且小於 0.05，改成 0.00 
if rem < 0: print("No Money")  # 如果 rem 小於 0，印出 No Money
else: print(f"{b:s} {rem:.2f}")  # 剩出幣制及餘額