NC14968. N阶汉诺塔变形
描述
相信大家都知道汉诺塔问题。那么现在对汉诺塔问题做一些限制，成为一个新的玩法。
在一个底座上，从左到右有三个分别命名为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
C++14(g++5.4) 解法, 执行用时: 40ms, 内存消耗: 608K, 提交时间: 2018-07-17 15:17:15
#include <iostream>
#include <vector>
using namespace std;
long long n,k;
int main() {
while(cin >> n >> k) {
vector<int> v[3];
long long base = 1;
for(int i = 1;i <= n;i++) {
int t = (k / base) % 6;
if(t > 2)
t = 5 - t;
v[t].push_back(i);
base *= 3;
}
for(int i = 0;i < 3;i++) {
if(v[i].size()) {
for(int j = v[i].size() - 1;j >= 0;j--) {
cout << v[i][j];
if(j != 0)
cout << " ";
}
} else
cout << "0";
cout << endl;
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 752K, 提交时间: 2020-03-12 12:55:41
#include<stdio.h>
int main()
{
int n,ans[41];
int p[]={0,1,2,1};
long long k;
while(scanf("%d %lld",&n,&k)!=EOF)
{
for(int i=1;i<=n;++i)
ans[i]=0;
for(int i=1;i<=n&&k;++i)
{
long long temp=k/3;
ans[i]=p[(k-temp)&3];
k=temp;
}
for(int i=0;i<3;++i)
{
int cnt=0;
for(int j=n;j>=1;--j)
{
if(ans[j]==i)
{
if(++cnt>1)
printf(" ");
printf("%d",j);
}
}
if(cnt==0)
printf("0");
printf("\n");
}
}
return 0;
}