ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1260. Фотограф-зануда

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Если 2 человека родились с разницей в секунду и один из них — ребёнок, то другой — тоже ребёнок. По индукции получаем, что все люди — дети.
Всем известно, что матмех — это одна большая семья численностью в N человек, возраст которых 1 год, 2 года, 3 года, …, N лет соответственно.
Однажды декан заказал фотографию своей большой «семьи». На фотографии должны присутствовать все студенты матмеха, и для этого они должны расположиться в один ряд. Сперва было решено расположить студентов по старшинству, начиная с самого младшего. Но фотограф сказал, что, возможно, на фото это будет выглядеть неестественно. Тогда декан посоветовал студентам расположиться так:
  1. Слева сидит студент возрастом в 1 год.
  2. Разность возрастов двух соседних студентов не превышает 2 года.
Декан решил, что на фотографии, таким образом, студенты будут все равно выглядеть будто расположенные по старшинству (ведь среди людей с возрастом, к примеру, 25 и 27 лет не так легко определить старшего). Способов такой посадки существует, понятно, несколько. Фотограф, ни в чём не переча декану, заснял все такие способы.

Исходные данные

В единственной строке записано число N, 1 ≤ N ≤ 55.

Результат

Выведите количество фотографий всех студентов матмеха.

Пример

исходные данныерезультат
4
4

Замечания

При N = 4 существуют следующие способы рассадки: (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2).
Автор задачи: Александр Ипатов
Источник задачи: Открытое командное соревнование школьников Свердловской области по программированию, 11 октября 2003 года