資料工程高階・限流、串流、SCD 與 CDC

爬蟲呼叫外部 API 前要先過「令牌桶」限流：桶的容量是 C 個令牌，每秒補 R 個（補滿為止）。每個請求要拿 1 個令牌，拿得到就放行，拿不到就拒絕（被拒的請求不會重試）。

規則（全部用整數運算）：

• 時間 0 時桶是滿的（C 個），上次補充時間 last = 0。
• 請求在第 t 秒到達（t 不遞減）時，先補：tokens = min(C, tokens + (t − last) × R)，last = t。
• 補完若 tokens ≥ 1 就放行並 tokens −= 1，否則拒絕。

輸入：

第 1 行：C R

第 2 行：各請求到達的秒數（空白分隔，不遞減）

輸出：每個請求一行「t ALLOW」或「t DENY」，最後一行「allowed 放行數 denied 拒絕數」。

範例輸入：

2 1

0 0 0 2

範例輸出：

0 ALLOW

0 ALLOW

0 DENY

2 ALLOW

allowed 3 denied 1

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。starter 已先把全部輸入讀進來，請保留這段，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。

串流系統依「事件時間」把資料切成 60 秒的滾動視窗（第 t 秒屬於視窗 t // 60 × 60）。資料可能晚到，系統用 watermark 判斷能不能收：

• watermark ＝ 目前為止看過的最大事件時間 − L（L 為允許延遲秒數）；還沒看過任何事件時，watermark 視為負無限大。
• 每筆事件到達時，先用「這筆到達前」的 watermark 判斷：若該事件所屬視窗的結束時間（start + 60）≤ watermark，這筆就丟棄（太晚了）。
• 判斷完（不論收或丟）再用這筆的事件時間更新最大事件時間。

輸入：

第 1 行：L

第 2 行：n

接下來 n 行：事件時間 值（依「到達順序」排列，事件時間不一定遞增）

輸出：

先依視窗起點由小到大，每個「有收到資料」的視窗一行「window 起點 count 筆數 sum 值總和」；

最後一行「dropped」加上被丟棄事件的事件時間（依到達順序，空白分隔；沒有就只印 dropped）。

範例輸入：

5

4

10 1

70 2

50 3

20 4

範例輸出：

window 0 count 1 sum 1

window 60 count 1 sum 2

dropped 50 20

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。starter 已先把全部輸入讀進來，請保留這段，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。

資料倉儲的客戶維度表要保留歷史（SCD Type 2）：屬性改變時不覆蓋，而是把舊版本「關閉」、再新增一筆新版本。

目前維度表每筆都是現行版本（valid_to 為 9999-12-31、current 為 Y）。今天（日期 D）收到一批客戶資料，規則：

• 新的 key：新增一筆，valid_from = D、valid_to = 9999-12-31、current = Y。
• 既有 key 且 name 或 city 有變：舊版本改成 valid_to = D、current = N；再新增一筆新版本（同上）。
• 既有 key 且內容相同：不動。
• 這批資料沒出現的 key：不動（不刪除）。

輸入：

第 1 行：D

第 2 行：m（現行維度筆數）

接下來 m 行：key name city valid_from

下一行：k（今天收到的筆數）

接下來 k 行：key name city

輸出：處理後的完整維度表，每筆一行「key name city valid_from valid_to current」，依 key、再依 valid_from 由小到大排序。最後一行「inserted 新增筆數 closed 關閉筆數」。

範例輸入：

2026-01-01

1

K1 amy tp 2025-01-01

2

K1 amy tc

K2 bob ks

範例輸出：

K1 amy tp 2025-01-01 2026-01-01 N

K1 amy tc 2026-01-01 9999-12-31 Y

K2 bob ks 2026-01-01 9999-12-31 Y

inserted 2 closed 1

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。starter 已先把全部輸入讀進來，請保留這段，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。

資料庫的變更紀錄（CDC）透過訊息佇列送到下游，可能「亂序」也可能「重送」。每筆紀錄有遞增的序號 lsn。下游要重放出最終的資料表內容：

• 依 lsn 由小到大套用；同一個 lsn 出現多次只套用一次（重送）。
• I（新增）與 U（更新）都視為 upsert：把 key 的值設成 value。
• D（刪除）：key 存在就刪除，不存在就忽略。

輸入：

第 1 行：n

接下來 n 行：lsn op key [value]（D 沒有 value）

輸出：最終資料表每個 key 一行「key value」，依 key 由小到大；最後一行「applied 套用筆數 duplicates 重送筆數」。

範例輸入：

4

2 U a 5

1 I a 1

3 D a

2 U a 5

範例輸出：

applied 3 duplicates 1

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。starter 已先把全部輸入讀進來，請保留這段，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。