ZeroJudge 解題筆記：m583. 精靈王國 (Kingdom)

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



ZeroJudge 題目連結：m583. 精靈王國 (Kingdom)

解題想法

我用一層 for 迴圈掃過所有的傳送點，如果這個點已經走過就找下一個點，如果還沒有走過就將它歸零；接下來再用一層 while 迴圈，不斷地找傳送到的下一個點 nxt，直到 nxt 等於 0 為止。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 16.3 MB，通過測試。

import sys

for line in sys.stdin:
    k = int(line)  # k 個傳送點
    imax = 0  # 同一個王國中最多的傳送點數量
    arr = [0] + list(map(int, input().split()))  # 傳送點資料，開頭多一個 0，改成 0 代表已走訪
    for i in range(1, k+1):  # 依序走訪傳送點 1 ~ k
        if arr[i] == 0: continue  # 如果 arr[i] 等於 0，找下一個點
        cnt = 0  # 同一個王國中的傳送點數量
        nxt = arr[i]  # 下一個位置
        arr[i] = 0  # 已走訪 arr[i]
        while nxt != 0:  # 繼續執行直到 nxt 等於 0
            cnt += 1  # cnt 加 1
            tmp = arr[nxt]  # 暫存 arr[nxt] 到 tmp
            arr[nxt] = 0  # 已走訪 arr[nxt]
            nxt = tmp  # 更新 nxt
        imax = max(imax, cnt)  # 更新 imax
    print(imax)

ZeroJudge 解題筆記：m582. 書房 (Study)

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



ZeroJudge 題目連結：m582. 書房 (Study)

解題想法

用一個陣列儲存答案，索引值是碎片編號減 1，內容為所在書架編號。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # n 個書架，m 張碎片
    ans = [0]*m  # 儲存答案用的串列，索引值是碎片編號減 1，內容為所在書架編號
    for i, a in enumerate(map(int, input().split()), start=1):  # 依序讀取各書架的碎片編號
        if a != 0: ans[a-1] = i  # 如果 a 不等於 0，設定 ans
    print(*ans)

C++ 程式碼

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

#include <cstdio>
using namespace std;

