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 mét, và sẽ không nhảy xuống từ độ cao tới 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 mét, hoặc thấp hơn mép dưới cửa sổ đó ít nhất 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 mét, hoặc cao hơn mép dưới cửa sổ đó ít nhất 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 có thể tới con chim ở tầng 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ố ), loại vật nuôi ở mọi tầng từ tầng 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 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 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 mét; mọi cửa sổ cao đúng mét và mép dưới của mỗi cửa sổ cao hơn sàn phòng đúng mét.
Như vậy, mép dưới cửa sổ ở tầng (của cả hai toà) cao 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 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 và () lần lượt là tầng của Jan và tầng của Tereza, và một số thực () là khoảng cách giữa hai toà nhà, tính bằng mét.
- Dòng thứ hai chứa chữ cái in hoa cách nhau bởi dấu cách. Chữ cái là
Bnếu ở tầng của toà nhà của Jan có một con chim,Cnếu ở tầng có một con mèo, vàNnếu ở tầng không có loại vật nuôi nào trong hai loại trên. - Dòng thứ ba chứa 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ố .
Dữ liệu ra
Với bộ test thứ (), in một dòng Case k: c, trong đó là giá trị lớn nhất sao cho có thể dùng hai dây cáp, mỗi dây dài , để 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 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
- ; , có không quá chữ số sau dấu thập phân.
- Mỗi file có không quá 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 (trường hợp làm tròn nước đôi) ít nhất .
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 m, của Tereza cao m. Mặt cầu có thể đặt ở độ cao thấp nhất là m (mèo ở độ cao m và m không nhảy lên được), nên điểm thấp nhất của dây cáp cao m. Bộ test 2: mọi độ cao mặt cầu từ m tới 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 m (cao hơn mép cửa sổ của con mèo đúng m là được phép). Bộ test 2: mặt cầu phải cao ít nhất m nhưng không được cao quá m. Bộ test 3: mặt cầu cao m. Bộ test 4: không có mèo, mặt cầu cao m. |
https://oj.chuyentin.pro/problem/icpcwf04_i
Bình luận