trang chủ / đề bài / icpcwf04_i

Hồi hộp!

Đề bài

Mô tả

Jan và Tereza sống ở hai toà nhà sát nhau, căn hộ của hai bạn nhìn thẳng sang nhau. Trong dự án khoa học ở trường, hai bạn muốn làm một cây cầu treo thu nhỏ bằng dây thừng, dây nhỏ và bìa cứng nối hai toà nhà. Hai sợi dây thừng có độ dài bằng nhau làm hai dây cáp treo chính, được buộc vào mép dưới cửa sổ của hai bạn. "Mặt cầu" bằng bìa cứng được giữ bởi nhiều sợi dây nhỏ buộc vào các dây cáp chính. Mặt cầu nằm ngang và thấp hơn đúng một mét so với điểm thấp nhất của dây cáp. Vì lý do thẩm mỹ, mặt cầu phải thấp hơn mép dưới của cửa sổ thấp hơn trong hai cửa sổ của hai bạn ít nhất hai mét. Theo các định luật vật lý, mỗi dây cáp treo có dạng một đường parabol.

Dù Jan và Tereza không định đi lại trên cây cầu mô hình này, vẫn có một vấn đề nghiêm trọng: một số người trong hai toà nhà nuôi mèo, một số khác nuôi chim. Jan và Tereza muốn chắc chắn rằng cây cầu không tạo ra đường để một con mèo tới được chỗ một con chim. Hai bạn quan sát thấy mèo không nhảy lên cao được tới 0,5 mét, và sẽ không nhảy xuống từ độ cao tới 3 mét. Vì vậy, nếu mặt cầu cao hơn mép dưới cửa sổ của một con mèo ít nhất 0,5 mét, hoặc thấp hơn mép dưới cửa sổ đó ít nhất 3 mét, thì con mèo sẽ không nhảy lên mặt cầu. Tương tự, một con mèo đã lên được mặt cầu sẽ không thể tới cửa sổ của một con chim nếu mặt cầu thấp hơn mép dưới cửa sổ của con chim ít nhất 0,5 mét, hoặc cao hơn mép dưới cửa sổ đó ít nhất 3 mét. Mèo chỉ quan tâm tới việc tới được chỗ chim, không bận tâm chuyện quay về nhà.

Hình dưới đây vẽ căn hộ của Jan ("J") và căn hộ của Tereza ("T") với một dây cáp nối mép dưới cửa sổ của hai bạn và mặt cầu bằng bìa cứng thấp hơn điểm thấp nhất của dây cáp một mét. Con mèo ở tầng 2 có thể tới con chim ở tầng 2 qua cây cầu.

Bạn cần viết chương trình xác định Jan và Tereza cần bao nhiêu dây thừng để làm mỗi dây cáp của một cây cầu không gây nguy hiểm cho con chim nào trong hai toà nhà.

Cho khoảng cách giữa hai toà nhà (tính bằng mét), số tầng của căn hộ Jan và của căn hộ Tereza (ở mỗi toà, tầng thấp nhất, tức tầng trệt, có số 1), loại vật nuôi ở mọi tầng từ tầng 1 tới tầng của Jan trong toà của Jan, và loại vật nuôi ở mọi tầng từ tầng 1 tới tầng của Tereza trong toà của Tereza. Chương trình phải xác định độ dài lớn nhất của dây cáp có thể dùng để treo một cây cầu giữa hai toà nhà mà không cho phép con mèo nào tới được con chim nào nhờ cây cầu. Mặt cầu phải cao hơn mặt đất ít nhất 1 mét và phải thấp hơn đúng một mét so với điểm thấp nhất của dây cáp treo. Mặt cầu cũng phải thấp hơn cửa sổ thấp hơn trong hai cửa sổ của Jan và Tereza ít nhất hai mét. Mọi phòng trong hai toà nhà cao đúng 3 mét; mọi cửa sổ cao đúng 1,5 mét và mép dưới của mỗi cửa sổ cao hơn sàn phòng đúng 1 mét.

