時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
有一個空泳池與一列編號從 0 起的水罐，每罐有已知水量及溫度。只能選擇一段連續水罐全部倒入池中，總水量須至少為池容量的一半，且不得超過容量。
混合溫度是以水量為權重的平均溫度。請選出與目標溫度差距最小的一段，且差距不得超過 5 度（較冷或較熱皆同）。若有多個同樣最佳方案，選編號較小的罐子，即先取較小起始編號，再取較小結束編號。
輸入格式
第一行為問題數。每筆先有兩個整數：泳池容量與目標溫度。下一行為水罐數量，最多 3000；之後每行有該罐的整數水量與溫度。
輸出格式
每筆輸出起始與結束水罐編號，以空白分隔。若無法同時滿足水量與溫度限制，輸出 Not possible。
範例測資
範例輸入 1
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
範例輸出 1
5 12 Not possible
請先登入後再提交程式碼
討論與題解
載入討論區…