1260 Timus answer/Решение задачи 1260:•

№1260
http://acm.timus.ru/problem.aspx?space=1&num=1260
ЖМИ ДАЛЕЕ>>>

РЕШЕНИЕ:

PASCAL

Var
A: Array[1..55] of LongInt;
N,I: LongInt;
Begin
Readln(N);
a[1]:=1;
a[2]:=1;
a[3]:=2;
For I:=4 to 55 do
a[i]:=a[i-1]+a[i-3]+1;
Writeln(A[N]);
End.

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ

Если 2 человека родились с разницей в секунду и один из них — ребёнок,
то другой — тоже ребёнок. По индукции получаем, что все люди — дети.

Всем известно, что матмех — это одна большая семья численностью в N человек, возраст которых 1 год, 2 года, 3 года, …, N лет соответственно.

Однажды декан заказал фотографию своей большой «семьи». На фотографии должны присутствовать все студенты матмеха, и для этого они должны расположиться в один ряд. Сперва было решено расположить студентов по старшинству, начиная с самого младшего. Но фотограф сказал, что, возможно, на фото это будет выглядеть неестественно. Тогда декан посоветовал студентам расположиться так:

Слева сидит студент возрастом в 1 год.
Разность возрастов двух соседних студентов не превышает 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 года