#include <iostream>
#include <ctime>

static unsigned long long *arr1;
static unsigned long long *arr2;
static unsigned long long *arr3;

unsigned long long stairs(int n, char step)
{
	if (n > 0)
	{
		if (step == 1)
		{
			if (arr1[n]) return arr1[n];
			return arr1[n] = stairs(n - 2, 2) + stairs(n - 3, 3);
		}
		if (step == 2)
		{
			if (arr2[n]) return arr2[n];
			return arr2[n] = stairs(n - 1, 1) + stairs(n - 3, 3);
		}
		if (step == 3)
		{
			if (arr3[n]) return arr3[n];
			return arr3[n] = stairs(n - 2, 2) + stairs(n - 1, 1);
		}
		return stairs(n - 2, 2) + stairs(n - 1, 1) + stairs(n - 3, 3);
	}
	if (n == 0) return 1;
	return 0;
}

int main()
{
	int n;
	//std::cin >> n;

	for (int i = 1; i < 1000; ++i)
	{
		arr1 = new unsigned long long[i + 1]{ 1 };
		arr2 = new unsigned long long[i + 1]{ 1 };
		arr3 = new unsigned long long[i + 1]{ 1 };

		clock_t begin = clock();
		std::cout << i << " - " << stairs(i, 0) << ' ';
		clock_t end = clock();
		int delta_ms = (end - begin) * 1000 / CLOCKS_PER_SEC;
		std::cout << "  time: "<< delta_ms << " ms\n";

		delete[] arr1;
		delete[] arr2;
		delete[] arr3;
	}
	system("pause");
	return 0;
}