ハノータII(繰返し+数学)

ハノータII
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6234    Accepted Submission(s): 3047
Problem Description
古典的なハノータ問題はしばしば再帰的な古典的な例題として存在する.ハノタ問題の故事を知らない人もいるかもしれない.ハノタはインドの伝説の物語に由来し、神が世界を創造した時に3本のダイヤモンドの柱を作り、1本の柱の上に64枚の黄金の円盤を下から上に積み上げた.神はボロモンに円盤を下から大きさ順に別の柱に置くように命じた.また、小円盤では円盤を拡大することができず、3本の柱の間で1回に1つの円盤しか移動できないことが規定されている.このことが終わると、宇宙は一瞬にして稲妻のように壊滅するという予言がある.ボロモンは今も円盤を一刻も動かさないと信じている人もいる.ええ、もちろんこの伝説は信じられませんが、今ハンノタはおもちゃとしてもっと存在しています.Gardonは誕生日プレゼントとしてハノータのおもちゃを受け取った.
Gardonは面倒を恐れる人(うん、怠け者)で、64個の円盤をすべての皿が3番目の柱に届くまで一つ一つ運ぶのは難しいのは明らかだから、Gardonは小さな弊害を作ることにした.彼はまた同じ柱を探して、この柱を通じてすべての皿を3番目の柱にもっと速く移した.次の質問は、GardonがゲームでN個の皿を使ったとき、3番目の柱に移動するには何回移動する必要がありますか?明らかに、4番目の柱がない場合、問題の解は2^N-1ですが、今この柱の助けがあれば、いくらでしょうか.
 
Input
複数組のデータを含み、各データの1行は、皿の数N(1<=N<=64)である.
 
Output
データのセットごとに、ターゲットに到達するために必要な移動数を1つ出力します.
 
Sample Input

   
   
   
   

    
    
    
    1
3
12
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
5
81
   
   
   
   
   
   
   
   

    
    
    
     
   
   
   
   
   
   
   
   

    
    
    
    
#include<stdio.h>
#include<string.h>
#include<math.h>
#define INF 0x3f3f3f
int a[65]={0,1,3};
int main(){
	int n,i,j;
	for(i=3;i<=64;i++)
	{
		int MIN=INF;
		for(j=1;j<i;j++)
		{
			if(2*a[j]+pow(2,i-j)-1<MIN)
				MIN=2*a[j]+pow(2,i-j)-1;
		}
		a[i]=MIN;
	}
	while(scanf("%d",&n)!=EOF)
	{
		printf("%d
",a[n]);
	}
	return 0;
}
 
 
 
/*__int64 unsigned __int64，      
[-2^63, 2^63) [0,2^64)，
 -9223372036854775808~9223372036854775807 
0~18446744073709551615( 1800 )。*/
#include<stdio.h>
#include<math.h>
int main(){
    int i=0,j=0,n=0;
    unsigned __int64 a[65]={0},min=0;
    a[1]=1,a[2]=3;
    for(i=3;i<=64;i++)
    {
        min=2*a[1]+(unsigned __int64)pow(2,(i-1))-1;
        for(j=2;j<i;j++)
        {
            if(2*a[j]+(unsigned __int64)pow(2,(i-j))-1<min)
                min=2*a[j]+(unsigned __int64)pow(2,(i-j))-1;
        }
        a[i]=min;
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%I64u
",a[n]);
    }
    return 0;
}