双轨车皮编序问题

Description:

在一个列车调度站中，2 条轨道连接到2条侧轨处，形成2 个铁路转轨栈。其中左边轨道为车皮入口，编号为A；右边轨道为出口，编号为D，2 个铁路转轨栈分别编号为C和D，如下图所示。编号为a，b，…，的n 个车皮依序停放在车皮入口处。调度室要安排各车皮进出栈次序，使得在出口处各车皮按照预先指定的顺序依次出站。车皮移动时只能按照从左到右的方向移动。

给定车皮数n，以及各车皮的出站顺序，编程计算最优调度方案，使得移动车皮的总次数最少。

Input:

第一行有1 个正整数n，表示车皮数。接下来的1 行中，是预先指定的车皮出站顺序。

Output:

文件的第一行是最少移动次数m。接下来的m行是对应于最优方案的m次移动。每次移动用形如‘c X Y’的3 个字符来表示，其中c 表示车皮编号，X 表示起始栈轨号，Y 表示目标栈轨号。如果无法调度则输出“NoSolution!”。

Sample Input:

3
Abc

Sample Output:

5
c A B
b A B
a A D
b B D
c B D

Note:

undefined

本题由旧版NOJ导入，来源：算法设计与实验题解