Автомобильные пробки
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
Автомобильные пробки случаются везде, даже в нашем небольшом городе. Дороги у нас имеют по две полосы в одном направлении, а автомобили только двух видов: легковые (в пробке занимают квадратное место 1×1 от ширины одной полосы) и грузовые (занимают прямоугольное место 1×2). Автомобилисты очень дисциплинированы: не становятся поперек полосы, не занимают чужую площадь, но и не оставляют свободных мест.
Требуется написать программу, которая определит количество различных автомобильных пробок длины N.
Входные данные
Входной файл INPUT.TXT содержит одно натуральное число N (N ≤ 1000).
Выходные данные
Выходной файл OUTPUT.TXT должен содержать найденное количество автомобильных пробок.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 | 4 |
| 2 | 3 | 9 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
