種子論壇 | 高雄市資訊培育協會學員討論區

標題: b859: 水梨 [打印本頁]

作者: 沈子耕 時間: 2016-10-28 20:06 標題: b859: 水梨

內容：

小李有顆水梨。有天，小李的水梨掉進了水裡，水裡有很多水貍，水裡的水貍拿走了小李的水梨。小李想從水裡的水貍手裡拿回小李的水梨。小李發現，若一隻水貍手裡有水梨，該水貍會把水梨拿給任一隻身高更高而且體重更重的水貍。若沒有更高而且更重的水貍，那水貍就會把水梨拿在手裡。請問最後水梨可能在哪幾隻水貍的手裡？

輸入說明：
第 1 行有一正整數 T(T <= 50)，接下來有 T 筆輸入。
每一筆輸入的第 1 行有 2 個正整數 N, M(M <= N <= 20,000)，代表有 N 隻水貍(編號為 1~N)，水梨目前在 M 號水貍的手裡。接下來有 N 行，第 i 行有兩個正整數 Hi, Wi(Hi, Wi <= 10^9)，分別代表 i 號水貍的身高和體重。

有 40% 的測資 N <= 200

輸出說明：
對於每一筆輸入，先輸出最後水梨可能會落在幾隻水梨的手裡，下一行輸出這些水貍的編號，編號由小到大輸出。

範例輸入：
2
3 1
1 1
2 3
3 2
4 2
1 3
1 1
2 2
3 3
範例輸出:
2
2 3
1
4
提示：
第 1 筆輸入，1 號水貍可能會把水梨拿給 2 號或 3 號水貍，2 號和 3 號水貍不會把水梨拿給其他水貍。

歡迎光臨種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)