int main() {
    int n, m;  // n 個書架，m 張碎片
    while(scanf("%d %d", &n, &m) != EOF) {
        int ans[m];  // 儲存答案用的串列，索引值是碎片編號減 1，內容為所在書架編號
        for(int i=1; i<=n; i++) {  // 依序讀取各書架的碎片編號
            int a; scanf("%d", &a);
            if (a != 0) ans[a-1] = i;  // 如果 a 不等於 0，設定 ans
        }
        for(int i=0; i<m; i++) {
            printf("%d", ans[i]);
            if (i == m-1) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}

ZeroJudge 解題筆記：m581. 狼人殺 (Werewolves)

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



ZeroJudge 題目連結：m581. 狼人殺 (Werewolves)

解題想法

不斷讀取要淘汰的人編號，直到讀到 0、無解或是沒有狼人為止。特別容易出錯的地方在於，如果無解，仍然需要讀完測資，不能直接 break。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    arr = [-2] + list(map(int, input().split()))  # 每個人的身份，配合編號開頭多一項，-2 為已淘汰
    werewolves = sum([a == -1 for a in arr])  # 狼人數量
    solve = True  # 是否有解
    while True:  # 不斷讀取要淘汰的人
        k = int(input())  # 要淘汰的人編號
        if k == 0: break  # 讀到 0 中止迴圈
        elif arr[k] == -2:  # 如果 k 號已淘汰
            solve = False  # 無解，但是要讀完資料，不能 break
        else:
            if arr[k] == -1: werewolves -= 1  # 如果 k 號是狼人，數量減 1
            arr[k] = -2  # k 號淘汰
    if not solve: print("Wrong")  # 無解，印出 Wrong
    elif werewolves == 0: print("Townsfolk")  # 好人陣營獲勝
    else: print("Werewolves")  # 狼人陣營獲勝

ZeroJudge 解題筆記：m398. 超市排隊 (Supermarket)

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



ZeroJudge 題目連結：m398. 超市排隊 (Supermarket)

解題想法

依序計算三個櫃枱所需時間，再更新最短時間即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    abc = list(map(int, line.split()))  # 三個櫃枱的人數
    idx, imin = 0, float('inf')  # 櫃枱編號及所需最短時間
    for i, n in enumerate(abc, start=1):  # 依序讀取三個櫃枱的人數
        arr = list(map(int, input().split()))  # 每個顧客購買的商品數量
        t = 2 * (n - 1)  # 顧客前進所需時間
        for d in arr: t += 3*d # 依序讀取商品數量並更新時間
        if t < imin:  # 如果 t 小於 imin
            idx = i; imin = t  # 更新 idx 及 imin
    print(idx, imin)

ZeroJudge 解題筆記：m397. 烤肉 (BBQ)

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



ZeroJudge 題目連結：m397. 烤肉 (BBQ)

解題想法

注意，其中一種可能是 0 串。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, m, x, y = map(int, line.split())  # 共 n 元，m 串，單價 x 元、y 元
    solve = False  # 是否有解
    for i in range(m+1):  # 依序檢查 0 ~ m 串
        j = m-i  # 另一種有 m-i 串
        if i*x + j*y == n:  # 有解
            solve = True; print(i, j); break
    if not solve: print("-1 -1")

ZeroJudge 解題筆記：l925. P.8 值班警衛 (Guard)

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



ZeroJudge 題目連結：l925. P.8 值班警衛 (Guard)

解題想法

産生警衛的組合之後立刻檢查這個組合是否能覆蓋所有的邊，不需要把所有組合都儲存起來，可以少用一點記憶體。

Python 程式碼

寫法1，産生所有可能的警衛組合，先存入串列中，最後才檢查每個組合是否能覆蓋所有的邊。最後一筆測資超出記憶體上限。

import sys

def sove(N, M, edges):  # 輸入節點數量N、邊的數量M、邊 edges
    # 産生所有可能的組合
    all_combs = []
    for i in range(1 << N):  # i = 0 ~ 2**N - 1
        comb = []  # 組合
        for j in range(N):  # j = 0 ~ N-1
            if (i >> j) & 1:  # 如果 i 向右移 j 位等於 1，comb 加入 j
                comb.append(j + 1)  # 因為編號從 1 開始
        all_combs.append(comb)  # comb 加入 all_combs
    # 找到可以複蓋所有邊而且數量最少的組合
    imin = N  # 最少的數量，預設為所有的節點數量N
    for comb in all_combs:  # 依序從 all_combs 取出 comb
        covered = True  # 是否覆蓋所有的邊，預設為 True
        for u, v in edges:  # 從 edges 依序讀取每個邊的端點 u, v
            if u not in comb and v not in comb:  # 如果 u, v 都不在 comb 之中
                covered = False; break  # comb 不能覆蓋所有的邊，中止迴圈
        if covered: imin = min(imin, len(comb))  # 如果 comb 可以覆蓋所有的邊，更新 imin
    return imin  # 回傳 imin

for line in sys.stdin:
    N, M = map(int, line.split())
    edges = [list(map(int, input().split())) for _ in range(M)]
    print(min_guards(N, M, edges))

寫法2，由寫法1修改而成，産生警衛的組合之後立刻檢查這個組合是否能覆蓋所有的邊，可以少用一點記憶體。使用時間約為 2 s，記憶體約為 3.3 MB，通過測試。

import sys

def solve(N, M, edges):  # 輸入節點數量N、邊的數量M、邊 edges
    imin = N  # 最少的數量，預設為所有的節點數量N
    for i in range(1 << N):  # i = 0 ~ 2**N - 1
        comb = []  # 組合
        for j in range(N):  # j = 0 ~ N-1
            if (i >> j) & 1:  # 如果 i 向右移 j 位等於 1，comb 加入 j
                comb.append(j + 1)  # 因為編號從 1 開始
        covered = True  # 是否覆蓋所有的邊，預設為 True
        for u, v in edges:  # 從 edges 依序讀取每個邊的端點 u, v
            if u not in comb and v not in comb:  # 如果 u, v 都不在 comb 之中
                covered = False; break  # comb 不能覆蓋所有的邊，中止迴圈
        if covered: imin = min(imin, len(comb))  # 如果 comb 可以覆蓋所有的邊，更新 imin
    return imin  # 回傳 imin

for line in sys.stdin:
    N, M = map(int, line.split())
    edges = [list(map(int, input().split())) for _ in range(M)]
    print(solve(N, M, edges))

ZeroJudge 解題筆記：l924. P.7 搜集寶藏 (Treasure)

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



ZeroJudge 題目連結：l924. P.7 搜集寶藏 (Treasure)

解題想法

但是這題的記憶體限制很嚴格，如果先將所有格子的資料存進二維陣列，不論是用 Python 或 C++ 記憶體都不夠。如果改用滾動陣列節省記憶體，Python 還是無法通過，C++ 勉強可以過關。

Python 程式碼

寫法1，先將所有格子的資料存進二維串列。但是這題的記憶體限制很嚴格，我用 Python 解題在第 2、5、8、9、12、18 筆測資記憶體爆掉。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 地圖 n*m
    grid = [list(map(int, input().split())) for _ in range(n)]  # 讀取地圖資料
    for i in range(1, n):  # 處理第 0 欄
        grid[i][0] += grid[i-1][0]
    for j in range(1, m):  # 處理第 0 列
        grid[0][j] += grid[0][j-1]
    for i in range(1, n):  # 處理 grid[1][1] ~ grid[n-1][m-1]
        for j in range(1, m):
            grid[i][j] += max(grid[i-1][j], grid[i][j-1])
    print(grid[n-1][m-1])  # 答案在 grid[n-1][m-1]

寫法2，用滾動陣列節省記憶體，結果第2筆測資就超時。

import sys

for line in sys.stdin:
    n, m = map(int, line.split())  # 地圖 n*m
    pre = list(map(int, input().split()))  # 讀取第 0 列地圖資料
    for j in range(1, m):  # 處理第 0 列
        pre[j] += pre[j-1]
    for _ in range(1, n):  # 處理第 1 ~ n-1 列
        cur = list(map(int, input().split()))  # 讀取一列地圖資料
        cur[0] += pre[0]  # 處理第 0 欄
        for j in range(1, m):  # 依序更新第 1 ~ m-1 欄
            cur[j] += max(pre[j], cur[j-1])
        pre, cur = cur, pre  # 交換 pre, cur 的資料
    print(pre[m-1])  # 答案在 pre[n-1][m-1]

ZeroJudge 解題筆記：l922. P.5 古堡長廊 (Castle)

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



ZeroJudge 題目連結：l922. P.5 古堡長廊 (Castle)

解題想法

我用字典儲存英文單字對應的整數字元。讀取畫的字串及年份時，將年份轉成整數與單字對應的字元組成 tuple 或 pair，儲存到 list 或 vector 之中，依照年份排序，再將排序後的字元組成答案。

Python 程式碼

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

import sys

num = {"ONE": '1', "TWO": '2', "THREE": '3', "FOUR": '4', "FIVE": '5',
       "SIX": '6', "SEVEN": '7', "EIGHT": '8', "NINE": '9'}
for line in sys.stdin:
    n = int(line)  # n 幅畫
    data = []  # 資料
    for _ in range(n):  # 讀取 n 筆資料
        s, y = input().split()  # 字串 s，年份 y
        data.append((int(y), num[s]))  # y 轉成整數，s 代入 num 換成字元
    data.sort()  # 依照年份排序
    print(''.join([m for _, m in data]))  # 將字元組成字串再印出

ZeroJudge 解題筆記：l921. P.4 草圖 (Sketch)

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



ZeroJudge 題目連結：l921. P.4 草圖 (Sketch)

解題想法

因為這題要檢查的範圍比較大，要加兩層題目沒有用到的符號作為哨兵，避免走訪時出界。

Python 程式碼

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

import sys

# 右、右下、下、左下、左、左上、上、右上，距離2格，距離1格
two = ((0, 2), (2, 2), (2, 0), (2, -2), (0, -2), (-2, -2), (-2, 0), (-2, 2))
one = ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1))
sym = ('-', '\\', '|', '/', '-', '\\', '|', '/')

