Chèn chuyến cất cánh
Đề bài
Mô tả
Một đường băng đang có lịch chuyến hạ cánh, mỗi chuyến chiếm đúng phút. Bạn cần chèn thêm một chuyến cất cánh cũng kéo dài phút vào lịch này.
Vì lý do an toàn, giữa chuyến cất cánh và mọi chuyến hạ cánh phải có khoảng cách ít nhất phút ở cả hai phía. Cụ thể, nếu một chuyến hạ cánh bắt đầu ở phút (chiếm phút ) và chuyến cất cánh bắt đầu ở phút (chiếm phút ), thì phải có hoặc .
Thời điểm hiện tại được tính là giờ phút. Hãy tìm thời điểm sớm nhất kể từ hiện tại có thể chèn chuyến cất cánh.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (giờ và phút) là thời điểm một chuyến hạ cánh, tính từ thời điểm hiện tại. Các thời điểm được cho theo thứ tự tăng dần.
Dữ liệu ra
In ra hai số nguyên và là giờ và phút của thời điểm sớm nhất kể từ hiện tại có thể chèn chuyến cất cánh. Lưu ý thời điểm này có thể vượt quá giờ.
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 60 0 0 1 20 3 21 5 0 19 30 23 40 |
6 1 | Không thể chèn giữa 1:20 và 3:21 vì mỗi chuyến chiếm phút nên khoảng trống không đủ phút mỗi bên. Khe trống đầu tiên đủ rộng nằm sau chuyến 5:00, cho phép cất cánh sớm nhất lúc 6:01. |
| 16 50 0 30 1 20 3 0 4 30 6 10 7 50 9 30 11 10 12 50 14 30 16 10 17 50 19 30 21 10 22 50 23 59 |
24 50 | Lịch dày đặc, không có khe trống nào đủ rộng nên chỉ có thể cất cánh sau chuyến cuối cùng. Kết quả vượt quá giờ. |
| 3 17 0 30 1 0 12 0 |
0 0 | Có thể cất cánh ngay lúc 0:00 vì chuyến hạ cánh đầu tiên (0:30) cách đủ xa. |
Bình luận