trang chủ / đề bài / fruitcard

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 x quả cam và y quả táo.

Đầu tiên Alice lấy từ túi 1 quả cam, Bob lấy từ túi 1 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 x và y, 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 x và y, 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á 106 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á 106 ký tự.

Ràng buộc

  • 1≤x,y≤1018
  • x·y>1

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

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