E. Следы

Имя входного файла:	trails.in
Имя выходного файла:	trails.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

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

Петя решил не портить такую красивую картину и кататься аккуратно по следам. Он может съезжать вниз на лыжах, используя два соседних следа, или на снегокате, используя три подряд идущих следа, поскольку у его снегоката три полоза.

Например, если на горке всего четыре следа, то Петя может съехать вниз на снегокате либо, используя следы 1, 2, 3, либо используя следы 2, 3, 4. На лыжах в таком случае он сможет использовать либо следы 1, 2, либо 2, 3, либо 3, 4.

Петя покатался некоторое время, потом окончательно вымотался, сел на снегокат и задумался о том, а сколько разных вариантов спуска с горки у него есть. Помогите ему найти это количество. Два варианта считаются разными, если они используют разные наборы следов. Например варианты 1, 2 и 1, 2, 3 – разные.

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

В первой строке входного файла находится единственное число N – количество следов на горке (1 ≤ N ≤ 1000).

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

Выведите единственное число – количество различных вариантов спуска с горки, которые есть у Пети.

Пример:

trails.in	trails.out
5	7
6	9

В первом примере у Пети есть следующие варианты: (1, 2), (2, 3), (3, 4), (4, 5) для спуска на лыжах и (1, 2, 3), (2, 3, 4), (3, 4, 5) для спуска на снегокате. Всего семь вариантов.

Источник: VII сетевая районная олимпиада Республики Карелия по информатике, XXIV Городская олимпиада школьников по информатике

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