for line in sys.stdin:
    R = int(line)  # 圖形 (2*R - 1) * (2*R - 1)，要加上點之間的格子
    grid = [['#']*(2*R - 1) + ['!']*2 for _ in range(2*R - 1)]  # 圖形先填入 #，最後以 ! 作為哨兵
    grid += [['!']*(2*R +1), ['!']*(2*R +1)]  # 最下方加 2 列 ! 作為哨兵
    N = int(input())  # N 個點
    ps = []  # 點的位置
    for _ in range(N):  # 讀取 N 行資料
        r, c = map(int, input().split())  # 座標 (r, c)
        r *= 2; c *= 2  # 配合 grid 的維度要乘以 2
        ps.append((r, c))  # (r, c) 加入 ps
        grid[r][c] = '&'  # grid[r][c] 標記成 &
    for r, c in ps:  # 從 ps 依序取出點的座標
        for i in range(8):  # 8 方向檢查
            nr, nc = r+two[i][0], c+two[i][1]  # 要檢查的座標 (nr, nc)，距離 2 格
            if grid[nr][nc] == '&':  # 如果 grid[nr][nc] 是 &
                cr, cc = r+one[i][0], c+one[i][1]  # 距離 1 格的位置
                if grid[cr][cc] == '#':  # 如果 grid[cr][cc] 還沒有標記
                    grid[cr][cc] = sym[i]
                elif ((i == 3 or i == 7) and grid[cr][cc] == '\\') or \
                     ((i == 1 or i == 5) and grid[cr][cc] == '/'):
                    grid[cr][cc] = 'X'
    for row in grid[:2*R - 1]: print(''.join(row[:2*R - 1]))

ZeroJudge 解題筆記：fl920. P.3 建築倒塌 (Collapse)

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



ZeroJudge 題目連結：fl920. P.3 建築倒塌 (Collapse)

解題想法

這題可以用陣列儲存建築物狀態，不斷檢查每棟建築物是否需要更新狀態，直到沒有再更新狀態為止。如果改用集合儲存還要檢查的建築物位置，速度會更快一些。

Python 程式碼

寫法1，不斷檢查每棟建築物是否需要更新狀態，直到沒有再更新狀態為止。使用時間約為 0.3 s，記憶體約為 3.4 MB，通過測試。

import sys

def solve(s):  # 輸入建築物狀態
    n = len(s)  # 建築物數量
    if n <= 1:  # 特例，將 s 組成字串再印出，跳出函式
        print(''.join(s)); return
    cont = True  # 是否需要繼續更新狀態
    while cont:
        t = s[:]  # 暫存建築物狀態
        cont = False  # 先改成 False
        for i in range(n):  # 依序掃過每棟建築物
            if i == 0 and s[i] == 'X' and s[i+1] == 'L':  # 最左側建築物被右側建築物向左壓
                t[i] = 'L'; cont = True
            elif i == n-1 and s[n-1] == 'X' and s[n-2] == 'R':  # 最右側建築物被左側建築物向右壓
                t[n-1] = 'R'; cont = True
            elif 1 <= i <= n-2:  # 中間的建築物
                if s[i-1] == 'R' and s[i+1] == 'L':  # 左側向右倒，右側向左倒，中間不動
                    pass
                elif s[i-1] == 'R' and s[i] == 'X':  # 左側向右倒，中間原來還沒倒
                    t[i] = 'R'; cont = True
                elif s[i+1] == 'L' and s[i] == 'X':  # 右側向左倒，中間原來還沒倒
                    t[i] = 'L'; cont = True
        s = t[:]  # t 的資料存到 s
    print(''.join(s))  # 將 s 組成字串再印出

for arr in sys.stdin:
    arr = list(arr.strip())  # 建築物狀態
    solve(arr)

ZeroJudge 解題筆記：f934. 消失的二十年

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



ZeroJudge 題目連結：f934. 消失的二十年

解題想法

這是 l919. P.2 珠寶交易 (Jewel) ) 簡化題，只要計算一次買賣的最大獲利。

Python 程式碼

使用時間約為 1.2 s，記憶體約為 78.3 MB，通過測試。

buy, profit = float('inf'), 0  # 最低買價，利潤
for p in map(int, input().split()):  # 讀取每天的價格
    buy = min(buy, p)  # 更新最低買價
    profit = max(profit, p - buy)  # 更新最大利潤
print(profit)

使用時間約為 0.8 s，記憶體約為 78.4 MB，通過測試。

buy, profit = float('inf'), 0  # 最低買價，利潤
for p in map(int, input().split()):  # 讀取每天的價格
    if p < buy: buy = p  # 更新最低買價
    if p - buy > profit: profit = p - buy  # 更新最大利潤
print(profit)

ZeroJudge 解題筆記：l919. P.2 珠寶交易 (Jewel)

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



ZeroJudge 題目連結：l919. P.2 珠寶交易 (Jewel)

解題想法

這題理論上用貪心法就能解，有通過範例測資，但是無法送出解答。

Python 程式碼

無法送出解答。

import sys

