记录编号	141211	评测结果	AAAAAAAAAA
题目名称	[FJOI 2007] 轮状病毒	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-11-30 10:57:11	内存使用	0.33 MiB

#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
inline void getd(int &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 102;

struct BigN{
	#define base 100000000
	#define maxl 1000
	int A[maxl], len;
	BigN(){len = 1, A[0] = 0;}
	BigN &operator = (const BigN &x){
		len = 0;
		while(len < x.len){A[len] = x.A[len]; ++len;}
		return *this;
	}
	BigN &operator = (int k){len = 1;A[0] = k; return *this;}
	BigN &operator += (const BigN &x){
		int i, mor = 0;
		for(i = 0;i < x.len || mor;++i){
			if(i < len)mor += A[i];
			if(i < x.len)mor += x.A[i];
			A[i] = mor % base;
			mor /= base;
		}
		if(i > len)len = i;
		return *this;
	}
}f[2], S[2];

inline void work(int k){
	int i;
	if(!k){printf("0\n");return;}
	f[0] = 1, f[1] = 1, S[1] = 1;
	if(k == 1){printf("1\n");return;}
	for(i = 2;i <= k;++i){
		f[i&1] = 1; f[i&1] += f[(i^1)&1]; f[i&1] += S[(i^1)&1];
		S[i&1] = S[(i^1)&1]; S[i&1] += f[i&1];
	}
	S[k&1] += S[(k^1)&1];
	i = S[k&1].len - 1;
	printf("%d", S[k&1].A[i]);
	while(i)
		printf("%08d", S[k&1].A[--i]);
	putchar('\n');
}
	
int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("bzoj_1002.in", "r", stdin);
	freopen("bzoj_1002.out", "w", stdout);
	#endif
	int k;
	getd(k);
	
	work(k);
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}