Ba Đồng Xu
Đề bài
Mô tả
Có ba đồng xu được ký hiệu là A, B, C, đôi một có khối lượng khác nhau. Người ta cân từng cặp đồng xu trên cân thăng bằng và ghi lại kết quả của cả ba lần cân.
Mỗi kết quả là một dòng có đúng ba ký tự dạng trong đó:
- và là hai chữ cái khác nhau trong .
- là một trong hai ký tự hoặc , mang ý nghĩa khối lượng của lớn hơn hay nhỏ hơn khối lượng của .
Hãy xác định thứ tự khối lượng tăng dần của ba đồng xu, hoặc cho biết các kết quả cân là mâu thuẫn.
Một dòng nào đó không đúng định dạng nêu trên (chứa ký tự lạ, độ dài khác , hai chữ cái trùng nhau, v.v.) cũng được coi là kết quả không hợp lệ — trong trường hợp đó in ra Impossible.
Dữ liệu vào
Gồm đúng ba dòng, mỗi dòng là một kết quả cân theo định dạng đã mô tả ở trên. Mỗi cặp đồng xu được cân đúng một lần.
Dữ liệu ra
- Nếu các kết quả cân nhất quán: in ra một chuỗi gồm ba ký tự là hoán vị của , ứng với thứ tự khối lượng từ nhẹ nhất đến nặng nhất.
- Nếu có mâu thuẫn hoặc dữ liệu không hợp lệ: in ra
Impossible.
Ràng buộc
- Mỗi cặp trong xuất hiện đúng một lần.
- Không có hai đồng xu nào cùng khối lượng.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| C>A CB>A |
ACB | Suy ra B nặng nhất, kế tiếp là C, nhẹ nhất là A. |
| CBC>A | Impossible | Từ hai dòng đầu suy ra C < A, mâu thuẫn với dòng thứ ba. |
| A>B B>C C>A |
Impossible | Ba kết quả tạo thành vòng tròn A > B > C > A nên mâu thuẫn. |
Bình luận