HDU2511:漢諾塔 X

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;
}