#Pybt2420. 九连环
九连环
九连环
题目描述
九连环是我国的传统民间智力玩具,总共9个环互相连接。一些环在框柄上,一些不在,例如下图中第4和第9个环在框柄上,其他环不在。

我们称把某个环从框柄上取下为off操作,把环放到框柄上为on操作。
第1个环可以在任何时候取下或放上。对于大于1的整数n,必须恰好第n-1个环在框柄上,编号小于n-1的环都不在框柄上,才可以被取下或放上。
例如需要放上第5个环,那么得先保证第1,2,3个环不在框柄上,第4个环在框柄上,此时可以把第5个环放上框柄。
现在有一个连环,所有环都在框柄上。需要取下所有的环,输出步数最少的操作过程。
实际中第1个环和第2个环是可以一起取下或放上的,但为了处理方便,我们不允许它们同时操作。
输入格式
从标准输入读入数据。
一行一个正整数n,表示环的数量。保证n<=18。
输出格式
输出到标准输出。
输出若干行表示方案。每行为一个操作,格式为环的编号、操作名称,之间用一个空格隔开。
数据范围
(原站未提供,导入后需人工补齐)
样例
3
1 off
3 off
1 on
2 off
1 off
4
2 off
1 off
4 off
1 on
2 on
1 off
3 off
1 on
2 off
1 off
5
1 off
3 off
1 on
2 off
1 off
5 off
1 on
2 on
1 off
3 on
1 on
2 off
1 off
4 off
1 on
2 on
1 off
3 off
1 on
2 off
1 off