ZeroJudge 解題筆記：e971. 2. 梗圖著色 (Coloring)

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



ZeroJudge 題目連結：e971. 2. 梗圖著色 (Coloring)

解題想法

只要記錄前一個 1 的位置就好，不需要用到 queue。

Python 程式碼

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

m, n = map(int, input().split())  # 圖的高度 m、寬度 n
for _ in range(m):  # 讀取 m 行資料
    arr = list(map(int, input().split()))  # 一行圖形資料
    pre = -1  # 前一個 1 的位置，預設為 -1
    for i, a in enumerate(arr):  # 由 arr 依序讀取數值 a、索引值 i
        if a == 1:  # 如果 a 等於 1
            if pre != -1:  # 如果 pre 不等於 -1
                for j in range(pre+1, i): arr[j] = 1 # 將 [pre+1, i-1] 之間都設定為 1
                pre = -1  # pre 重設為 -1
            else: pre = i  # 如果 pre 等於 -1，pre 設定為 i
    print(*arr)  # 印出這行塗色後的結果

C++ 程式碼

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n; cin >> m >> n;  // 圖的高度 m、寬度 n
    for(int i=0; i<m; i++) {  // 讀取 m 行資料
        int arr[n] = {0}, pre = -1;  // 一行圖形資料，前一個 1 的位置，預設為 -1
        for(int j=0, a; j<n; j++) {  // 讀取 n 個數值 a
            cin >> a; arr[j] = a;  // 讀取圖形資料
            if (a == 1) {  // 如果 a 等於 1
                if (pre != -1) {  // 如果 pre 不等於 -1
                    for(int k=pre+1; k<j; k++) arr[k] = 1;  // 將 [pre+1, i-1] 之間都設定為 1
                    pre = -1;  // pre 重設為 -1
                } else pre = j;  // 如果 pre 等於 -1，pre 設定為 j
            }
        }
        for(int j=0; j<n; j++) cout << arr[j] << " \n"[j == n-1];  // 印出這行塗色後的結果
    }
    return 0;
}

ZeroJudge 解題筆記：e970. 1. 粉專抽獎 (Lucky Draw)

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



ZeroJudge 題目連結：e970. 1. 粉專抽獎 (Lucky Draw)

解題想法

按照題目敘述的規則計算就好。

Python 程式碼

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

n = int(input())  # 留言量 n
arr = [0] + list(map(int, input().split()))  # n 個隨機數字
b = arr[-1]  # arr 最後一項是基數 b
tot = 0  # 索引值對應到之隨機數字加總
for i in range(1, n+1):  # 依序測試 1 ~ n
    if i%b == 1: tot += arr[i]  # 如果 i 除以 b 的餘數等於 1，將 arr[i] 加到 tot
m = tot%n  # 中獎留言索引值
if m == 0: m = n  # 如果 m 等於 0，最後一則留言中獎，m 改為 n
print(f"{m:d} {arr[m]:d}")  # 印出 m 及 arr[m]

C++ 程式碼

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

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 留言量 n
    int arr[n+1] = {0};  // n 個隨機數字，為了配合題目的索引值，前面多一個 0
    for(int i=1; i<=n; i++) cin >> arr[i];
    int b = arr[n], tot = 0;  // arr 最後一項是基數 b，索引值對應到之隨機數字加總
    for(int i=1; i<=n; i++) {  // 依序測試 1 ~ n
        if (i%b == 1) tot += arr[i];  // 如果 i 除以 b 的餘數等於 1，將 arr[i] 加到 tot
    }
    int m = tot%n;  // 中獎留言索引值
    if (m == 0) m = n;  // 如果 m 等於 0，最後一則留言中獎，m 改為 n
    cout << m << " " << arr[m] << "\n";  // 印出 m 及 arr[m]
    return 0;
}

ZeroJudge 解題筆記：e969. 大吃大喝 (Big eater)

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



ZeroJudge 題目連結：e969. 大吃大喝 (Big eater)

解題想法

這題要很注意輸出的內容，很容易弄錯一些細節。

Python 程式碼

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

n, m, k = map(int, input().split())
t = 0
food = ("eats an Apple pie", "drinks a Corn soup")
imin = (32, 55)

if n < imin[k]:
    print("Wayne can't eat and drink.")
else:
    while n >= imin[k]:
        n -= imin[k]
        print(f"{t:d}: Wayne {food[k]:s}, and now he ", end="")
        if n == 0: print(f"doesn't have money.")
        elif n == 1: print(f"has 1 dollar.")
        else: print(f"has {n:d} dollars.")
        k = (k+1)%2
        t += m

ZeroJudge 解題筆記：e948. 基礎代謝率 (BMR Calculation)

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



ZeroJudge 題目連結：e948. 基礎代謝率 (BMR Calculation)

解題想法

這題考輸出格式，要輸出小數點後 2 位，如果是用 C++ 可以用 printf 會比較方便。

Python 程式碼

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

