trang chủ / đề bài / icpcwf24_c

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 d ngày mỗi năm, trong y năm liên tiếp gần nhất. Các năm này được tính theo từng khoảng 12 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ó 12 tháng với tổng cộng 365 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 d ngày trong mỗi khoảng 12 tháng: từ 2023-09-19 đến 2024-09-18, từ 2022-09-19 đến 2023-09-18, và cứ thế cho đủ y khoảng như vậy.

Bạn đã sống ở quốc gia này ít nhất y 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 n, y và d (1≤n≤500, 1≤y≤1000, 1≤d≤365). Bạn đã ra khỏi đất nước n lần, còn y và d mô tả yêu cầu cư trú của quốc gia như trên.

Mỗi dòng trong n dòng tiếp theo chứa hai ngày theo dạng YYYY-MM-DD (0000≤ YYYY ≤5000, 01≤ MM ≤12, 01≤ DD ≤31). 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

  • 1≤n≤500, 1≤y≤1000, 1≤d≤365.
  • Năm của mọi ngày trong dữ liệu vào nằm trong đoạn [0,5000]; 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ó 125 ngày vắng mặt, tức đúng 240 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ó 239 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 240 ngày có mặt; chuyến đi năm 2022 nằm ngoài 5 khoảng cần xét.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0