Như vậy, mép dưới cửa sổ ở tầng k (của cả hai toà) cao 3(k−1)+1 mét so với mặt đất. Mỗi dây cáp là một cung parabol (trục thẳng đứng) nối mép dưới cửa sổ của Jan và mép dưới cửa sổ của Tereza, hai điểm này cách nhau d mét theo phương ngang. Mèo và chim ở cả hai toà nhà đều được xét (một con mèo có thể tới con chim ở cùng toà nhà với nó nhờ cây cầu). Các tầng cao hơn tầng của Jan (hoặc của Tereza) không được cho và không cần xét.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, mỗi bộ test gồm ba dòng.

  • Dòng đầu chứa hai số nguyên dương j và t (2≤j,t≤25) lần lượt là tầng của Jan và tầng của Tereza, và một số thực d (1≤d≤25) là khoảng cách giữa hai toà nhà, tính bằng mét.
  • Dòng thứ hai chứa j chữ cái in hoa ℓ1,ℓ2,…,ℓj cách nhau bởi dấu cách. Chữ cái ℓk là B nếu ở tầng k của toà nhà của Jan có một con chim, C nếu ở tầng k có một con mèo, và N nếu ở tầng k không có loại vật nuôi nào trong hai loại trên.
  • Dòng thứ ba chứa t chữ cái in hoa, cho thông tin tương tự về các tầng của toà nhà của Tereza.

Sau bộ test cuối cùng là một dòng chứa ba số 0.

Dữ liệu ra

Với bộ test thứ k (k=1,2,…), in một dòng Case k: c, trong đó c là giá trị lớn nhất sao cho có thể dùng hai dây cáp, mỗi dây dài c, để treo một cây cầu từ mép dưới cửa sổ của Jan và của Tereza thoả mãn: mặt cầu thấp hơn điểm thấp nhất của dây cáp đúng một mét, cao hơn mặt đất ít nhất 1 mét, thấp hơn cửa sổ của Jan và của Tereza ít nhất hai mét, và không cho phép con mèo nào tới được con chim nào. Độ dài được làm tròn đến đúng ba chữ số sau dấu thập phân. Nếu không thể làm được cây cầu như vậy, in Case k: impossible. In một dòng trống giữa kết quả của hai bộ test liên tiếp. Định dạng phải giống ví dụ.

Ràng buộc

  • 2≤j,t≤25; 1≤d≤25, d có không quá 3 chữ số sau dấu thập phân.
  • Mỗi file có không quá 1000 bộ test.
  • Với mỗi bộ test có đáp án, độ dài đúng cách mọi giá trị có chữ số thập phân thứ tư đúng bằng 5 (trường hợp làm tròn nước đôi) ít nhất 10−6.

Ví dụ

Input Output Giải thích
4 3 5.0
N C N C
N B B
4 3 5.0
C B C C
B C B
0 0 0
Case 1: 14.377

Case 2: impossible
Bộ test 1: mép dưới cửa sổ của Jan cao 10 m, của Tereza cao 7 m. Mặt cầu có thể đặt ở độ cao thấp nhất là 1 m (mèo ở độ cao 4 m và 10 m không nhảy lên được), nên điểm thấp nhất của dây cáp cao 2 m. Bộ test 2: mọi độ cao mặt cầu từ 1 m tới 5 m đều cho phép một con mèo tới một con chim.
3 3 4.5
C N N
B N N
2 3 2.5
C C
B N N
3 3 2.5
C C N
B N N
25 2 25
B B B B B B B B B B B B B B B B B B B B B B B B B
N N
0 0 0
Case 1: 10.455

Case 2: impossible

Case 3: 4.925

Case 4: 80.219
Ví dụ tự thêm. Bộ test 1: mặt cầu cao 1,5 m (cao hơn mép cửa sổ của con mèo đúng 0,5 m là được phép). Bộ test 2: mặt cầu phải cao ít nhất 4 m nhưng không được cao quá 2 m. Bộ test 3: mặt cầu cao 4 m. Bộ test 4: không có mèo, mặt cầu cao 1 m.

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