Задача о волшебной пружинке

Волшебная пружинка

Ограничение времени

1 секунда

Ограничение памяти

64Mb

Ввод

стандартный ввод или input.txt

Вывод

стандартный вывод или output.txt

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

Так вот представьте, что на вершине длинной лестницы, содержащей К ступенек, расположена волшебная пружинка новейшей модификации, которая начинает спускаться вниз по лестнице, прямиком к ее основанию. Пружинка может переползти или на одну ступеньку вниз, или через одну ступеньку, или даже через 2.

(Пример: пружинка находится на 97-й ступеньке. Получается, что она может переместиться на 96-ую, 95-ую или 94-ую ступеньки)

Узнайте сколькими способами пружинка может спуститься с «небес» на землю.

Формат ввода

Количество ступенек в лестнице – К – целое число.

Формат вывода

Количество способов спуска – целое число.

Пример 1

Ввод Вывод

4 7

Пример2

Ввод Вывод

• 13

Пример 3

Ввод Вывод

1 1

F(1) = 1

F(2) = 2

F(3) = 4

F(4) = 4 + 2 + 1

F(5) = 7 + 4 + 2 = 13

…

F(n) = F(n-1)+F(n-2)+F(n-3)

Рекуррентная формула:

Пишем код программы:

var k:int64;

function f(n:int64):int64;

begin

case n of

1,2: f:=n;

3: f:=4;

else f:=f(n-1)+f(n-2)+f(n-3);

end;

end;

begin

read(k);

write(f(k));

end.