for line in sys.stdin:
    n = int(line)  # n 天
    buy = float('inf')  # 最低買價，預設為正無窮大
    profit = 0  # 最大利潤，預設為 0
    best_buy_dat, best_sell_day = 0, 0  # 最佳買入、𧶠出時機
    buy_day = 0  # 買入時機
    for i, p in enumerate(map(int, input().split()), start=1):  # 第 i 天，價格 p
        if p < buy:  # 如果當天的價格小於 buy，更新 buy 及 buy_day
            buy = p; buy_day = i
        elif p - buy > profit:  # 價差大於 profit
            profit = p - buy  # 更新 profit
            best_sell_day = i  # 更新 sell_day
            best_buy_day = buy_day  # 更新 best_buy_day
    if profit > 0: print(best_buy_day, best_sell_day)
    else: print(-1)

ZeroJudge 解題筆記：l918. P1. 彈珠汽水 (Soda)

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



ZeroJudge 題目連結：l918. P1. 彈珠汽水 (Soda)

解題想法

這題有一個陷阱，如果 $N = 1$，每喝一瓶汽水就可以再換一瓶新的汽水，如果寫 while 迴圈的條件時只考慮是否還有沒喝的汽水，這樣會變成無窮迴圈。

Python 程式碼

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

m, n, k = map(int, input().split())  # m 瓶彈珠汽水，n 個瓶子再換一瓶汽水，想要喝到 k 瓶
t, b = 0, 0  # 總瓶數，空瓶數
while m > 0 and t < k:  # 如果還有沒喝的汽水而且還沒有喝到想要的瓶數
    t += m; b += m  # 更新 t, b，加上 m
    m = b//n  # 用空瓶換汽水
    b %= n  # 剩下的空瓶
print("YES" if t >= k else "NO")  # 依照 t 是否大於等於 k 印出答案

ZeroJudge 解題筆記：k931. P8. 切割蜂蜜 (Honey)

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



ZeroJudge 題目連結：k931. P8. 切割蜂蜜 (Honey)

解題想法

這題有 3 個重點：

1. 要設計儲存六角形蜂巢資料的方式，我是用二維串列，偶數列的欄位為 1, 3, 5, ...，奇數列的欄位為 0, 2, 4, ...，這個寫法的優點是讀取資料時索引值比較好寫，缺點是會浪費接近一半的二維串列空間。
2. 用動態規畫計算從左到右切割到每一格時最小的累積損失量，取這一格的左上、左側、左下之中的最小值，再加上這格原來的值。
3. 為了避免檢查邊界值要寫一堆 if，我選擇在四周 (C++) 或是最右側、最下方 (Python) 加上正無窮大的值當作哨兵，缺點是要多花一點記憶體。

經過測試，這個寫法在目前通過測試的人當中，C++ 及 Python 使用的時間都最短，可能其他人都很認真地檢查是否出界吧！

Python 程式碼

使用時間約為 1.1 s，記憶體約為 26.7 MB，通過測試。

import sys

