Cam, táo và dãy thẻ
Đề bài
Mô tả
Alice và Bob cùng chia nhau một túi hoa quả chứa quả cam và quả táo.
Đầu tiên Alice lấy từ túi quả cam, Bob lấy từ túi quả táo. Sau đó họ chơi một trò chơi với một dãy các lá thẻ, mỗi lá ghi chữ 'A' hoặc chữ 'B'. Các lá thẻ được bỏ đi lần lượt từ trái sang phải:
- Nếu lá thẻ ghi 'A': Alice đưa cho Bob toàn bộ số quả cô đang cầm, rồi lấy từ túi đúng bằng số cam và số táo vừa đưa đi. Như vậy số quả trên tay Alice không thay đổi, còn Bob nhận thêm đúng chừng ấy quả.
- Nếu lá thẻ ghi 'B': Bob làm điều tương tự với Alice.
Sau khi lá thẻ cuối cùng được bỏ đi, túi hoa quả vừa đúng hết sạch.
Biết và , hãy tìm một dãy thẻ thoả mãn, hoặc cho biết không tồn tại.
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và , lần lượt là số cam và số táo có trong túi lúc đầu.
Dữ liệu ra
Nếu không tồn tại dãy thẻ nào thoả mãn, in ra một từ duy nhất Impossible.
Ngược lại, in ra dãy thẻ dưới dạng nén: mỗi đoạn gồm các ký tự giống nhau liên tiếp được thay bằng số lần lặp rồi đến ký tự đó. Ví dụ chuỗi AAABAABBB được nén thành 3A1B2A3B; các cách viết 2A1A1B2A3B hay 3AB2A3B đều không hợp lệ vì không gộp trọn vẹn từng đoạn ký tự giống nhau.
Chuỗi in ra có không quá ký tự. Dữ liệu đảm bảo nếu đáp án tồn tại thì dạng nén của nó dài không quá ký tự.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 4 | 3B | Alice cầm 1 cam, Bob cầm 1 táo. Mỗi lá thẻ 'B' khiến Bob đưa 1 quả táo cho Alice rồi lấy lại 1 quả táo từ túi. Sau 3 lá thẻ, Alice có 1 cam và 3 táo, Bob có 1 táo, túi rỗng. Tổng cộng đúng 1 cam và 4 táo. |
| 2 2 | Impossible | Một lá thẻ là không đủ để hết túi, còn hai lá thẻ sẽ sinh ra ít nhất 3 quả cam hoặc 3 quả táo. |
| 3 2 | 1A1B | Dãy thẻ là AB. Sau lá thẻ 'A', Bob có 1 cam và 1 táo. Sau lá thẻ 'B', Alice có 2 cam và 1 táo. Tổng cộng 3 cam và 2 táo. |
Bình luận