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

Input file name:	stdin
Output file name:	stdout
Time limit:	2 s
Memory limit:	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

Source: Petrozavodsk state university championship. October 2014.

Discuss       Submit a solution