Submit solution

Points: 400 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem types

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. 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. 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.

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

  • A: Đổi chỗ dòng trên và dòng dưới.
  • B: Thực hiện một 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 mô tả trong hình 2, với giả thiết trước khi thực hiện một phép biến đổi bất kỳ bảng đều đang ở trạng thái khởi đầu.

Hình 1:        Hình 2:

1 2 3 4 -----> 8 7 6 5
8 7 6 5   A    1 2 3 4

        -----> 4 1 2 3
          B    5 8 7 6

        -----> 1 7 2 4
          C    8 6 3 5

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

Dữ liệu

  • Chứa 8 số nguyên dương trong dòng đầu tiên mô tả trạng thái đích.

Kết quả

  • Số phép biến đổi ít nhất.

Input

2 6 8 4 5 7 3 1

Output

7

Nguồn: 3D 20172018


Be the first to comment

Comments

There are no comments at the moment.