N阶汉诺塔变形
题号:NC14968
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

    相信大家都知道汉诺塔问题。那么现在对汉诺塔问题做一些限制,成为一个新的玩法。

    在一个底座上,从左到右有三个分别命名为A、B和C的塔座,有n个大小不一的圆盘。这些圆盘一开始,从小到大按顺序叠加在塔座A上,形成一座上小下大的塔,塔座B和C为空。我们将n个圆盘,从小到大编号为1~n。现要求将塔座A上的n个圆盘移至塔座C上并仍按照同样的顺序叠排,圆盘移动时必须遵循以下规则:
    (1)每次只能将一个圆盘从一个塔座移动到相邻的塔座上
    (2)所有圆盘可以叠在A、B和C中的任一塔座上

    (3)任何时刻都不能将一个较大的圆盘压在较小的圆盘上面

    那么问题来了,对于一个n阶(阶数即是问题中圆盘的个数)的上述问题,用最少操作次数将圆盘塔从塔座A移动到塔座C的操作总是固定的。请问,n阶问题执行k步操作后,塔座A、B和C上圆盘的情况是怎样的?从大到小输出三个塔座上的圆盘的编号(如果该塔座上没有圆盘,请输出0)。

比如,塔座A上有圆盘1,3;塔座B上有圆盘2;塔座C上有圆盘4。我们将输出:

3 1

2

4

输入描述:

数据有多组,处理到文件结束。
每组数据一行输入,有两个整数n和k,n代表问题的阶数,k代表执行的步数。

输出描述:

每组数据输出占三行。
第一行描述塔座A的情况。
第二行描述塔座B的情况。
第三行描述塔座C的情况。
示例1

输入

复制
3 5
4 10

输出

复制
3 1
2
0
4
3 1
2

备注:

10000组数据。
对于100%的数据,
1 <= n < 40;
1 <= k < (3^n)。