n = int(input())  # 人數
for _ in range(n):  # 執行 n 次
    g, a, h, w = map(int, input().split())  # 性別、年齡、身高、體重
    if g == 1:  # 男
        print(f"{13.7*w + 5.0*h - 6.8*a + 66:.2f}")
    else:  # 女
        print(f"{9.6*w + 1.8*h - 4.7*a + 655:.2f}")

C++ 程式碼

使用 iomanip 函式庫的 setprecison 固定輸出的小數點位數。使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 人數
    for(int i=0; i<n; i++) {  // 執行 n 次
        int g, a, h, w; cin >> g >> a >> h >> w;  // 性別、年齡、身高、體重
        float bmr;
        if (g == 1) bmr = 13.7*w + 5.0*h - 6.8*a + 66.0;  // 男
        else bmr = 9.6*w + 1.8*h - 4.7*a + 655.0;  // 女
        cout << fixed << setprecision(2) << bmr << "\n";
    }
    return 0;
}

ZeroJudge 解題筆記：e841. P8. 幽靈寶藏(Treasure)

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



ZeroJudge 題目連結：e841. P8. 幽靈寶藏(Treasure)

解題想法

操作有以下 2 種

1. 在連續的數個藏寶箱內放入 $S$ 枚硬幣。
2. 使連續的數個藏寶箱內的硬幣價值變為 $S$ 倍，包括事後放入的硬幣。

所以操作時不需要考慮先加或是先乘，寫起來會簡單很多。

Python 程式碼

測資很大，第18筆測資開始超時。

n, m = map(int, input().split())  # n 個寶箱，編號 1 ~ n；m 次操作
add = [0]*(n+2)  # 各個寶箱硬幣增加的數量
mul = [1]*(n+2)  # 各個寶箱硬幣乘上的倍數
div = [1]*(n+2)  # 各個寶箱硬幣除掉的倍數
for _ in range(m):  # 讀取 m 次操作
    p, q, r, s = map(int, input().split())  # 範圍 [p, q]，操作種類 r，數量 s
    if r == 1:  # 操作是 1
        add[p] += s  # 編號 p 硬幣加 s
        add[q+1] -= s  # 編號 q+1 硬幣減 s
    elif r == 2:  # 操作是 2
        mul[p] *= s  # 編號 p 硬幣乘上的倍數乘以 s
        div[q+1] *= s  # 編號 q+1 硬幣除掉的倍數乘以 s
# end of for loop
idx, imax = 0, 0  # 最大值的寶箱編號，最大值
cur_val, cur_mul = 0, 1  # 目前的硬幣數量，目前乘上的倍數
for i in range(1, n+1):  # 更新各個寶箱的硬幣數量
    cur_mul = cur_mul * mul[i] // div[i]  # 更新 cur_mul
    cur_val += add[i]  # 更新 cur_val
    cur = cur_val * cur_mul  # 計算硬幣數量
    if cur > imax:  # 如果 cur 較大
        imax = cur  # 更新 imax
        idx = i  # 更新 i
print(f"{idx:d} {imax:d}")

ZeroJudge 解題筆記：e840. P7. 密碼強度測試(Passwords)

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



ZeroJudge 題目連結：e840. P7. 密碼強度測試(Passwords)

解題想法

按照題目給的規則計分就好，不過要注意連續數字的扣分方式，例如 1234，要扣的分數是 $(4-1) \times 2$。

Python 程式碼

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

digit = 0  # 數字數量
letter = 0  # 字母數量
cont = []  # 連續數字
s = input().strip()  # 讀取字串，用 strip 去掉最後的 \0
c1 = s[0]  # 處理 s 開頭的字元
if c1.isdigit():  # 如果 c1 是數字
    digit += 1  # digit 加 1
    cont.append([c1])  # [c1] 加到 cont
elif c1.isalpha(): letter += 1  # 如果 c1 是字母，letter 加 1
# 處理 s[1] ~ s[-1]
for i, c in enumerate(s[1:], start=1):
    if c.isdigit():  # 如果 c 是數字
        digit += 1  # digit 加 1
        if s[i-1].isdigit():  # 如果 s-1 是數字
            cont[-1].append(c)  # c 加到 cont[-1]
        else: cont.append([c])  # 如果 s-1 不是數字，[c] 加到 cont
    elif c.isalpha(): letter += 1  # 如果 c 是字母，letter 加 1
# 計算分數
score = len(s)*3 + letter*3 + digit*2  # 處理長度、字母數量、數字數量
if len(s) >= 8 and digit > 0 and letter > 0: score += 10  # 達最低要求
else: score -= 5  # 未達最低要求
if digit == 0 and letter > 0: score -= letter  # 只有英文字母
if digit > 0 and letter == 0: score -= digit  # 只有數字
for con in cont:  # 依序由 cont 讀取資料 con
    if len(con) > 1: score -= (len(con)-1)*2  # 如果 con 長度大於 1，扣分
print(score)  # 印出分數

ZeroJudge 解題筆記：e839. P6. 飲食分類 (Food)

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



ZeroJudge 題目連結：e839. P6. 飲食分類 (Food)

解題想法

這題用字典儲存各種類食物的名稱會比較方便。

Python 程式碼

使用預設的字典儲存食物名稱、種類。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

