Question

Что не так? Без трёх единиц

Определите количество последовательностей из нулей и единиц длины N (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом.

Входные данные

Дано натуральное число N, не превосходящее 40.

Выходные данные

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 231−1.

Примеры

Ввод

3

Вывод

7

#include

#include

using namespace std;

int main() {

long long n;

cin >> n;

vector > ggbet(n + 1, vector (2));

ggbet[1][1] = 1;

ggbet[1][0] = 1;

ggbet[2][1] = 2;

ggbet[2][0] = 2;

for (int i = 3; i < ggbet.size(); i++) {

ggbet[i][1] = ggbet[i - 1][1] + ggbet[i - 1][0] - 1;

ggbet[i][0] = ggbet[i - 1][1] + ggbet[i - 1][0];

}

cout << ggbet[n][1] + ggbet[n][0];

}