Problem Description
1,2,...,n表示n個盤子．數字大盤子就大．n個盤子放在第１根柱子上．大盤不能放在小盤上．在第１根柱子上的盤子是a[1],a[2],...,a[n]. a[1]=n,a[2]=n-1,...,a[n]=1.即a[1]是最下面的盤子．把n個盤子移動到第3根柱子．每次只能移動1個盤子，且大盤不能放在小盤上．問第m次移動的是哪一個盤子，從哪根柱子移到哪根柱子.例如：n=3,m=2. 回答是 ：2 1 2，即移動的是2號盤，從第1根柱子移動到第2根柱子 。
Input
第1行是整數T,表示有T組數據，下面有T行,每行2個整數n (1 ≤ n ≤ 63) ,m≤ 2^n-1
Output
輸出第m次移動的盤子號數和柱子的號數．
Sample Input
4
3 2
4 5
39 183251937942
63 3074457345618258570
Sample Output
2 1 2
1 3 1
2 2 3
2 2 3
先把情況列出來自己尋找規律吧
規律就是
如果總盤數與現在移動的盤子的號碼同奇偶性，那麼移動順序是1->3->2->1
否則是1->2->3->1
記住這個移動順序是對於同一個盤而言的
[cpp] view plaincopyprint?#include <stdio.h>
__int64 pow(__int64 n)
{
__int64 s = 1;
int i;
for(i = 1;i<=n;i++)
s*=2;
return s;
}
int main()
{
__int64 n,m,t;
int a[3][2] = {{3,1},{1,2},{2,3}},b[3][2] = {{2,1},{1,3},{3,2}};
int i,test;
scanf("%d",&test);
while(test--)
{
__int64 cnt = 0;
scanf("%I64d%I64d",&n,&m);
__int64 tem = m;
for(i = 1; i<=n; i++)
{
t = m%2;
if(t)
{
printf("%d ",i);
break;
}
else
m/=2;
}
if(tem%2)
cnt = (tem+1)/2;
else
{
m = tem;
__int64 sum = pow(i-1);
m = m-sum;
cnt = m/pow(i)+1;
}
int flag = 0;
if((n%2 && i%2) || (n%2 == 0 && i%2 == 0))
{
flag = 1;
}
cnt = cnt%3;
if(flag)
{
printf("%d %d\n",b[cnt][0],b[cnt][1]);
}
else
{
printf("%d %d\n",a[cnt][0],a[cnt][1]);
}
}
return 0;
}
#include <stdio.h>
__int64 pow(__int64 n)
{
__int64 s = 1;
int i;
for(i = 1;i<=n;i++)
s*=2;
return s;
}
int main()
{
__int64 n,m,t;
int a[3][2] = {{3,1},{1,2},{2,3}},b[3][2] = {{2,1},{1,3},{3,2}};
int i,test;
scanf("%d",&test);
while(test--)
{
__int64 cnt = 0;
scanf("%I64d%I64d",&n,&m);
__int64 tem = m;
for(i = 1; i<=n; i++)
{
t = m%2;
if(t)
{
printf("%d ",i);
break;
}
else
m/=2;
}
if(tem%2)
cnt = (tem+1)/2;
else
{
m = tem;
__int64 sum = pow(i-1);
m = m-sum;
cnt = m/pow(i)+1;
}
int flag = 0;
if((n%2 && i%2) || (n%2 == 0 && i%2 == 0))
{
flag = 1;
}
cnt = cnt%3;
if(flag)
{
printf("%d %d\n",b[cnt][0],b[cnt][1]);
}
else
{
printf("%d %d\n",a[cnt][0],a[cnt][1]);
}
}
return 0;
}
