ハノータVIII
5109 ワード
出典:hdu 2184
ハノータVIII
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 260 Accepted Submission(s): 155
Problem Description
1,2,…,nはn個の皿を表す.数字の大皿は大きい.n個の皿は1本目の柱の上に置く.大皿は小皿の上に置くことができない.1本目の柱の上の皿はa[1],a[2],…,a[n].a[1]=n,a[2]=n-1,…,a[n]=1.つまりa[1]は一番下の皿である.n個の皿を3本目の柱に移動する.毎回1個の皿しか移動できない.また、大皿は小皿に置くことができません.m回移動した後の状況を聞いてください.
Input
1行目は整数Tで、T組のデータがあることを示し、以下はT行である
1行あたり2個の整数n(1≦n≦63),m≦2^n−1
Output
移動m回後の状況を出力.各グループは3行出力,i行目の1番目の数はi本目の柱の皿数,次いで皿の番号である.
Sample Input
ハノータVIII
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 260 Accepted Submission(s): 155
Problem Description
1,2,…,nはn個の皿を表す.数字の大皿は大きい.n個の皿は1本目の柱の上に置く.大皿は小皿の上に置くことができない.1本目の柱の上の皿はa[1],a[2],…,a[n].a[1]=n,a[2]=n-1,…,a[n]=1.つまりa[1]は一番下の皿である.n個の皿を3本目の柱に移動する.毎回1個の皿しか移動できない.また、大皿は小皿に置くことができません.m回移動した後の状況を聞いてください.
Input
1行目は整数Tで、T組のデータがあることを示し、以下はT行である
1行あたり2個の整数n(1≦n≦63),m≦2^n−1
Output
移動m回後の状況を出力.各グループは3行出力,i行目の1番目の数はi本目の柱の皿数,次いで皿の番号である.
Sample Input
3 3 2 4 5 39 183251937942
Sample Output
1 3 1 2 1 1 2 4 1 1 3 1 2 13 39 36 33 30 27 24 21 18 15 12 9 4 1 12 38 35 32 29 26 23 20 17 14 11 8 5 14 37 34 31 28 25 22 19 16 13 10 7 6 3 2
Author
Zhousc
Source
ECJTU 2008 Summer Contest
Recommend
lcy | We have carefully selected several similar problems for you: 1002 2182 2180 2177 1078
解析：模拟；
首先预处理一个f[]，f[i]表示将 i 个盘子从A——>C所需要的次数，f[1]=1,f[i]=f[i-1]*2+1。
①考虑 n 号盘子，移动方向A——>C；
②若m==f[n]，则正好 n 个盘子完全从A——>C；
③若m>f[n-1]，则n号盘子移动到了C ，其上的n-1个盘子正处于从B——>C的移动过程中，此时考虑盘号n-1，移动方向B——>C，移动次数m-f[n-1]-1
；
④若m<=f[n-1]，则 n 号盘子依然在A上，其上的n-1个盘子正处于从A——>B的移动过程中，此时考虑盘号n-1，移动方向A——>B，移动次数m；
⑤重复①②③④；
代码：
#include
#define maxn 63
using namespace std;
long long f[maxn+10],a[4][maxn+10];
void redirect()
{
freopen("hdu2184.in","r",stdin);
freopen("hdu2184.out","w",stdout);
}
void init()
{
int i,j,k;
for(f[1]=1,i=2;i<=maxn;i++)f[i]=f[i-1]*2+1;
}
void dfs(int s,int z,int e,long long n,long long m)
{
int i,j,k;
if(n<=0)return;
if(m==f[n])
{
k=a[e][0],a[e][0]+=n;
for(i=n;i>=1;i--)a[e][k+i]=i;
return;
}
if(m>f[n-1])
{
a[e][++a[e][0]]=n;
m=m-f[n-1]-1,n--;
dfs(z,s,e,n,m);
return;
}
a[s][++a[s][0]]=n;
n--;
dfs(s,e,z,n,m);
}
void write_ans()
{
int i,j,k;
for(i=1;i<=3;i++)
{
printf("%d",a[i][0]);
if(a[i][0]<=0){printf("
");continue;}
for(j=1;j<=a[i][0];j++)printf(" %d",a[i][j]);
printf("
");
}
}
void work()
{
init();
int t,i,j,k;
long long n,m;
while(scanf("%d",&t)==1)
for(i=1;i<=t;i++)
{
scanf("%I64d%I64d",&n,&m);
a[1][0]=a[2][0]=a[3][0]=0;
dfs(1,2,3,n,m);
write_ans();
}
}
int main()
{
redirect();
work();
return 0;
}