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

演算法中階・數學與位元運算

最大公因數決定分批大小、質數篩回答區間查詢、位元遮罩表示集合找不相交的配對。

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

  1. 01

    依分區鍵等量分批

    中等數學

    一批事件要切成好幾個小批次送出,規則是:每個小批次的筆數都相同(至少 2 筆),而且同一個小批次裡的事件分區鍵都一樣。每筆事件都要分進某個小批次。請判斷能不能這樣切;能的話,列出所有可行的批次大小,並印出用最大批次大小時一共有幾批。

    輸入:

    第 1 行:組數 t

    接下來 t 行:每行一組事件的分區鍵(以空白分隔,至少一筆)

    輸出:每組一行

    • 不能切:印 NO
    • 能切:印 MAX 最大批次大小 BATCHES 批數 SIZES 所有可行大小(可行大小由小到大,以空白分隔)

    要求:可行的批次大小 g 必須整除每個分區鍵的筆數,所以先算所有筆數的最大公因數,再從它推出答案。

    範例輸入:

    2

    u1 u2 u2 u1

    u1 u1 u2

    範例輸出:

    MAX 2 BATCHES 2 SIZES 2

    NO

    類型對應:LeetCode「X of a Kind in a Deck of Cards」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  2. 02

    雜湊分區數挑質數

    中等數學

    把資料雜湊分到 n 個分區時,分區數取質數比較不容易因為鍵的規律而分得不平均。規劃人員會問很多個上限值:不超過這個值的質數有幾個、最大的是哪一個。

    輸入:一行,若干個查詢值(非負整數,以空白分隔,最大 200000)

    輸出:每個查詢一行 查詢值 質數個數 最大質數(不超過查詢值的質數;沒有質數時最大質數印 -)。

    要求:用埃拉托斯特尼篩法(Sieve of Eratosthenes)一次篩到所有查詢的最大值,再用前綴的方式回答每個查詢;不要對每個查詢逐一試除。

    範例輸入:

    5 20

    範例輸出:

    5 3 5

    20 8 19

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

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

    作答登入後可作答
  3. 03

    不共用資料表的工作配對

    中等位元運算

    每個批次工作會鎖住幾張共用資料表,資料表以小寫字母 a 到 t 代表(共 20 張)。兩個工作鎖的資料表完全沒有重疊時才能同時跑。排程器想找出一對可以同時跑、而且執行時間加總最長的工作。

    用位元遮罩表示集合:資料表 a 是第 0 個位元、b 是第 1 個位元……,一個工作鎖的資料表集合就是一個整數,例如 abd 是 1 + 2 + 8 = 11。兩個集合沒有交集,等價於兩個遮罩做 & 的結果是 0。

    輸入:

    第 1 行:組數 t

    每組:第 1 行是工作數 n,接下來 n 行是 工作名稱 執行時間 資料表字母(不鎖任何資料表時寫 -,同一個字母不會重複)

    輸出:每組

    • 先依輸入順序,每個工作一行 工作名稱 遮罩值
    • 最後一行:BEST 時間加總 工作A 工作B;加總相同時取工作A在輸入中較前面的,再相同取工作B較前面的(工作A一定排在工作B之前)。沒有任何一對能同時跑時印 NONE

    要求:先把每個工作轉成遮罩整數,配對時只用 & 判斷,不要用 set 交集。

    範例輸入:

    1

    3

    load 20 ab

    clean 15 c

    index 30 bt

    範例輸出:

    load 3

    clean 4

    index 524290

    BEST 45 clean index

    類型對應:LeetCode「Maximum Product of Word Lengths」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答