#include <iostream>
#include <vector>
using namespace std;
void Input(int &a, int &n)
{
	cout << "a = ";
	cin >> a;
	cout << "n = ";
	cin >> n;
}

void Cau2a()
{
	const int a = 2;
	cout << "a) Voi a = 2" << endl;
	int f1, f2, f3, f4;
	f1 = a;
	f2 = 18 * a * a + 10;
	f3 = 18* f2 + 10 * f1;
	f4 = 18 * f3 + 10 * f2;
	cout << "F3 = " << f3 << endl;
	cout << "F4 = " << f4 << endl;
}

long long Cau2b(int a, int n)
{
	if (n == 1)
		return a;
	if (n == 2)
		return (long long)18 * a * a + 10;
	else
		return 18 * Cau2b(a, n - 1) + 10 * Cau2b(a, n - 2);
}

long long Cau2c(int a, int n)
{
	long long f1 = a;
	long long f2 = (long long)18 * a * a + 10;
	int temp = 3;
	long long temp1;
	while (temp <= n)
	{
		temp1 = f1;
		f1 = f2;
		f2 = 18 * f2 + 10 * temp1;
		temp++;
	}
	return f2;
}

long long Cau2c_Cach2(int a, int n)
{
	long long F[100000];
	F[1] = a;
	F[2] = (long long)18 * a * a + 10;
	int temp = 3;
	while (temp <= n)
	{
		F[temp] = 18 * F[temp - 1] + 10 * F[temp - 2];
		temp++;
	}
	return F[n];
}


void Caud()
{
	/*Phương pháp không dùng đệ qui(câu c) hiệu quả hơn phương phương pháp dùng đệ qui(câu b)
	bởi vì theo độ phức tạp thuật toán thì câu c có độ phức tạp là O(n) còn câu b là O(2 ^ n);*/
}



int main()
{
	int a, n;
	Cau2a();
	Input(a, n);
	cout << "b) Cau b: ";
	cout << Cau2b(a, n) << endl;
	cout << "c) Cau c: ";
	cout << Cau2c(a, n) << endl;
	cout << "c) Cau c(Cach 2): ";
	cout << Cau2c_Cach2(a, n) << endl;
}