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

演算法高階・圖的進階搜尋

BFS 著色判斷能否分兩組、Kruskal 加併查集的最小生成樹、位置加鑰匙遮罩的狀態 BFS。

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

  1. 01

    衝突任務分兩個時段

    困難圖

    夜間批次有 n 個任務(編號 1 到 n),要分到 A、B 兩個時段跑。有些任務兩兩衝突(會搶同一張表的鎖),衝突的兩個任務必須在不同時段。請判斷能不能分;能分的話,照下面的規則決定唯一的分法並印出兩個時段各有幾個任務。

    規則:把任務與衝突關係看成圖,每個連通的群組裡編號最小的任務放 A 時段,同群組其他任務的時段就被衝突關係決定;沒有任何衝突的任務自己就是一個群組,放 A。

    輸入:

    第 1 行:組數 t

    接下來 t 行:n 後面接若干個衝突 a-b(以空白分隔;可能沒有任何衝突;同一對可能重複出現;a-a 表示任務 a 跟自己衝突,這種情況一定分不了),或 n GEN m seed(由 starter 產生 m 個衝突)。GEN 開頭的行是大量測資的縮寫:starter 已寫好產生資料的函式,讀進來後跟一般的資料一樣,不用自己處理。

    輸出:每組一行

    • 能分:YES A時段任務數 B時段任務數
    • 不能分:NO 編號,編號是「分不了的群組」中最小的任務編號;有多個群組分不了時,取這個編號最小的那一個

    要求:用 BFS 著色,任務編號由小到大當起點,一個群組一個群組處理;n 可能有幾千,不要列舉所有分法。

    範例輸入:

    2

    4 1-2 1-3 1-4

    3 1-2 2-3 1-3

    範例輸出:

    YES 1 3

    NO 1

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

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

    作答登入後可作答
  2. 02

    叢集專線最低建置成本

    困難最小生成樹

    新機房有 n 個節點(編號 1 到 n),網路組列出了可以拉的專線,每條連接兩個節點、有建置成本。要挑一些專線讓所有節點彼此連通(可以經過別的節點),總成本最低。最低成本的挑法可能不只一種,但總成本與「挑中的專線裡最貴的那條」的成本是固定的,請印出這兩個數。

    輸入:

    第 1 行:組數 t

    每組:第 1 行是 n m(節點數、候選專線數),接下來 m 行是 a b 成本(a ≠ b,成本是正整數,同一對節點可能有多條);

    或第 1 行是 n m、第 2 行是 GEN seed lo hi(由 starter 產生 m 條專線,成本在 lo 到 hi 之間)。GEN 開頭的行是大量測資的縮寫:starter 已寫好產生資料的函式,讀進來後跟一般的資料一樣,不用自己處理。

    輸出:每組一行

    • 能全部連通:MST 總成本 最貴一條的成本(n = 1 時不用拉線,印 MST 0 0)
    • 不能全部連通:DISCONNECTED 群組數,群組數是用所有候選專線連完之後,彼此不相連的節點群有幾個

    要求:用 Kruskal 演算法:專線依成本由小到大排序,用併查集(union-find)判斷兩端是不是已經相連,相連就跳過;m 可能有幾千條。

    範例輸入:

    1

    3 3

    1 2 4

    2 3 1

    1 3 2

    範例輸出:

    MST 3 2

    類型對應:LeetCode「Connecting Cities With Minimum Cost」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  3. 03

    機房巡檢收齊門禁卡

    困難BFS

    機房的平面圖是一個 r×c 的格子:@ 是巡檢人員的起點,. 是走道,# 是機櫃(不能走),小寫字母 a 到 f 是門禁卡,大寫字母 A 到 F 是門。拿到門禁卡 a 之後才能通過門 A,依此類推;走到門禁卡的格子就自動拿到,拿到後一直有效。每一步可以往上下左右走一格,不能走出平面圖。每種門禁卡最多一張;有些門可能沒有對應的門禁卡,那扇門永遠過不去。

    請算出收齊平面圖上所有門禁卡最少要走幾步。

    輸入:

    第 1 行:組數 t

    每組:第 1 行是 r c,接下來 r 行各是長度 c 的字串

    輸出:每組一行,最少步數;收不齊時印 -1;平面圖上沒有門禁卡時印 0。

    要求:用 BFS,狀態是「位置+手上有哪些門禁卡」,門禁卡集合用位元遮罩表示;同一個位置手上的卡不同,要當成不同的狀態。

    範例輸入:

    1

    2 4

    @.aA

    ..#b

    範例輸出:

    4

    類型對應:LeetCode「Shortest Path to Get All Keys」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答