oo = float('inf')
for line in sys.stdin:
    H, W = map(int, line.split())  # 晶格的高與寬
    grid = [[-1]*(2*W+2) for _ in range(H)]  # 晶格 (H+1)*(2*W+2)
    grid.append([oo]*(2*W+2))  # 最下方補一列 oo
    for r in range(H):  # 讀取 H 行資料
        row = list(map(int, input().split()))
        if r%2 == 0:  # 如果是偶數列，欄位為 1, 3, 5, ..., 2*W - 1
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i+1] = v
            grid[r][2*W] = grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
        else:  # 如果是奇數列，欄位為 0, 2, 4, ..., 2*W
            for i, v in enumerate(row):  # 索引值 i，數值 v
                grid[r][2*i] = v
            grid[r][2*W+1] = oo  # 最後面補上 oo 當作哨兵
    # 動態規畫，grid[r][c] 改成到這格損失的值，加上左上、左側、左下最小值
    for c in range(2, 2*W+1):  # 依序掃過第 2 ~ 2*W 欄
        if c%2 == 0:  # 如果是偶數欄，列為 1, 3, 5, ...
            for r in range(1, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
        else:  # 如果是奇數欄，列為 0, 2, 4, ...
            for r in range(0, H, 2):
                grid[r][c] += min(grid[r-1][c-1], grid[r][c-2], grid[r+1][c-1])
    # 找出答案，在每一列的最後一格，不含 oo
    ans = oo  # 答案預設為最大值
    for r in range(H):  # 依序掃過每一列
        if r%2 == 0: ans = min(ans, grid[r][2*W-1])  # 如果是偶數列
        else: ans = min(ans, grid[r][2*W])   # 如果是奇數列
    print(ans)

ZeroJudge 解題筆記：k930. P7. 興建圍籬 (Fence)

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



ZeroJudge 題目連結：k930. P7. 興建圍籬 (Fence)

解題想法

這題我用 BFS，但是在 Python 不論是用 deque 或 list 都太慢，在 C++ 用 queue 或 vector 都要跑 0.1 s。

Python 程式碼

寫法1，用 deque 儲存待走訪的佇列，但是速度不夠快，只能通過 60% 的測資。

import sys
from collections import deque

for line in sys.stdin:
    H, W = map(int, line.split())  # 地圖 H*W
    grid = [list(map(int, input().split())) for _ in range(H)]  # 讀取地圖
    num = 1  # 花地編號
    ans = []  # 答案
    for i in range(H):  # 依序掃過每一格
        for j in range(W):
            if grid[i][j] == 1:  # 如果此格是花地
                tot = 0  # 這區的圍籬數量
                que = deque([(i, j)])  # 待走訪的佇列
                num += 1  # 編號加 1
                while que:  # 如果 que 還有資料繼續執行
                    r, c = que.popleft()  # 從 que 開頭讀取並移除資料
                    grid[r][c] = num  # 設定 grid[r][c] 的編號
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                        nr, nc = r+dr, c+dc  # 要檢查的格子 (nr, nc)
                        if 0 <= nr < H and 0 <= nc < W:  # 如果 nr, nc 沒有出界
                            if grid[nr][nc] == 1:  # 如果是還沒有編號的花地
                                grid[nr][nc] = num  # 設定編號
                                que.append((nr, nc))  # (nr, nc) 加入 que
                            elif grid[nr][nc] == 0:  # 如果是空地
                                tot += 1  # (r, c) 需要加一片圍籬
                ans.append(tot)  # 將 tot 加入 ans
    print(*sorted(ans))  # 將 ans 排序後印出

ZeroJudge 解題筆記：k926. P3. 錯字校正 (Correction)

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



ZeroJudge 題目連結：k926. P3. 錯字校正 (Correction)

解題想法

這題測資不大，按照題目的要求模擬替換字母的過程，最後再計算原來的字串與替換後的字串不同的字母數量即可。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = list(line.strip())  # 輸入的字串
    t = list(input().strip())  # 正確的字串
    n = int(input())  # 修正次數
    for _ in range(n):  # 讀取 n 行修正資料
        x, y = list(input().split())  # x 替換成 y
        for i in range(len(s)):  # 依序由 s 讀取字元
            if s[i] == x: s[i] = y  # 如果 s[i] 是 x 則換成 y
    diff = sum([a != b for a, b in zip(s, t)])  # 計算 s, t 之中對應位置不相同的字母數量
    print(diff)

ZeroJudge 解題筆記：k925. P2. 海底探險 (Adventure)

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



ZeroJudge 題目連結：k925. P2. 海底探險 (Adventure)

解題想法

這題我沒有想到比較簡潔的寫法，只能按照題目的敘述模擬烏龜的運動過程，程式碼寫起來很長。

Python 程式碼

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

import sys

def solve(L, T, hs):
    rem = T-1  # 剩下的探索時間，先減 1
    hmax = max(hs)  # 最高區塊高度
    imax = hs.index(hmax)  # 最高區塊位置
    t1 = hmax - hs[0]  # 上升到最高區塊高度需要的時間
    rem -= t1  # 更新 rem
    if rem <= 0: return 1  # 已經用完探索時間，還在起點區塊，回傳 1
    t2 = imax  # 向右游到最高區塊需要的時間
    rem -= t2  # 更新 rem
    if rem <= 0: return T-t1  # 向右游到的區塊 T-1-t1+1
    if imax == L-1:  # 如果游到最右邊
        hmin = min(hs[1:L-1])  # hs[1] ~ hs[L-2] 最低點
        imin = L-2 - hs[1:L-1][::-1].index(hmin)  # hs[1] ~ hs[L-2] 最低點位置
        t3 = L-1-imin  # 向左游到 imin 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return L-(rem+t3)  # 游到區塊 2 前時間就到了
        return imin + 1  # 可以游到區塊 imin + 1
    else:  # 不是游到最右邊
        hmax2 = max(hs[imax+1:])  # imax 右側最高的區塊高度
        imax2 = hs[imax+1:].index(hmax2) + imax + 1  # hmax2 的位置
        t3 = imax2-imax  # 向右游到 imin2 需要的時間
        rem -= t3  # 更新 rem
        if rem <= 0: return imax+rem+t3+1  # 游到 imax2 + 1 前時間就到了
        return imax2 + 1  # 可以游到 imax2 + 1

for line in sys.stdin:
    L = int(line)  # L 個區塊
    hs = list(map(int, input().split()))  # 各區塊高度
    T = int(input())  # 探索時間
    print(solve(L, T, hs))

ZeroJudge 解題筆記：k924. P1. 數字結合 (Combination)

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



ZeroJudge 題目連結：k924. P1. 數字結合 (Combination)

解題想法

先將兩個字串合併，再計算奇數位數和、偶數位數和，如果兩者的差是 11 的倍數印出 Yes，反之印出 No。

Python 程式碼

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

import sys

for line in sys.stdin:
    s = "".join(line.split())  # 兩個整數合併
    odd, even = 0, 0  # 奇數位數和，偶數位數和
    for i, c in enumerate(s):  # 計算奇數位數和、偶數位數和
        if i%2 == 1: odd += int(c)
        else: even += int(c)
    dif = abs(odd - even)
    print("Yes" if dif%11 == 0 else "No")

ZeroJudge 解題筆記：k866. 8.運送隕石 (Delivery)

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



ZeroJudge 題目連結：k866. 8.運送隕石 (Delivery)

解題想法

我用 priority queue 儲存隕石重量，每次處理最重的隕石，將重量除以 2 之後再放回 priority queue 之中，處理 m 次之後，priority queue 最上面的資料就是答案。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 22.2 MB，通過測試。

import sys, math, heapq

for line in sys.stdin:
    n, m = map(int, line.split())  # n 顆隕石，m 顆炸彈
    ws = []  # 每顆隕石的重量，為了將最大值放上面，要加負號
    for w in map(int, input().split()): heapq.heappush(ws, -w)
    for _ in range(m):  # 執行 m 次
        w = -heapq.heappop(ws)  # 取出最大值
        h = w/2  # 除以2
        heapq.heappush(ws, -h)  # 加入兩個 -h
        heapq.heappush(ws, -h)
    print(math.ceil(-ws[0]))

ZeroJudge 解題筆記：k865. 7.幼稚園 (Kindergarten)

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



ZeroJudge 題目連結：k865. 7.幼稚園 (Kindergarten)

解題想法

我是用兩層的 for 迴圈，先讀取第 i 個人的身高 h，裡面再用兩個 for 迴圈，分別向左、向右找較高的人，取向左、向右交換次數較少者。這樣的寫法效率不夠高，Python 過不了，C++ 可以通過測試。

Python 程式碼

速度太慢，只能通過 40% 的測資，需要再找到更有效率的寫法。

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    hs = list(map(int, input().split()))  # 身高
    ans = 0  # 交換次數
    for i, h in enumerate(hs):  # 讀取第 i 個人的身高 h
        toleft = 0  # 向左找較高的人數
        for j in range(i-1, -1, -1):
            if hs[j] > h: toleft += 1
        toright = 0  # 向右找較高的人數
        for j in range(i+1, n):
            if hs[j] > h: toright += 1
        if toleft <= toright: ans += toleft  # 取向左、向右交換次數較少者
        else: ans += toright
    print(ans)

ZeroJudge 解題筆記：k854. P8.簡易數織 (Nonogram)

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



ZeroJudge 題目連結：k854. P8.簡易數織 (Nonogram)

解題想法

這題我試著用 dp 計算可能的組合，但是最後一筆測資極大，用 Python 最後一筆測資超時。後來我把題目丢到 Gemini 2.0 Flash，它提供了一個數學化的解法，才能在時限內順利解出來。

Python 程式碼

最後一筆測資超時。

import sys

def solve(w, n, arr):
    mod = 10**9 + 7  # 要取餘數用的整數
    imin = sum(arr) + n - 1  # 黑色區塊總和 + 至少需要的空格數量
    if imin > w:  # 需要的格子數大於 w
        print(0); return  # 印出 0，跳出函式
    dp = [[0]*(n+1) for _ in range(w+1)]  # dp[i][j] 填到第 i 格時放入第 j 段黑色區塊
    for i in range(w+1): dp[i][0] = 1  # 初始化，填滿 0 ~ w 格、沒有黑色區塊，只有一種方式
    for i in range(1, w+1):  # 填滿 1 ~ w 格
        for j in range(1, n+1):  # 放入第 j 段黑色區塊
            block = arr[j-1]  # 黑色區塊長度
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod  # 不放這個黑色區塊
            if i >= block:  # 可以放入這個黑色區塊
                if j == 1:  # 第 1 個黑色區塊，前面可以不需要是空格
                    dp[i][j] = (dp[i][j] + dp[i-block][j-1]) % mod
                elif i >= block+1:  # 不是第 1 個黑色區塊，前面必須是空格
                    dp[i][j] = (dp[i][j] + dp[i-block-1][j-1]) % mod
    print(dp[w][n]); return

for line in sys.stdin:
    w, n = map(int, line.split())  # w 個格子，n 段連續的黑色區塊
    arr = list(map(int, input().split()))  # 各段連續黑色區塊的長度
    solve(w, n, arr)

ZeroJudge 解題筆記：l919. P.2 珠寶交易 (Jewel)

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



ZeroJudge 題目連結：l919. P.2 珠寶交易 (Jewel)

解題想法

這題理論上用貪心法就能解，有通過範例測資，但是無法送出解答。

Python 程式碼

無法送出解答。

import sys

for line in sys.stdin:
    n = int(line)  # n 天
    buy = float('inf')  # 最低買價，預設為正無窮大
    profit = 0  # 最大利潤，預設為 0
    best_buy_dat, best_sell_day = 0, 0  # 最佳買入、𧶠出時機
    buy_day = 0  # 買入時機
    for i, p in enumerate(map(int, input().split()), start=1):  # 第 i 天，價格 p
        if p < buy:  # 如果當天的價格小於 buy，更新 buy 及 buy_day
            buy = p; buy_day = i
        elif p - buy > profit:  # 價差大於 profit
            profit = p - buy  # 更新 profit
            best_sell_day = i  # 更新 sell_day
            best_buy_day = buy_day  # 更新 best_buy_day
    if profit > 0: print(best_buy_day, best_sell_day)
    else: print(-1)

ZeroJudge 解題筆記：k853. P7.直播趕場 (Live)

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



ZeroJudge 題目連結：k853. P7.直播趕場 (Live)

解題想法

採用類似〈APCS實作題2016年3月第3題：線段覆蓋長度〉計算重疊線段厚度的寫法，讀到開始直播時刻厚度加 1，讀到直播結束時刻厚度減 1；假設目前檢查的時間端點為 [start, end+1]，若厚度小於等於螢幕數量，可以觀看的時數加上厚度乘以端點距離，若厚度大於螢幕數量，可以觀看的時數加上螢幕數量乘以端點距離。

Python 程式碼

使用時間約為 1 s，記憶體約為 25.1 MB，通過測試。

import sys

for line in sys.stdin:
    n, s = map(int, line.split())  # n 個螢幕，s 個直播
    cast = []  # 直播開始、結束時刻，開始厚度加 1，結束厚度減 1
    for _ in range(s):  # 讀取 s 行資料
        start, end = map(int, input().split())
        cast += [(start, 1), (end+1, -1)]  # 結束時刻要加 1
    cast.sort()  # 排序
    last = 0  # 正在檢查的範圍開始時刻
    thick = 0  # 厚度，正在直播的頻道數量
    ans = 0  # 答案，可以觀看的直播總時數
    for p, t in cast:  # 依序讀取時刻及厚度變化
        if thick > 0:  # 如果目前直播頻道數量大於 0
            ans += min(thick, n)*(p-last)  # 更新 ans，加上 thick, n 較小值乘以 p-last
        thick += t  # 更新厚度
        last = p  # 更新 last
    print(ans)

ZeroJudge 解題筆記：k851. P5.辨識碼 (Identification)

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



ZeroJudge 題目連結：k851. P5.辨識碼 (Identification)

解題想法

我是用字串分割的方式，按照題目要求的長度分割字串，將每個子字串的數字加總存入集合 isum 之中，如果 isum 之中已經有同樣的值就是國民，不需要再檢查後面的子字串。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)  # 分組數字 x 個
    n = sys.stdin.readline().strip()  # 身分證號
    m = len(n)  # 長度
    isum = set()  # 各組的加總
    flag = False  # 是否為國民，預設為 False
    for i in range(m-x, -1, -x):  # 從最後往前取長度為 x 的子字串
        s = n[i:i+x]  # 子字串
        tot = sum([int(c) for c in s])  # 加總
        if tot in isum:  # 如果 isum 之中已經有 tot
            flag = True; break  # 是國民，中止迴圈
        isum.add(tot)  # tot 加入 isum
    print("Yes" if flag else "No")  # 印出答案

