AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・中階・3 題

演算法中階・回溯、矩陣與佇列模擬

遞迴列舉組合、以邊界控制矩陣走訪、用佇列模擬排程器。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 01

    湊出剛好容量的檔案組合

    中等回溯

    上傳到物件儲存前,要把小檔案打包成剛好等於分塊大小 cap(MB)的包。給一批大小各不相同的檔案,列出所有「每個檔案最多用一次、大小總和剛好等於 cap」的組合。

    輸入:

    第 1 行:cap

    第 2 行:每個檔案的大小(正整數,以空白分隔,彼此不同)

    輸出:

    第 1 行:組合數(沒有任何組合時印 0,後面不再印東西)

    接下來每個組合一行:組合內的大小由小到大、以空白分隔;各組合之間依字典順序排列(先比第一個數,相同再比第二個數,依此類推)

    要求:用遞迴回溯產生組合,總和超過 cap 就不再往下試。

    範例輸入:

    10

    6 1 4 3 9

    範例輸出:

    3

    1 3 6

    1 9

    4 6

    類型對應:LeetCode「Combination Sum II」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  2. 02

    機櫃溫度螺旋巡檢

    中等矩陣走訪

    機房的感測器排成 r 列 c 欄的網格。巡檢機器人從左上角出發,沿著外圈順時針走:先往右走到底、再往下、再往左、再往上,走完一圈再往內縮一圈,直到每個位置都走過一次。請依機器人經過的順序列出讀數。

    輸入:

    第 1 行:r c

    接下來 r 行:每行 c 個整數,是該列的讀數

    輸出:一行,依巡檢順序的讀數,以空白分隔。

    範例輸入:

    3 3

    1 2 3

    4 5 6

    7 8 9

    範例輸出:

    1 2 3 6 9 8 7 4 5

    類型對應:LeetCode「Spiral Matrix」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  3. 03

    輪流配額排程

    中等佇列模擬

    排程器用輪流配額(round-robin)分配一個 CPU:所有任務在時間 0 依輸入順序排進佇列。每一輪從佇列最前面取出一個任務,讓它執行 min(q, 剩餘工作量) 個時間單位;做完就記下完成時間,沒做完就排回佇列最後面。換任務不花時間。

    輸入:

    第 1 行:每次的配額 q

    第 2 行:任務數 n

    接下來 n 行:每行 任務名稱 工作量(正整數)

    輸出:n 行,依完成的先後,每行 任務名稱 完成時間。

    範例輸入:

    2

    3

    A 3

    B 2

    C 5

    範例輸出:

    B 4

    A 7

    C 10

    類型對應:LeetCode「Time Needed to Buy Tickets」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答