演算法中階・回溯、矩陣與佇列模擬
遞迴列舉組合、以邊界控制矩陣走訪、用佇列模擬排程器。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 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 執行,只用標準函式庫。
作答登入後可作答 - 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 執行,只用標準函式庫。
作答登入後可作答 - 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 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了