ZeroJudge 解題筆記：k849. P3.骨牌 (Domino)

作者：王一哲
日期：2025年5月8日



ZeroJudge 題目連結：k849. P3.骨牌 (Domino)

解題想法

這題是有向圖，我用集合 child 儲存子節點編號，用字典 nxt 儲存每個節點的子節點編號，讀取 n 行資料存入 child 及 nxt，再掃瞄一輪找出根節點（第一張牌），最後用一個 while 迴圈第根節點開始掃過所有的節點並將節點編號存入串列 ans。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 組資料，n 張牌
    child = set()  # 不是第一張牌的編號
    nxt = dict()  # 下一張牌的編號
    for _ in range(n):  # 讀取 n 行資料，u 的下一張是 v
        u, v = map(int, input().split())
        child.add(v)
        nxt[u] = v
    start = 0  # 第一張牌
    for u in nxt.keys():  # 從 nxt 的 keys 之中找第一張牌
        if u not in child:  # 只有一個 u 不在 child 之中
            start = u; break  # 找到就可以中止迴圈
    ans = [start]  # 先將 start 加入 ans
    while nxt[ans[-1]] != -1:  # 如果 ans 最後一項的下一張不是 -1 繼續執行
        ans.append(nxt[ans[-1]])  # 將找到的牌加入 ans
    print(*ans)

