Lệch múi giờ
Đề bài
Mô tả
Vòng chung kết ICPC thế giới đã đến, với vô số hoạt động bạn muốn tham dự: các bài phát biểu, bài thuyết trình, sự kiện vui chơi, chưa kể chính cuộc thi. Chỉ có một vấn đề: khi nào bạn sẽ ngủ?
Mỗi khi đi ngủ, bạn luôn đặt hẹn giờ, vì nếu không bạn có thể ngủ mãi. Nhờ hẹn giờ, bạn có thể chọn ngủ trong một số phút nguyên dương bất kỳ. Sau khi ngủ phút, bạn sẽ ở trạng thái tỉnh táo trong phút tiếp theo (nên bạn không thể ngủ lại được); rồi bạn vẫn hoạt động được thêm phút thứ ba (trong khoảng này bạn có thể tiếp tục thức, nhưng cũng có thể đi ngủ nếu muốn).
Bạn biết thời gian của mọi hoạt động trong vòng chung kết; hãy lập lịch ngủ sao cho không bỏ lỡ bất kỳ phần nào của bất kỳ hoạt động nào. Ngay trước khi vòng chung kết bắt đầu (tại phút ), bạn về tới phòng khách sạn sau một chuyến đi dài và cần đi ngủ ngay lập tức.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương (): số hoạt động được lên kế hoạch.
Dòng thứ trong dòng tiếp theo chứa hai số nguyên và : thời điểm bắt đầu và kết thúc của hoạt động thứ , tính bằng phút kể từ lúc vòng chung kết bắt đầu. Biết , , và .
Dữ liệu ra
Nếu tồn tại lịch ngủ cho phép bạn tham gia trọn vẹn mọi hoạt động đã lên kế hoạch, hãy in ra một lịch như vậy theo định dạng dưới đây. Ngược lại, in ra impossible.
Lịch ngủ gồm một dòng chứa số () là số lần ngủ, tiếp theo là dòng. Dòng thứ trong số đó chứa hai số nguyên và : thời điểm bắt đầu và kết thúc của lần ngủ thứ , tính bằng phút kể từ lúc vòng chung kết bắt đầu. Không được in lần ngủ nào sau hoạt động cuối cùng.
Các lần ngủ phải thỏa mãn , cùng với điều kiện đã mô tả ở trên là không được ngủ trong một khoảng thời gian sau mỗi lần ngủ. Bạn có thể đi ngủ ngay sau khi một hoạt động kết thúc (tức là có thể ) và có thể thức dậy ngay trước khi một hoạt động bắt đầu (tức là có thể ).
Nếu có nhiều lịch ngủ hợp lệ, in ra lịch bất kỳ. Có thể chứng minh rằng nếu tồn tại lịch ngủ hợp lệ thì cũng tồn tại lịch có không quá lần ngủ.
Ràng buộc
- .
- , , ; mọi giá trị là số nguyên.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 30 45 60 90 120 180 |
2 0 30 90 120 |
Ngủ phút từ đến : tỉnh táo tới phút và hoạt động được tới phút , đủ cho hai hoạt động đầu. Sau đó ngủ phút từ đến , hoạt động được tới phút , đúng lúc hoạt động cuối kết thúc. |
| 1 0 60 |
impossible | Bạn phải ngủ ngay tại phút , nhưng hoạt động duy nhất cũng bắt đầu tại phút . |
| 7 31 32 35 41 48 55 69 91 1000 2022 2022 2023 2994 4096 |
5 0 5 10 28 56 68 92 900 2025 2900 |
Chẳng hạn lần ngủ dài phút: không được ngủ trước phút , phải ngủ lại muộn nhất ở phút ; lần ngủ tiếp theo bắt đầu ở phút . Lần ngủ cuối giúp bạn hoạt động tới phút . |
Bình luận