n = int(input())  # n 個食物
food = dict()  # 食物種類、名稱
for _ in range(n):  # 讀取 n 行資料
    f, s = input().split()  # 食物名稱 f、種類 s
    if s not in food: food[s] = [f]  # 如果 s 不在 food 之中，food[s] 設定為 [f]
    else: food[s].append(f)  # 如果 s 已經在 food 之中，food[s] 新增 f
t = input().strip()  # 要找的目標
if t not in food: print("No")  # 如果 t 不在 food 之中，印出 No
else:  # 如果 t 在 food 之中，將食物名稱排序後印出
    for f in sorted(food[t]):
        print(f)

改用 collections.defaultdict。使用時間約為 22 ms，記憶體約為 3.6 MB，通過測試。

from collections import defaultdict

n = int(input())  # n 個食物
food = defaultdict(list)  # 食物種類、名稱
for _ in range(n):  # 讀取 n 行資料
    f, s = input().split()  # 食物名稱 f、種類 s
    food[s].append(f)  # food[s] 新增 f
t = input().strip()  # 要找的目標
if t not in food: print("No")  # 如果 t 不在 food 之中，印出 No
else:  # 如果 t 在 food 之中，將食物名稱排序後印出
    for f in sorted(food[t]):
        print(f)

ZeroJudge 解題筆記：e838. P5. 炸彈超人(Bombs)

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



ZeroJudge 題目連結：e838. P5. 炸彈超人(Bombs)

解題想法

這題先將炸彈的位置儲存起來，等讀取完整個地圖資料之後再處理會比較方便。

Python 程式碼

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

n = int(input())  # 地圖為 n*n
bomb = []  # 炸彈位置
grid = []  # 地圖
for i in range(n):  # 讀取 n 行資料
    row = list(input().strip())  # 一行資料，轉成串列
    grid.append(row)  # row 加入 grid
    for j, ch in enumerate(row):  # 依序由 row 讀取字元 ch
        if ch == "*": bomb.append((i, j))  # ch 是炸彈，位置 (i, j) 加入 bomb
for i, j in bomb:  # 讀取炸彈位置 (i, j)，將十字方向上的位置皆改成 *
    for c in range(j, -1, -1): grid[i][c] = "*"
    for c in range(j, n, 1): grid[i][c] = "*"
    for r in range(i, -1, -1): grid[r][j] = "*"
    for r in range(i, n, 1): grid[r][j] = "*"
for row in grid:  # 由 grid 依序讀取整列的資料
    print("".join(row))  # 將 row 接成字串再印出

ZeroJudge 解題筆記：e837. P4. 字母排列 (Letters)

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



ZeroJudge 題目連結：e837. P4. 字母排列 (Letters)

解題想法

這題的說明不精準，題目中說要找按照順序排列的最長字串，實際上是要找按照順序且相鄰字母的最長字串。

Python 程式碼

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

import sys

for s in sys.stdin:
    s = s.strip()  # 去掉最後面的 \0
    now = s[0]  # 目前符合要求的最長字串，先放入 s[0]
    ans = ""  # 答案
    for c in s[1:]:  # 依序讀取 s[1] ~ s[-1]
        if ord(c) == ord(now[-1])+1: now += c # 如果 c 是 now[-1] 的下一個字母，將 c 接到 now 之後
        else:  # 如果 c 不是 now[-1] 的下一個字母
            if len(now) >= len(ans): ans = now  # 如果 now 的長度大於等於 ans 的長度，更新 ans
            now = c  # 更新 now
    if len(now) >= len(ans): ans = now  # 最後要再檢查一次 now 是否比 ans 長
    print(f"{len(ans):d} {ans:s}")  # 印出答案

ZeroJudge 解題筆記：e836. P3. 數字統計 (Counting)

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



ZeroJudge 題目連結：e836. P3. 數字統計 (Counting)

解題想法

這題用字典計數比較方便。

Python 程式碼

可以使用 collections 函式庫的 Counter，這是專門用來計算數量的工具，輸入一個可以迭代的物件，回傳物件中各項資料的數量。使用時間約為 45 ms，記憶體約為 3.8 MB，通過測試。

import sys
from collections import Counter

for line in sys.stdin:
    n = int(line)  # n 個數字
    rs = list(map(int, input().split()))  # 讀取一行數字
    cnt = Counter(rs)  # 計數器
    print(len(cnt))  # 印出不同的數字數量
    imax = max(cnt.values())  # 相同數字最大數量
    if imax < 2: print("NO")  # 沒有重複的數字，印出 NO
    else:  # 否則依照出現順序印出數字
        tmp = []  # 暫存用的串列
        for r in rs:  # 依序由 rs 讀取數字 r
            if cnt[r] == imax and r not in tmp:  # 如果 r 的數量最多而且不在 tmp 之中
                tmp.append(r)  # r 加入 tmp
        print(*tmp)  # 印出 tmp

由於 Counter 的 key 值會依照輸入的物件資料順序排序，上方程式第 11 到 16 行可以改為以下這行，使用時間約為 37 ms，記憶體約為 3.8 MB，通過測試。

else: print(*[key for key, val in cnt.items() if val == imax])