ZeroJudge 解題筆記：k848. P2.卡牌評分 (Card)

作者：王一哲
日期：2025年5月7日



ZeroJudge 題目連結：k848. P2.卡牌評分 (Card)

解題想法

分成兩個部分，先掃過全部的卡牌資料並找最大值，再掃一輪計算每張牌的積分。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 張卡牌
    S, A, D, H = [0]*n, [0]*n, [0]*n, [0]*n  # 積分，攻擊力，防禦力，生命力
    amax, dmax, hmax = 0, 0, 0  # 最高攻擊力，最高防禦力，最高生命力
    for i in range(n):  # 讀取 n 張牌的資料並找最大值
        a, d, h = map(int, input().split())
        A[i] = a; amax = max(amax, a)
        D[i] = d; dmax = max(dmax, d)
        H[i] = h; hmax = max(hmax, h)
    for i in range(n):  # 計算每張牌的積分
        if A[i] == amax: S[i] += 1
        if D[i] == dmax: S[i] += 1
        if H[i] == hmax: S[i] += 1
    print(S.index(max(S)) + 1)  # 印出最高積分卡牌編號

ZeroJudge 解題筆記：k847. P1.租車費用 (Rent)

作者：王一哲
日期：2025年5月6日



ZeroJudge 題目連結：k847. P1.租車費用 (Rent)

解題想法

按照題目的計費規則寫就行了，先算租車天數，分成每租滿 10 天以及未滿 10 天兩個部分計費。

Python 程式碼

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

import sys

month = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = sum(month[m1: m2]) - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)

月份的天數改成前綴和，如果輸入的月份是 $m1, m2$，要算計算 $m2-1$ 到 $m1$ 月份的天數 $psum[m2-1] - psum[m1-1]$。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

import sys

psum = (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)
for line in sys.stdin:
    m1, d1 = map(int, line.split())  # 第一天月、日
    m2, d2 = map(int, input().split())  # 第二天月、日
    # 租車天數，先計算月份，減去 m1 月份在 d1 之前的天數，加上 m2 月份的天數，頭尾都要算天數，再加 1
    days = psum[m2-1] - psum[m1-1] - d1 + d2 + 1
    fee = (days//10) * 900  # 每租滿10天算900元
    fee += (days%10) * 100  # 未滿10天的部分每天100元
    print(fee)

ZeroJudge 解題筆記：k520. P8.幸運基數 (Base)

作者：王一哲
日期：2025年5月5日



ZeroJudge 題目連結：k520. P8.幸運基數 (Base)

解題想法

我在這題卡了很久，一直想不出比較有效率的寫法。由題目的敘述可知，如果要把10進位制的數字 $n$ 換成 $k$ 進位制表示，而且轉換後每個位數都是 $1$，一定會有的解是 $k = n-1$，轉換後為 $11$，如果 $k$ 越小，轉換後的位數越多。我有試著把 $3 \leq n \leq 1000$ 之中 $k \neq n-1$ 的數字列出來，但看不出規律。

(7, 2), (13, 3), (15, 2), (21, 4), (31, 2), (31, 5), (40, 3), (43, 6), (57, 7), (63, 2),
(73, 8), (85, 4), (91, 9), (111, 10), (121, 3), (127, 2), (133, 11), (156, 5), (157, 12), (183, 13), 
(211, 14), (241, 15), (255, 2), (259, 6), (273, 16), (307, 17), (341, 4), (343, 18), (364, 3), (381, 19),
(400, 7), (421, 20), (463, 21), (507, 22), (511, 2), (553, 23), (585, 8), (601, 24), (651, 25), (703, 26),
(757, 27), (781, 5), (813, 28), (820, 9), (871, 29), (931, 30), (993, 31)

後來想到，如果 $k$ 越小，轉換後的位數越多，那就先算出 2 進位制的位數，然後位置依序遞減到 2 為止，每次再用二分搜尋法，在 $low = 2, high = n-1$ 之間找解，雖然有很多次不必要的計算，但至少能正確地找到答案。

Python 程式碼

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

import sys, math

# 檢查以 base 為底，在指定位數 digit 的值與 num 的大小關係
def check(num, base, digit):
    power, total = 1, 0  # 目前的次方，加總
    for i in range(digit):  # 從個位數開始往左計算 
        total += power  # 更新 total
        power *= base  # 更新 power 為 base**(i+1)
        if total > num: return 1  # 如果 total 大於 num，回傳 1，跳出函式
    if total == num: return 0  # 如果最後 total 等於 num，回傳 0
    return -1  # 否則回傳 -1

for line in sys.stdin:
    n = int(line)  # 要找基底的數字 n
    ans = n-1  # 答案預設為 n-1
    digitmax = math.ceil(math.log(n, 2))  # 最多的位數
    for digit in range(digitmax, 1, -1):  # 依序檢查最多位數到 2 位數
        low, high = 2, n-1  # 下限 2，上限 n-1
        while low <= high:  # 當 low 小於等於 high，繼續執行
            mid = (high - low)//2 + low  # 取中間值
            state = check(n, mid, digit)  # 呼叫 check 檢查大小關係
            if state == 0:  # 找到解，更新 ans 為較小的值，降低 high
                ans = min(ans, mid); high = mid-1
            elif state == 1: high = mid-1 # mid 太大，降低 hight
            else: low = mid+1  # mid 太小，提高 low
    print(ans)  # 印出答案

ZeroJudge 解題筆記：k519. P7.機票 (Ticket)

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



ZeroJudge 題目連結：k519. P7.機票 (Ticket)

解題想法

這題考 Floyd-Warshall 演算法。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 個城市
    graph = [list(map(int, input().split())) for _ in range(n)]  # 讀取城市之前移動費用
    start, end = map(int, input().split())  # 起點、終點
    start -=1; end -= 1  # 配合索引值減 1
    for k in range(n):  # 以 k 為轉機地點
        for i in range(n):  # 以 i 為起點
            for j in range(n):  # 以 j 為終點
                if graph[i][k] == -1 or graph[k][j] == -1: continue  # k 等於 i 或 j，找下一組
                if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j] - 50:  # 如果 i 等於 j 或 i->j 成本大於 i->k->j -50
                    graph[i][j] = graph[i][k] + graph[k][j] - 50
    print(graph[start][end])  # 印出答案

