1
2
3
4
5
6
7
8
9
10
11
12
13
14 #include
15 using namespace std;
16 const int N=1100;
17 const int M=500;
18 struct Big
19 {
20 int s[M];
21 int len;
22 };
23 Big f[N];
24 void Add(Big &a,Big &b,Big &c,Big &d)
25 {
26 d.len=a.len;
27 int t=0;
28 for(int i=0;i<d.len;i++)
29 {
30 t+=a.s[i]+b.s[i]+c.s[i];
31 d.s[i]=t%10;
32 t=t/10;
33 }
34 if(t>0)
35 {
36 d.s[d.len]=t;
37 d.len++;
38 }
39 }
40 void OutPut(Big &a)
41 {
42 for(int i=a.len-1;i>=0;i--)
43 printf("%d",a.s[i]);
44 printf("\n");
45 }
46 void Init()
47 {
48 f[0].s[0]=1;f[0].len=1;
49 f[1].s[0]=1;f[1].len=1;
50 f[2].s[0]=2;f[2].len=1;
51 f[3].s[0]=4;f[3].len=1;
52 for(int i=4;i<N;i++)
53 {
54 Add(f[i-1],f[i-2],f[i-4],f[i]);
55 }
56
57 }
58
59 int main()
60 {
61 int n;
62 Init();
63 while(scanf("%d",&n))
64 {
65 OutPut(f[n]);
66 }
67 }