3303: 「一本通 1.4 例 2」魔板

内存限制:512 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

**原题来自:USACO 3.2.5** Rubik 先生在发明了风靡全球魔方之后,又发明了它的二维版本——魔板。这是一张有 $8$ 个大小相同的格子的魔板: ```plain 1 2 3 4 8 7 6 5 ``` 我们知道魔板的每一个方格都有一种颜色。这 $8$ 种颜色用前 $8$ 个正整数来表示。可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。对于上图的魔板状态,我们用序列 $1,2,3,4,5,6,7,8$ 来表示。这是基本状态。 这里提供三种基本操作,分别用大写字母 `A`,`B`,`C` 来表示(可以通过这些操作改变魔板的状态): - `A`:交换上下两行; - `B`:将最右边的一列插入最左边; - `C`:魔板中央作顺时针旋转。 下面是对基本状态进行操作的示范: `A`: ```plain 8 7 6 5 1 2 3 4 ``` `B`: ```plain 4 1 2 3 5 8 7 6 ``` `C`: ```plain 1 7 2 4 8 6 3 5 ``` 对于每种可能的状态,这三种基本操作都可以使用。 你要编程计算用最少的基本操作完成基本状态到特殊状态的转换,输出基本操作序列。

输入

输入仅一行,包括 $8$ 个整数,用空格分开,表示目标状态。

输出

输出文件的第一行包括一个整数,表示最短操作序列的长度。 第二行为在字典序中最早出现的操作序列。

样例输入 复制

2 6 8 4 5 7 3 1

样例输出 复制

7
BCABCCB

提示


数据范围:输入数据中的所有数字均为 $1$ 到 $8$ 之间的整数。

来源/分类