trang chủ / đề bài / icpcwf05_e

Nhiều nắng

Đề bài

Mô tả

Công ty Quản lý Xây dựng Chung cư (ACM) có một số toà chung cư cao tầng mới ở ngoại ô Thượng Hải. Với nền kinh tế đang bùng nổ, ACM kỳ vọng thu được lợi nhuận đáng kể từ việc cho thuê căn hộ. Công ty quảng cáo rằng căn hộ của họ đẹp hơn những căn hộ khác trong vùng vì nhận được nhiều ánh nắng trực tiếp hơn: không có toà nhà nào khác che đường ánh nắng chiếu tới các căn hộ trong những toà nhà cao của ACM.

ACM muốn kiểm chứng lời quảng cáo này bằng cách cho khách thuê tương lai biết chính xác một căn hộ nhận được bao nhiêu ánh nắng. Để đưa ra một mẫu đại diện về giờ nắng, công ty muốn quảng cáo giờ nắng của ngày 6 tháng 4 năm 2005. Ngày hôm đó ở Thượng Hải, mặt trời mọc lúc 5:37 sáng và lặn lúc 6:17 chiều.

Như hình trên, các căn hộ nằm trong một dãy toà nhà xếp thẳng hàng theo hướng đông tây (phía đông ở bên trái hình). Hai chữ số cuối của số hiệu căn hộ cho biết toà nhà, bắt đầu từ 01 cho toà nhà ở cực đông. Các chữ số còn lại cho biết tầng của căn hộ, với 1 là tầng trệt (tầng sát mặt đất). Chẳng hạn căn hộ 302 ở tầng 3 của toà nhà 2.

Mặt trời mọc ở phía đông và di chuyển trên bầu trời với tốc độ góc không đổi cho tới khi lặn ở phía tây (góc cao của mặt trời tăng đều từ 0∘ lúc mọc tới 180∘ lúc lặn, tính từ chân trời phía đông). Bóng râm chỉ do các toà nhà tạo ra (tức là mỗi toà nhà có thể đổ bóng lên một hoặc nhiều toà nhà khác). Một căn hộ được coi là nhận được ánh nắng khi bức tường ngoài phía đông hoặc bức tường ngoài phía tây của nó được ánh nắng phủ kín hoàn toàn, hoặc khi mặt trời ở ngay trên đỉnh đầu.

Mỗi toà nhà là một hình chữ nhật trong mặt phẳng thẳng đứng theo hướng đông tây: rộng w mét, cao bằng số căn hộ của nó nhân với h mét (mỗi tầng một căn hộ, mỗi căn hộ chiếm toàn bộ chiều rộng toà nhà). Khoảng cách giữa hai toà nhà liền nhau là khoảng cách giữa hai bức tường đối diện của chúng.

Dữ liệu vào

Dữ liệu gồm nhiều mô tả khu chung cư. Mỗi mô tả bắt đầu bằng một dòng chứa một số nguyên n là số toà nhà trong khu. Dòng tiếp theo chứa hai số nguyên w (chiều rộng toà nhà theo hướng đông tây) và h (chiều cao mỗi căn hộ), đơn vị mét. Dòng tiếp theo là dãy số nguyên m(1),d(1),m(2),d(2),…,d(n−1),m(n), trong đó m(i) là số căn hộ của toà nhà i và d(i) là khoảng cách (mét) giữa toà nhà i và toà nhà i+1.

Sau mô tả khu chung cư là một dòng chứa danh sách số hiệu các căn hộ cần hỏi giờ nắng, kết thúc bằng số 0.

Dữ liệu kết thúc bằng một dòng chứa số 0.

Dữ liệu ra

Với mỗi khu chung cư, in số thứ tự của nó trong dãy mô tả. Sau đó với mỗi căn hộ được hỏi, in khoảng thời gian căn hộ nhận được ánh nắng theo định dạng 24 giờ HH:MM:SS - HH:MM:SS. Làm tròn xuống mọi thời điểm tới giây gần nhất. Nếu số hiệu được hỏi không ứng với căn hộ nào, in rằng căn hộ đó không tồn tại. Theo đúng định dạng trong ví dụ.

Ràng buộc

  • 1≤n≤99.
  • 1≤w,h≤1000, 1≤m(i)≤1000, 1≤d(i)≤1000.
  • Mỗi số hiệu căn hộ được hỏi là số nguyên từ 1 đến 106 (có thể không ứng với căn hộ nào, chẳng hạn khi số tầng bằng 0, số toà nhà bằng 00 hoặc lớn hơn n, hoặc số tầng lớn hơn số căn hộ của toà nhà). Một khu chung cư có thể không có câu hỏi nào.
  • Mỗi file có không quá 100 khu chung cư và tổng số câu hỏi không quá 20000.
  • Thời điểm chính xác của mỗi đầu mút hoặc là một số nguyên giây, hoặc cách mọi số nguyên giây ít nhất 10−6 giây.

Ví dụ

Input Output Giải thích
3
6 4
5 6 3 3 4
302 401 601 303 0
4
5 3
4 5 7 8 5 4 3
101 302 503 0
0
Apartment Complex: 1
Apartment 302: 10:04:50 - 13:23:47
Apartment 401: 05:37:00 - 17:13:57
Apartment 601: Does not exist
Apartment 303: 09:21:19 - 18:17:00
Apartment Complex: 2
Apartment 101: 05:37:00 - 12:53:32
Apartment 302: 09:08:55 - 14:52:47
Apartment 503: 09:01:12 - 18:17:00
Khu 1 là hình trên. Căn hộ 302: chân tường phía đông cao 8 mét, cách toà 1 (cao 20 mét) 6 mét, nên tường phía đông được phủ nắng khi góc cao của mặt trời đạt arctan(12/6); tường phía tây bị toà 3 (cao 16 mét, cách 3 mét) che khi góc cao từ phía tây nhỏ hơn arctan(8/3). Toà 1 chỉ có 5 tầng nên căn hộ 601 không tồn tại.
1
10 3
4
101 401 501 100 1 0
2
2 2
2 4 1
101 201 102 0
0
Apartment Complex: 1
Apartment 101: 05:37:00 - 18:17:00
Apartment 401: 05:37:00 - 18:17:00
Apartment 501: Does not exist
Apartment 100: Does not exist
Apartment 1: Does not exist
Apartment Complex: 2
Apartment 101: 05:37:00 - 16:24:50
Apartment 201: 05:37:00 - 18:17:00
Apartment 102: 08:47:00 - 18:17:00
Ví dụ tự thêm. Khu 1 chỉ có một toà nhà nên mọi căn hộ có nắng suốt ngày; 100 là toà 00, 1 là tầng 0. Khu 2: căn hộ 102 bị toà 1 (cao 4 mét, cách 4 mét) che đúng tới góc 45∘, tức là 08:47:00.

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