e.cpp

The 5th Annual Shantou Univ.Collegiage Programming Contest

#include <cstdio>
#include <iostream>

using namespace std;

void add(int a[], int b[], int c[])
{
	int t=0;
	int i=1;
	while(i<=a[0]&&i<=b[0])
	{
		t+=a[i]+b[i];
		c[i]=t%10;
		t/=10;
		i++;
	}
	
	if (i<=a[0])
	{
		while(i<=a[0])
		{
			t+=a[i];
			c[i]=t%10;
			t/=10;
			i++;
		}
	}
	else if(i<=b[0])
	{
		while(i<=b[0])
		{
			t+=b[i];
			c[i]=t%10;
			t/=10;
			i++;
		}
	}
	if (t)
	{
		c[i]=t;
		c[0]=i;
	}
	else c[0]=i-1;
}

int main()
{
	int T, N;
	int x[201][200];
	x[0][0]=x[0][1]=x[1][0]=x[1][1]=x[2][0]=x[2][1]=1;
	for (int i=3; i<=200; i++)
		add(x[i-1], x[i-3], x[i]);
	cin >> T;
	while(T--)
	{
		cin >> N;
		for (int i=x[N][0]; i>=1; i--)
			cout << x[N][i];
		cout << endl;
	}
	return 0;
}