-
Notifications
You must be signed in to change notification settings - Fork 2
/
10198.cpp
executable file
·128 lines (115 loc) · 3.33 KB
/
10198.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <iomanip>
using namespace std ;
/*
#include <fstream>
using std::ofstream ;
ofstream outfile( "10198.swem" ) ;
*/
int main()
{
long long digit18 = 1000000000 ;
digit18 *= digit18 ;
int number_longint[ 1001 ] = { 0 } ;
number_longint[ 1 ] = 1 ;
number_longint[ 2 ] = 1 ;
number_longint[ 3 ] = 1 ;
//Here we use large number.
//For int n, the Counting number of n is from Counting[ n ][ 1 ] to Counting[ n ] [ number_longint[ n ] ]
long long *Counting[ 1001 ] ;
Counting[ 1 ] = new long long [ number_longint[ 1 ] + 1 ] ;
Counting[ 1 ][ 1 ] = 2 ;
Counting[ 2 ] = new long long [ number_longint[ 2 ] + 1 ] ;
Counting[ 2 ][ 1 ] = 5 ;
Counting[ 3 ] = new long long [ number_longint[ 3 ] + 1 ] ;
Counting[ 3 ][ 1 ] = 13 ;
for( int i = 4 ; i <= 1000 ; i++ )
{
//Calculate the long long int numbers we need.
if( Counting[ i - 1 ][ number_longint[ i - 1 ] ] >= digit18 / 4 )
{
number_longint[ i ] = number_longint[ i - 1 ] + 1 ;
}
else
{
number_longint[ i ] = number_longint[ i - 1 ] ;
}
//Allocate the space of Counting[ i ]
Counting[ i ] = new long long [ number_longint[ i ] + 1 ] ;
Counting[ i ][ 0 ] = 0 ;
for( int j = 1 ; j <= number_longint[ i - 3 ] ; j++ )
{
//Check if there is carry.
if( Counting[ i ][ j - 1 ] >= digit18 )
{
Counting[ i ][ j ] = Counting[ i ][ j - 1 ] / digit18 ;
Counting[ i ][ j - 1 ] = Counting[ i ][ j - 1 ] % digit18 ;
}
else
{
Counting[ i ][ j ] = 0 ;
}
// Use the recursion formula to calculate Counting numbers.
Counting[ i ][ j ] += 2 * Counting[ i - 1 ][ j ] + Counting[ i - 2 ][ j ] + Counting[ i - 3 ][ j ] ;
}
for( int j = number_longint[ i - 3 ] + 1 ; j <= number_longint[ i - 2 ] ; j++ )
{
//Check if there is carry.
if( Counting[ i ][ j - 1 ] >= digit18 )
{
Counting[ i ][ j ] = Counting[ i ][ j - 1 ] / digit18 ;
Counting[ i ][ j - 1 ] = Counting[ i ][ j - 1 ] % digit18 ;
}
else
{
Counting[ i ][ j ] = 0 ;
}
// Use the recursion formula to calculate Counting numbers.
Counting[ i ][ j ] += 2 * Counting[ i - 1 ][ j ] + Counting[ i - 2 ][ j ] ;
}
for( int j = number_longint[ i - 2 ] + 1 ; j <= number_longint[ i - 1 ] ; j++ )
{
//Check if there is carry.
if( Counting[ i ][ j - 1 ] >= digit18 )
{
Counting[ i ][ j ] = Counting[ i ][ j - 1 ] / digit18 ;
Counting[ i ][ j - 1 ] = Counting[ i ][ j - 1 ] % digit18 ;
}
else
{
Counting[ i ][ j ] = 0 ;
}
// Use the recursion formula to calculate Counting numbers.
Counting[ i ][ j ] += 2 * Counting[ i - 1 ][ j ] ;
}
for( int j = number_longint[ i - 1 ] + 1 ; j <= number_longint[ i ] ; j++ )
{
//Check if there is carry.
if( Counting[ i ][ j - 1 ] >= digit18 )
{
Counting[ i ][ j ] = Counting[ i ][ j - 1 ] / digit18 ;
Counting[ i ][ j - 1 ] = Counting[ i ][ j - 1 ] % digit18 ;
}
else
{
Counting[ i ][ j ] = 0 ;
}
}
}
int input ;
while( cin >> input )
{
int i = number_longint[ input ] ;
while( Counting[ input ][ i ] == 0 )
{
i-- ;
}
cout << Counting[ input ][ i ] ;
for( i = i - 1 ; i >= 1 ; i-- )
{
cout << setw( 18 ) << setfill('0') << Counting[ input ][ i ] ;
}
cout << endl ;
}
return 0 ;
}