trang chủ / đề bài / icpcwf04_e

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 NX và NR (0≤NX,NR≤100): NX là số khoảng ngày đã được yêu cầu dữ liệu trong quá khứ, NR là số khoảng ngày trong các yêu cầu mới. Tiếp theo là NX+NR 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. NX 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ứ, NR 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ố 0.

Mỗi ngày được cho dưới dạng YYYYMMDD: YYYY là năm (từ 1700 đến 2100), 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ó 30 ngày; các tháng 01, 03, 05, 07, 08, 10, 12 có 31 ngày; tháng 02 có 28 ngày, trừ năm nhuận thì có 29 ngày. Một năm là năm nhuận nếu nó chia hết cho 4 và không phải năm tròn thế kỷ (bội của 100), hoặc nếu nó chia hết cho 400.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case k: với k là số thứ tự của bộ test (1,2,…), 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ố 0 ở đầ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

  • 0≤NX,NR≤100 và NX+NR≥1 trong mỗi bộ test.
  • Mọi ngày đều hợp lệ, nằm trong các năm từ 1700 đến 2100; 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á 500 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 1990. Bộ test 2: hai khoảng đầu liền nhau nên được gộp; năm 1972 là năm nhuận nên ngày 29/2/1972 không được yêu cầu và ngày 1/3/1972 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 1900 không nhuận nên sau 28/2/1900 là 1/3/1900 (đã có); năm 2000 nhuận nên khoảng thứ hai gồm 3 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.

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