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.

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



Версия для печати