#41866: 暴力搜索 (窮舉法)


jesswanghtc@gmail.com (jesswanghtc)

學校 : 不指定學校
編號 : 277079
來源 : [49.216.33.110]
最後登入時間 :
2024-09-03 16:25:57
k514. P2.解藥 (Medicine) -- 2022年12月TOI新手同好會 | From: [49.216.33.110] | 發表日期 : 2024-09-03 16:19

解題思路:

  1. 遍歷所有可能的組合

    • 由於每種材料都有 NNN 個小包,我們需要檢查所有的組合來找到符合比例的組合。這裡採用四層巢狀迴圈,分別遍歷每種材料的小包。
    • 這樣的結構確保了我們能夠檢查所有可能的組合,避免遺漏。
  2. 比例檢查

    • 對於每一組候選小包,我們需要檢查這些小包的分量是否符合指定的比例 a:b:c:da:b:c:da:b:c:d。
    • 我們可以通過交叉相乘的方式來檢查比例,例如:檢查 A小包的分量 * b == B小包的分量 * a
    • 將比例檢查抽象成一個函式 check_proportion,方便邏輯的重用與維護。
  3. 輸出結果

    • 當找到符合比例的小包組合時,直接輸出這四個小包的分量並結束程式。
    • 如果遍歷了所有組合仍然找不到符合條件的組合,則輸出 -1,表示無法製作出符合要求的解藥。

實作步驟:

  1. 輸入處理

    • 讀取比例 a,b,c,da, b, c, da,b,c,d 和小包數量 NNN。
    • 讀取每種材料的 NNN 個小包的分量。
  2. 遍歷所有組合

    • 使用四層巢狀迴圈,分別對應每種材料的小包,檢查所有可能的組合。
  3. 比例檢查與結果輸出

    • 對於每一組小包,使用 check_proportion 函式檢查是否符合比例。
    • 如果找到符合條件的組合,輸出其分量並結束程式。
    • 否則,遍歷完所有組合後輸出 -1

關鍵觀念:

  • 暴力搜索:由於小包數量 NNN 最多是 10,因此使用暴力搜索 (窮舉法) 來檢查所有可能的組合是可行的。
  • 比例檢查:交叉相乘是一種常見的檢查比例相等的方法,這裡用來檢查各材料小包之間的比例是否符合要求。
 
ZeroJudge Forum