Phủ kín đồi trọc
Xem dạng PDF
Gửi bài giải
Điểm:
12,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Một nhóm học sinh đang tham gia buổi ngoại khóa với nhiệm vụ phủ kín một đồi trọc bằng cách trồng cây theo các đoạn thẳng có sẵn trên trục số. Đoạn đồi trọc cần phủ kín nằm trên trục số từ tọa độ ~x~ đến ~y~ (với ~x~ và ~y~ là số nguyên và ~x < y~). Nhóm học sinh có N đoạn thẳng, mỗi đoạn được biểu diễn bởi điểm đầu ~a_i~ và điểm cuối b_i với ~a_i < b_i~. Cả ~a_i, b_i~, ~x~, và ~y~ đều là số nguyên nằm trong khoảng ~[-100000, 100000]~.
Yêu cầu của bài toán là tìm ra ít nhất K đoạn thẳng sao cho khi đặt chúng lên trục số, các đoạn thẳng này có thể phủ kín đoạn ~[x, y]~. Nếu không thể chọn các đoạn để phủ kín đoạn ~[x, y]~, hãy báo rằng không có nghiệm.
Dữ liệu vào:
- Dòng đầu tiên chứa một số nguyên ~N~ (số lượng đoạn thẳng, ~1 < N ≤ 10000~0).
- Dòng tiếp theo chứa hai số nguyên ~x~ và ~y~ (tọa độ của đoạn cần phủ kín).
- ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a[i]~ và ~b[i]~, biểu thị điểm đầu và điểm cuối của đoạn thứ ~i~ (các số cách nhau bằng dấu cách). ~a[i],b[i] = long long~
Dữ liệu ra:
- Ghi ra số ~K~, là số lượng đoạn thẳng tối thiểu để phủ kín đoạn ~[x, y]~. Nếu không có cách nào để phủ kín, in ~K = -1~ .
- Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng được chọn để phủ kín đoạn ~[x, y]~.
Ví dụ:
Dữ liệu vào:
5
3 23
1 15
3 10
8 20
17 25
2 7
Dữ liệu ra:
3
1 3 4
Giải thích:
- Chọn các đoạn 1, 3, và 4 sẽ phủ kín đoạn [3, 23].
Bình luận
ai upvote la sv
im