ВКОШП 2023 - Дорожка из плиток

Задача E. Дорожка из плиток ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Антон Карабанов	Ограничение времени:	1 сек
Входной файл:	Стандартный вход	Ограничение памяти:	256 Мб
Выходной файл:	Стандартный выход

Условие

Тротуарная плитка должна укладываться качественно, и таким образом,
чтобы, не дай Бог, в стык между плитками не попала дамская шпилька, а то крику будет...

Руководство по укладке тротуарной плитки, 2012 г.

Тимофею необходимо уложить на узкой парковой дорожке размером 6 × n тротуарную плитку. У него есть неограниченное количество плиток двух типов: 2 × 2 и 3 × 3. Сколько существует различных способов заполнения дорожки? Заказчик требует качественной работы, поэтому плитки нельзя ломать, каждая плитка должна плотно прилегать к соседней без наложений, дорожка должна быть заполнена полностью, края плитки не могут выходить за пределы дорожки.

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 150

Пояснение к примеру

В примере дано n = 5. Смотри рисунок.

Примеры тестов

№	Стандартный вход	Стандартный выход
1	`5`	`2`

Разбор

Динамическое программирование.

База: DP[2] = 1, DP[3] = 1, DP[4] = 1.

Формула перехода: DP[i] = DP[i - 2] + DP[i - 3].