Nhập quốc tịch
Đề bài
Mô tả
Đã khá lâu kể từ khi bạn chuyển đến sống ở một quốc gia khác, và bạn quyết định đã đến lúc trở thành công dân của nước này. Quốc gia mới của bạn có yêu cầu cư trú rất nghiêm ngặt đối với mọi người nộp đơn. Để được nộp đơn, bạn phải có mặt trên lãnh thổ quốc gia này ít nhất ngày mỗi năm, trong năm liên tiếp gần nhất. Các năm này được tính theo từng khoảng tháng, đếm ngược từ ngày nộp đơn.
Trong bài này, giả sử một năm dương lịch có tháng với tổng cộng ngày, và số ngày của mỗi tháng đúng như bảng sau:
| Tháng | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Số ngày | 31 | 28 | 31 | 30 | 31 | 30 | 31 | 31 | 30 | 31 | 30 | 31 |
Ví dụ, nếu bạn nộp đơn vào ngày 2024-09-19, bạn phải có mặt trong nước ít nhất ngày trong mỗi khoảng tháng: từ 2023-09-19 đến 2024-09-18, từ 2022-09-19 đến 2023-09-18, và cứ thế cho đủ khoảng như vậy.
Bạn đã sống ở quốc gia này ít nhất năm, nhưng vì đi lại rất nhiều nên bạn không chắc mình có đáp ứng yêu cầu cư trú hay không. Hãy viết chương trình tìm ngày sớm nhất bạn có thể nộp đơn xin nhập quốc tịch, dựa trên lịch sử đi lại của bạn.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , và (, , ). Bạn đã ra khỏi đất nước lần, còn và mô tả yêu cầu cư trú của quốc gia như trên.
Mỗi dòng trong dòng tiếp theo chứa hai ngày theo dạng YYYY-MM-DD ( YYYY , MM , DD ). Bạn ở ngoài đất nước từ ngày thứ nhất đến ngày thứ hai, tính cả hai ngày này.
Mọi ngày trong dữ liệu vào được sắp xếp theo thứ tự tăng dần. Chỉ hai ngày trên cùng một dòng mới có thể bằng nhau. Mọi ngày cho trong dữ liệu vào đều hợp lệ.
Dữ liệu ra
In ra ngày sớm nhất mà bạn đáp ứng yêu cầu cư trú, theo cùng dạng YYYY-MM-DD. Ngày này phải sau ngày cuối cùng trong dữ liệu vào.
Ràng buộc
- , , .
- Năm của mọi ngày trong dữ liệu vào nằm trong đoạn ; mọi ngày đều hợp lệ theo bảng trên (không có năm nhuận).
- Các ngày được sắp xếp tăng dần; chỉ hai ngày trên cùng một dòng có thể bằng nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 240 2022-02-28 2022-10-01 2022-11-11 2022-11-11 2023-12-30 2024-01-01 |
2024-05-31 | Khoảng từ 2022-05-31 đến 2023-05-30 có ngày vắng mặt, tức đúng ngày có mặt; các khoảng khác đều đủ. Nộp ngày 2024-05-30 thì khoảng từ 2022-05-30 đến 2023-05-29 chỉ có ngày có mặt. |
| 3 5 240 2011-11-11 2012-12-12 2022-02-28 2022-10-01 2025-01-01 2025-06-30 |
2028-02-26 | Khoảng từ 2025-02-26 đến 2026-02-25 có đúng ngày có mặt; chuyến đi năm 2022 nằm ngoài khoảng cần xét. |
Bình luận