0382. Популяция слонов

Имя входного файла:	stdin
Имя выходного файла:	stdout
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Академик Григорий изучает изменение численности популяции слонов с течением времени. Он заметил следующую интересную закономерность. Популяция слонов в n-ом году выражается функцией f(n) = f(f(n - 1)) + f(n - f(n - 1)), причем f(1) = 1, f(2) = 2.

Григорий просит вас посчитать количество слонов в популяции в году с заданным номером N.

Формат входного файла

В единственной строке дано число N – интересующий Григория год (1 ≤ N ≤ 50).

Формат выходного файла

В единственную строку выведите численность популяции слонов в N-ом году.

Пример:

стандартный поток ввода	стандартный поток вывода
1	1
2	2

Источник: Чемпионат ПетрГУ по программированию. Октябрь 2014.

Обсудить       Отправить решение