Các khoảng ngày giao nhau
Đề bài
Mô tả
Một nhóm nghiên cứu đang phát triển chương trình lấy dữ liệu giá chứng khoán trong quá khứ từ một dịch vụ thu một khoản phí cố định cho dữ liệu của mỗi ngày mà dịch vụ cung cấp. Nhóm đã xem lại các yêu cầu dữ liệu trước đây và phát hiện rất nhiều yêu cầu bị trùng lặp, gây lãng phí tiền. Vì vậy chương trình mới sẽ lưu danh sách mọi dữ liệu giá đã được các thành viên trong nhóm yêu cầu. Khi cần thêm dữ liệu, chương trình chỉ lấy từ dịch vụ dữ liệu của những ngày chưa từng được lấy, nhờ đó chi phí là nhỏ nhất.
Bạn cần viết chương trình xác định khi nào cần lấy dữ liệu mới. Dữ liệu vào của chương trình gồm các khoảng ngày đã được yêu cầu dữ liệu trong quá khứ và các khoảng ngày cần dữ liệu. Chương trình phải xác định các khoảng ngày cần lấy dữ liệu từ dịch vụ.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng hai số nguyên không âm và (): là số khoảng ngày đã được yêu cầu dữ liệu trong quá khứ, là số khoảng ngày trong các yêu cầu mới. Tiếp theo là cặp ngày, mỗi cặp trên một dòng. Ngày thứ nhất của mỗi cặp không muộn hơn ngày thứ hai. cặp đầu tiên là các khoảng ngày đã được yêu cầu và đã lấy dữ liệu trong quá khứ, cặp tiếp theo là các khoảng ngày cần dữ liệu. Mỗi khoảng gồm cả hai ngày đầu mút.
Sau bộ test cuối cùng là một dòng chứa hai số .
Mỗi ngày được cho dưới dạng YYYYMMDD: YYYY là năm (từ đến ), MM là tháng (từ 01 đến 12) và DD là ngày (trong phạm vi hợp lệ của tháng và năm đó). Nhắc lại: các tháng 04, 06, 09, 11 có ngày; các tháng 01, 03, 05, 07, 08, 10, 12 có ngày; tháng 02 có ngày, trừ năm nhuận thì có ngày. Một năm là năm nhuận nếu nó chia hết cho và không phải năm tròn thế kỷ (bội của ), hoặc nếu nó chia hết cho .
Dữ liệu ra
Với mỗi bộ test, in một dòng Case k: với là số thứ tự của bộ test (), sau đó là danh sách các khoảng ngày cần lấy dữ liệu từ dịch vụ, mỗi khoảng trên một dòng, theo đúng định dạng ngày kiểu Mỹ M/D/YYYY như ví dụ (tháng và ngày không có chữ số ở đầu), mỗi dòng lùi vào hai dấu cách. Một khoảng được in dạng M/D/YYYY to M/D/YYYY.
- Nếu không cần lấy thêm dữ liệu nào, in dòng
No additional quotes are required.(lùi vào hai dấu cách) như ví dụ. - Nếu hai khoảng ngày liền nhau hoặc giao nhau thì gộp chúng thành một khoảng.
- Nếu một khoảng chỉ gồm một ngày, in ngày đó một lần, không in dạng khoảng có hai ngày giống nhau.
- In các khoảng theo thứ tự thời gian, bắt đầu từ khoảng sớm nhất.
In một dòng trống giữa hai bộ test liên tiếp.
Ràng buộc
- và trong mỗi bộ test.
- Mọi ngày đều hợp lệ, nằm trong các năm từ đến ; ngày thứ nhất của mỗi cặp không muộn hơn ngày thứ hai.
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 1 19900101 19901231 19901201 20000131 0 3 19720101 19720131 19720201 19720228 19720301 19720301 1 1 20010101 20011231 20010515 20010901 0 0 |
Case 1: 1/1/1991 to 1/31/2000 Case 2: 1/1/1972 to 2/28/1972 3/1/1972 Case 3: No additional quotes are required. |
Bộ test 1: đã có dữ liệu cả năm . Bộ test 2: hai khoảng đầu liền nhau nên được gộp; năm là năm nhuận nên ngày không được yêu cầu và ngày là một khoảng riêng. Bộ test 3: khoảng cần dữ liệu nằm trọn trong khoảng đã có. |
| 2 2 19000101 19000227 19000301 19001231 18991231 19000301 20000228 20000301 0 2 21001231 21001231 17000101 17000101 1 0 17000101 21001231 0 3 20040301 20040331 20040101 20040228 20040229 20040229 0 0 |
Case 1: 12/31/1899 2/28/1900 2/28/2000 to 3/1/2000 Case 2: 1/1/1700 12/31/2100 Case 3: No additional quotes are required. Case 4: 1/1/2004 to 3/31/2004 |
Ví dụ tự thêm. Bộ test 1: năm không nhuận nên sau là (đã có); năm nhuận nên khoảng thứ hai gồm ngày. Bộ test 2: các khoảng được in theo thứ tự thời gian, không theo thứ tự trong dữ liệu vào. Bộ test 3: không có yêu cầu mới. Bộ test 4: ba khoảng liền nhau được gộp thành một. |
https://oj.chuyentin.pro/problem/icpcwf04_e
Bình luận