演算法高階・快取、字串與視窗

為了少打幾次 FinMind API，要在記憶體裡放一個容量為 cap 的快取，滿了就淘汰「最久沒被用到」的項目（get 和 put 都算使用）。

輸入：

第 1 行：cap

第 2 行：m（操作數）

接下來 m 行，每行一個操作：

• get key：查詢
• put key value：寫入或更新

輸出：

• 每個 get 印一行：有就印值，沒有印 MISS
• 每個 put 若造成淘汰，印一行「EVICT 被淘汰的 key」
• 最後印一行「CACHE」加上目前所有 key，由最久沒用到排到最近使用，以空白分隔

要求每個操作 O(1)。

範例輸入：

2

5

put a 1

put b 2

get a

put c 3

get b

範例輸出：

1

EVICT b

MISS

CACHE a c

類型對應：LeetCode「LRU Cache」類（情境與敘述為本平台改寫）。

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。本題在瀏覽器內以 Pyodide 執行，只用標準函式庫。先把全部輸入讀完再輸出，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。

一段事件流被編碼成字串（每個字元一種事件）。稽核要找出「包含所有必查事件」的最短連續片段，必查事件可能重複（例如 AAB 表示要有至少兩個 A、一個 B）。

輸入：

第 1 行：事件流字串

第 2 行：必查事件字串

輸出：最短片段本身；若有多個同樣短，取最早出現的；找不到印 NONE。

範例輸入：

ADOBECODEBANC

ABC

範例輸出：

BANC

類型對應：LeetCode「Minimum Window Substring」類（情境與敘述為本平台改寫）。

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。本題在瀏覽器內以 Pyodide 執行，只用標準函式庫。先把全部輸入讀完再輸出，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。

部署工具用簡寫產生重複的設定片段：k[內容] 表示把內容重複 k 次，可以巢狀，例如 2[a3[b]] 展開成 abbbabbb。k 為正整數，可能是多位數。

輸入：

第 1 行：n

接下來 n 行：每行一個模板

輸出：每行一個展開結果。

範例輸入：

2

3[a]2[bc]

2[a3[b]]

範例輸出：

aaabcbc

abbbabbb

類型對應：LeetCode「Decode String」類（情境與敘述為本平台改寫）。

輸入請用 input() 逐行讀取（平台不支援 sys.stdin）。執行時平台會把每一行測資回顯在輸出最前面，這是正常的，不用自己印。本題在瀏覽器內以 Pyodide 執行，只用標準函式庫。先把全部輸入讀完再輸出，不要在迴圈裡邊讀邊印（回顯行會插進輸出中間，就對不上答案）。