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

演算法高階・圖的進階走訪

DFS 三色判環、拓撲排序推關鍵路徑、限制輪數的 Bellman-Ford。

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

  1. 01

    會無限觸發的資料表

    困難圖/環偵測

    資料倉儲裡設了觸發規則:A B 表示資料表 A 更新後會觸發 B 重算。如果從某張表出發,沿著觸發規則有可能繞進一個環(例如 A→B→C→A,或 A→A),這張表一更新就可能停不下來;反之,從它出發的每一條路最後都會走到沒有下游的表,它就是安全的。

    輸入:

    第 1 行:所有資料表名稱(以空白分隔)

    第 2 行:規則數 m

    接下來 m 行:A B(可能有重複的規則,也可能 A 等於 B)

    輸出:兩行

    第 1 行:SAFE: 後接安全的資料表,依名稱排序、以空白分隔

    第 2 行:LOOP: 後接不安全的資料表,依名稱排序、以空白分隔

    某一類沒有任何表時,冒號後印 -(例:LOOP: -)。

    要求:用 DFS 加三種狀態(走訪中、安全、不安全)一次判定,每張表只算一次;不要從每張表出發列舉所有路徑。

    範例輸入:

    t1 t2 t3 t4

    4

    t1 t2

    t2 t3

    t3 t2

    t4 t1

    範例輸出:

    SAFE: -

    LOOP: t1 t2 t3 t4

    類型對應:LeetCode「Find Eventual Safe States」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  2. 02

    管線關鍵路徑

    困難圖/拓撲排序

    一條資料管線有 n 個任務,各有執行時間(分鐘)與前置任務。worker 數量不限:任務的所有前置任務都完成後就立刻開始。請排出每個任務最早的開始與結束時間、整條管線最早完成的時間,並找出關鍵任務:只要延後 1 分鐘就會讓整條管線延後完成的任務(最晚可開始時間等於最早開始時間)。

    輸入:

    第 1 行:任務數 n

    接下來 n 行:任務名 執行分鐘 前置任務,前置任務以逗號分隔,沒有前置任務寫 -(前置任務一定是這 n 個任務之一)

    輸出:

    • 相依關係有環:只印一行 CYCLE
    • 否則:

    第 1 行:TOTAL 最早完成時間

    接下來 n 行:任務名 開始 結束,依開始時間排序,同時開始的依任務名排序

    最後一行:CRITICAL: 後接關鍵任務,依開始時間、再依任務名排序,以空白分隔

    要求:用拓撲排序(Kahn 演算法)往前推最早時間,再照拓撲順序反過來推最晚時間;不要列舉所有路徑。

    範例輸入:

    4

    load 10 -

    check 3 -

    transform 5 load

    publish 2 transform,check

    範例輸出:

    TOTAL 17

    check 0 3

    load 0 10

    transform 10 15

    publish 15 17

    CRITICAL: load transform publish

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

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

    作答登入後可作答
  3. 03

    限制轉送次數的最低傳輸費

    困難最短路徑

    資料要從一個區域的儲存桶複製到另一個區域。區域之間有單向的傳輸通道,每條通道有傳輸費用。每多經過一個中繼區域,資料就多一次落地與驗證,所以規定中繼區域最多 k 個(也就是最多走 k+1 條通道)。請回答多組查詢的最低費用。

    輸入:

    第 1 行:通道數 m

    接下來 m 行:起點 終點 費用(單向,費用為正整數,同一對區域可能有多條通道)

    下一行:查詢數 q

    接下來 q 行:起點 終點 k

    輸出:每個查詢一行,最低費用;在限制內到不了印 -1。起點等於終點時費用是 0。

    要求:用「限制輪數的 Bellman-Ford」:做 k+1 輪鬆弛,每一輪只能用上一輪的結果;不要列舉所有路徑。注意 Dijkstra 直接套用會出錯(費用最低的路可能中繼太多次)。

    範例輸入:

    3

    a b 10

    b c 10

    a c 50

    2

    a c 0

    a c 1

    範例輸出:

    50

    20

    類型對應:LeetCode「Cheapest Flights Within K Stops」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答