[VTT Q4 Contest 03] Bài 4: Phủ đoạn thẳng [COVER]
Xem dạng PDF
Gửi bài giải
Điểm:
4,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
COVER.INP
Output:
COVER.OUT
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, PyPy, Python
Trên trục số ~Ox~ có ~n~ đoạn thẳng, đoạn thứ ~i~ có hai đầu mút là ~l_i~ và ~r_i~. Hãy chọn ra ít đoạn nhất trong số đó sao cho chúng phủ kín toàn bộ đoạn ~[a, b]~.
Dữ liệu
- Dòng đầu tiên chứa ba số nguyên dương ~n, a, b~ (~1 \le n \le 10^5~, ~1 \le a \le b \le 10^5~) lần lượt là số đoạn và hai đầu mút của đoạn cần phủ.
- ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le 10^5~).
Kết quả
- Dòng đầu tiên ghi số nguyên ~k~ là số đoạn được chọn. Nếu không có cách chọn nào phủ được thì ghi ~-1~.
- Nếu có cách chọn, ghi tiếp ~k~ dòng, mỗi dòng một số nguyên là chỉ số (thứ tự trong input) của một đoạn được chọn.
Ví dụ
Ví dụ 1
COVER.INP
8 2 10
4 8
1 3
2 3
1 4
3 4
7 10
9 11
8 11
COVER.OUT
3
1
4
6
Ví dụ 2
COVER.INP
4 1 200
1 4
2 5
4 5
6 45
COVER.OUT
-1
Bình luận