ZeroJudge 解題筆記：k518. P6.蛋糕切塊 (Cake)

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



ZeroJudge 題目連結：k518. P6.蛋糕切塊 (Cake)

解題想法

這題考動態規畫，我同時利用 set 儲存可用的子字串，這樣程式運作速度會比較快。

Python 程式碼

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

import sys

def can_cut_cake(s, cuts):
    n = len(s)  # 字串長度
    dp = [False]*(n+1)  # 是否能走到 i，如果能走到 i+1 代表有解
    dp[0] = True  # 一定能走到開頭
    # 動態規劃遍歷
    for i in range(1, n+1):  # 依序找終點 i = 1 ~ n
        for j in range(i):  # 依序找起點 j = 0 ~ i-1
            if dp[j] and s[j:i] in cuts:  # 如果能走到 j 而且 s[j:i] 在 cuts 之中
                dp[i] = True  # 可以走到 i
                break  # 只要找到一個可行切割後就可以停止
    print("yes" if dp[n] else "no")  # 如果 dp[n] 為 True 印出 yes，反之印出 no

for s in sys.stdin:
    s = s.strip()  # 要檢查的字串
    m = int(input())  # 可用的子字串數量
    cuts = set()  # 可用的子字串
    for _ in range(m): cuts.add(input())  
    can_cut_cake(s, cuts)  # 計算並輸出結果

ZeroJudge 解題筆記：k517. P5.波動 (Wave)

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



ZeroJudge 題目連結：k517. P5.波動 (Wave)

解題想法

因為這題需要將所有的波依照傳播的時間由小到大排序，如果時間相同再依照方向 W、S、E、N 排序。如果將時間、方向組成 Python 的 tuple 或是 C++ 的 pair 再排序，但由於 W、S、E、N 不是依照字典順序，不能這樣處理。所以我先將 W、S、E、N 換成對應的數字 0、1、2、3，與時間組成 tuple 再排序，輸出結果時再將數字換回 W、S、E、N。在 C++ 則是自訂結構體，再用 lambda function 自訂排序規則。

Python 程式碼

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

import sys

c2n = {'W': 0, 'S': 1, 'E': 2, 'N': 3}
n2c = ('W', 'S', 'E', 'N')
for line in sys.stdin:
    p = int(line)  # p 道波動
    wave = []  # 傳播時間，波源方位
    for _ in range(p):  # 執行 p 次
        c, d, v = input().split()  # 波源方位，距離，波速
        d = int(d); v = int(v)  # 轉成 int
        wave.append((d/v, c2n[c]))  # (d/v, c2n[c]) 加入 wave
    wave.sort()  # 依照 (t, 方向) 由小到大排序
    print("".join([n2c[n] for _, n in wave]))  # 由 wave 取出 n，換成對應的字母，接成字串，印出

ZeroJudge 解題筆記：k516. P4.根號 (Sqrt)

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



ZeroJudge 題目連結：k516. P4.根號 (Sqrt)

解題想法

畫圖形的題目，關鍵在於找到各部位畫圖的規則。

Python 程式碼

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

import sys

for line in sys.stdin:
    k = int(line.strip())  # 短邊長度
    a, b = (k-1)//2 - 1, 2*k-1  # 左斜線、長邊長度
    n, h = k+a+k+b, k//2  # 全長，短邊於第 h 列
    grid = [[" "]*n for _ in range(k)]  # 圖形，預設為空白
    for i in range(k): grid[h][i] = "*"  # 短邊
    for i in range(a): grid[h+1+i][k+i] = "*"  # 左斜線
    for i in range(k): grid[k-1-i][k+a+i] = "*"  # 右斜線
    for i in range(2*k-1): grid[0][k+a+k+i] = "*"  # 長邊
    for i in range(k): print("".join(grid[i]))  # 印出圖形