/*
* 1250.cpp
*
* Created on: 2010-10-3
* Author: wyiu
*/
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int f[5][2100];
void init()
{
memset(f, 0, sizeof(f));
f[0][0] = 1;
f[1][0] = 1;
f[2][0] = 1;
f[3][0] = 1;
n--;
}
int fib()
{
if(n < 4) return 1;
int i, j, r, t, m;
for(i=4, m=1; i<=n; i++)
{
for(j=0, r=0; j<m; j++)
{
t = f[(i-1)%5][j]+f[(i-2)%5][j]+f[(i-3)%5][j]+f[(i-4)%5][j] + r;
f[i%5][j] = t % 10;
r = t / 10;
}
if(r > 0)
{
f[i%5][j] = r;
m++;
}
}
return m;
}
void display(int m)
{
int j;
for(j=m-1; j>=0; j--)
{
printf("%d", f[n%5][j]);
}
printf("\n");
fflush(stdout);
}
int main()
{
while(scanf("%d", &n) != EOF)
{
init();
int m = fib();
display(m);
}
return 0;
}
posted on 2010-10-03 17:40
wyiu 閱讀(491)
評論(0) 編輯 收藏 引用