Xét một
bảng có 8 ô vuông trong đó mỗi ô vuông có một màu khác nhau, các mùa được ký hiệu
bởi 8 số nguyên dương đầu tiên. Các 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 ở góc trái dưới.
1
|
2
|
3
|
4
|
8
|
7
|
6
|
5
|
Ví dụ trạng
thái của bảng trong hình trên đượ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.
Có thể
dùng 3 phép biến đổi cơ bản có tên là ‘A’, ‘B’, ‘C’ trong đó:
‘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ồ 4 ô giữa
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 3 phép biến đổi cơ bản được
mô tả trong hình sau:
+ Phép A
1
|
2
|
3
|
4
|
1
|
2
|
3
|
4
|
|
1
|
2
|
3
|
4
|
A
→
|
8
|
7
|
6
|
5
|
8
|
7
|
6
|
5
|
1
|
2
|
3
|
4
|
|
8
|
7
|
6
|
5
|
8
|
7
|
6
|
5
|
+ Phép B
1
|
2
|
3
|
4
|
1
|
2
|
3
|
4
|
|
1
|
2
|
3
|
4
|
B
→
|
4
|
1
|
2
|
3
|
8
|
7
|
6
|
5
|
5
|
8
|
7
|
6
|
|
8
|
7
|
6
|
5
|
8
|
7
|
6
|
5
|
+ Phép C
1
|
2
|
3
|
4
|
1
|
2
|
3
|
4
|
|
1
|
2
|
3
|
4
|
C
→
|
1
|
7
|
2
|
4
|
8
|
7
|
6
|
5
|
8
|
6
|
3
|
5
|
|
8
|
7
|
6
|
5
|
8
|
7
|
6
|
5
|
Trong đó
các số viết bên cạnh bảng dùng để chỉ 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: Viết chương trình tìm dãy biến đổi cơ bản để
chuyển bảng từ trạng thái khởi đầu về một trạng thái cho trước sao cho số phép
biến đổi là ít nhất có thể.
Dữ liệu vào: File OVUONG.INP chứa 8 số
nguyên liền nhau mô tả trạng thái đích
Dữ liệu ra: ghi vào file OVUONG.OUT
+ Dòng đầu
tiên ghi số phép biến đổi của dãy
+ Các
dòng tiếp theo ghi dãy các phép biến đổi theo thứ tự, mỗi phép biến đổi ghi
trên một dòng
Ví dụ:
OVUONG.INP
|
OVUONG.OUT
|
26845731
|
7
B
C
A
B
C
C
B
|
