JOJ-2033-Towers of Hanoi

Tomorrow is Kate's birthday, Kate is a lovely girl aged 20. This Contest is held for her birthday and I want everyone will be happy today. My name is sea .I'm not so good at English and Programming. But when I know that it is possible to have a personal contest on JOJ. I want to have a try. Just for her.

Kate : Wish you beauty and healthy forever

happy birthday!

Do you know the game "Towers of Hanoi"? It is a very famous game. But people stopped moving discs from peg to peg after they know the number of steps needed to complete the entire task ! Kate loves the game. She want to know how many times she has to move the disks at least to complete the game?

As we all know , for n disks the game takes 2^n-1 moves at least. But kate want to know the exact numble. Sea want to tell her ,but he is poor at math. So he want to write a program to help her.

Input SpecificationEach line contains a numbe 'N' (0 <= N <= 500). N stand for the number of the disks.

Output SpecificationJust output the least time that kate has to move the disks to complete the game. one per line.

Sample Input7

10

Sample Output127

1023

#include<iostream>

using namespace std;

const int MAX=501;

const int D=1000000000;

const int width=9;

void main()

{

int fact[MAX][17]={0};//151/9==16.777

int len[MAX]={0};

fact[0][0]=1;

len[0]=1;

for(int i=1;i<MAX;++i)

{

int c=0;

int idx=0;

for(idx=0;idx<len[i-1];++idx)

{

int t=fact[i-1][idx]*2+c;

fact[i][idx]=t%D;

c=t/D;

}

if(c>0)

{

len[i]=len[i-1]+1;

fact[i][idx]=c;

}

else

len[i]=len[i-1];

}

int n;

while(cin>>n)

{

if(len[n]==1)

{

cout<<fact[n][len[n]-1]-1<<endl;

continue;

}

cout<<fact[n][len[n]-1];

for(int i=len[n]-2;i>0;--i)

{

cout.width(width);

cout.fill('0');

cout<<fact[n][i];

}

cout.width(width);

cout.fill('0');

cout<<fact[n][0]-1;

cout<<endl;

}

}

说简单点就是用数组计算2的乘幂两点教训：第一，要计算2^0。在这道题里可能很自然考虑到，然而在一道计算N!的程

序可难住了我，郁闷了好久。实际上这个程序就是用计算N!的程序改。第二，不要以为加法比乘法快。开始我是用加法，

用时0.01秒，而用乘法是0.00秒，做移位运算毕竟要比加法快多了。