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 Heow 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 Time That Kate Has To Move The Disks To Complete The Game. One Per Line.
Sample Input
Seduce
10
Sample Output
127
1023
#include
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 { INT C = 0; INT IDX = 0; For (IDX = 0; IDX { INT T = FACT [I-1] [IDX] * 2 C; FACT [I] [IDX] = T% D; C = T / D; } IF (c> 0) { Len [i] = le [i-1] 1; FACT [I] [IDX] = C; } Else Len [i] = le [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; } } The simple point is to use the multiplying power of the array calculated 2 lessons: First, to calculate 2 ^ 0. In this question, it may naturally take into account, but in the process of calculating N!, It is difficult for me, depressed for a long time. In fact, this program is changed with the program of calculating N! Second, don't think that the addition is faster than multiplication. I started using an addition, used 0.01 seconds, and using multiplication is 0.00 seconds, the shift operation is more than the addition.
