有一個空的泳池需要注滿特定溫度的水。為了做到這一點，你有一排放在泳池邊緣附近的水罐，這些水罐從編號 0 開始排列。每個水罐中裝有不同體積、不同溫度的水。你可以將任意多個水罐倒入泳池，但只能倒入連續的水罐。
目標是讓泳池中至少注入一半容量的水（不能超過泳池總容量），並且使混合後的水溫儘可能接近目標溫度，而且與目標溫度的差異不得超過 ±5°C。我們假設，當混合兩種不同體積的水時，混合後的水溫為原始水溫按體積加權的平均值。
例如，你可能有以下 5 個水罐：
| 水罐編號 | 體積（公升） | 溫度（°C） |
|---|---|---|
| 0 | 45 | 23 |
| 1 | 20 | 40 |
| 2 | 67 | 22 |
| 3 | 109 | 11 |
| 4 | 9 | 56 |
例如，你可以將水罐 1、2 和 3 的水倒入泳池，但不能只倒入水罐 1 和 3，因為它們不是連續的。
假設泳池夠大，倒入水罐 1、2 和 3 的總體積為 20 + 67 + 109 = 196 公升。混合後的水溫為：
(20 × 40 + 67 × 22 + 109 × 11) / (20 + 67 + 109) = 17.719388 °C
第一行是一個整數，表示要解決的問題數量。接下來，對於每一個問題：
一行包含兩個整數：泳池的最大容量，以及目標水溫。
一行包含一個整數：水罐的數量（不會超過 3000 個）。
接下來有多行，每行對應一個水罐，包含兩個整數：該水罐中水的體積和水溫。
對於每一個問題，你需要輸出一行，包含兩個整數，分別表示要倒入泳池的起始水罐編號和結束水罐編號，以使混合後的水溫與目標溫度的差值最小。
如果沒有任何方法可以在不超過泳池容量的情況下，倒入至少一半容量的水，且使水溫在允許的溫度範圍內（與目標溫度的差異不超過 ±5°C），那麼這一行應該輸出 Not possible。
如果有多個最佳解（也就是混合後的水溫與目標溫度的差值相同），則應該選擇起始水罐編號最小的那組水罐。
2 615 11 15 24 18 25 5 74 4 80 5 75 3 96 2 53 6 25 24 74 20 97 20 76 3 14 16 8 3 21 14 82 18 100 20 3 10 20 66 40 5 100
5 12 Not possible
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||