Problem N: 九连环

Problem N: 九连环

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

SubmitProblemListSolved: 1Submit Num: 2StatisticsShowOff!

Description

九连环是中国传统益智玩具，它由由九个相互连接的环组成，这九个环套在一个中空的环柄中。九连环的玩法是要将这九个环从柄上解下来。
每个圆环有套上和取下两种状态，当所有圆环都取下时，就完成了解九连环。

九连环的结构限制了玩家可以操作的环
1. 1号环可以在任何时候套上或取下。
2. 还套在环柄上的第二个环可以套上或取下。

以下使用一个二进制串表示一个连环的状态，1表示该环套在环柄上，0表示该环已经取下。
二进制串从左到右分别表示1号环，2号环，...
例：010表示1号环以取下，2号环已套上，3号环已取下

本题要求：输入n，输出解n连环的步骤
要求按如下方式输出
此次操作的环编号:操作（0表示取下，1表示套上） 操作后九连环状态
例如：将1号环取下，操作后九连环状态为：1号环以取下，2号环已套上，3号环已取下，输出：
1:0 010

Input

一个整数(1<=n<=10)

Output

按照要求每行输出每一步九连环的操作
最后一行输出总操作步数

Sample 1 Input 

3

Sample 1 Output 

1:0 011
3:0 010
1:1 110
2:0 100
1:0 000
5
先将1号环拿下来
而后拿下3号环
再套上1号环
再拿下2号环
再拿下1号环

Sample 2 Input 

2

Sample 2 Output 

2:0 10
1:0 00
2

Sample 3 Input 

1

Sample 3 Output 

1:0 0
1
Submit