THỰC HÀNH

Kế tục thành công của trò chơi với khối lập phương thần bí, Ngài Rubik sáng tạo ra dạng phẳng của trò chơi này gọi là trò chơi các ô vuông thần bí. Đây là một bảng gồm 8 ô vuông bằng nhau (xem hình 1).

Trong bài này chúng ta xét bảng trong đó mỗi ô vuông có một mầu khác nhau. Các mầu được ký hiệu bởi 8 số nguyên dương đầu tiên (xem hình 1). Trạng thái của bảng được cho bởi dãy ký hiệu mầu của các ô được viết lần lượt theo chiều kim đồng hồ bắt đầu từ ô ở góc trái trên và kết thúc tại ô ở góc trái dưới. Ví dụ, trạng thái của bảng trong hình 1 được cho bởi dãy (1,2,3,4,5,6,7,8). Trạng thái này được gọi là trạng thái khởi đầu.

Hình 1

Có thể dùng 3 phép biến đổi cơ bản đối với bảng có tên là 'A', 'B' và 'C':

• 'A': đổi chỗ dòng trên và dòng dưới,
• 'B': thực hiện một phép hoán vị vòng quanh sang phải,
• 'C': quay theo chiều kim đồng hồ bốn ô giữa.

Hình 2

Biết rằng từ trạng thái khởi đầu luôn có thể chuyển về một trạng thái bất kỳ bằng cách dùng các phép biến đổi cơ bản nói trên.

Tác động của ba phép biến đổi cơ bản được mô tả trong hình 2, trong đó các số viết bên cạnh bảng dùng để chỉ vị trí các ô vuông của bảng và ô vuông ở vị trí p chứa số i có nghĩa là, sau khi áp dụng phép biến đổi tương ứng, ô vuông mà vị trí trước khi biến đổi của nó là i được chuyển đến vị trí p.

Yêu cầu: tìm dãy các phép biến đổi cơ bản để chuyển bảng từ trạng thái khởi đầu cho trong hình 1 về một trạng thái đích cho trước với ít phép biến đổi nhất.

Dữ liệu vào

Một dòng chứa 8 số nguyên dương mô tả trạng thái đích.

Dữ liệu ra

• Trong dòng đầu tiên ghi số L là số lượng phép biến đổi của dãy các phép biến đổi tìm được.
• Dòng tiếp theo ghi một dãy ký tự là tên các phép biến đổi cơ bản theo trình tự thực hiện.

Ví dụ:

Dữ liệu vào:
2 6 8 4 5 7 3 1
Dữ liệu ra:
7
BCABCCB