Задача g6_1043: Принцип компании (отборочный тур на Самарскую областную олимпиаду 2000 г.)

Компания SPAM занимается рассылкой рекламных газет и буклетов в разные города. По договоренности с почтой, каждая посылка должна содержать строго определенное количество (N, где 1 > N > 100) экземпляров рекламных изданий в сумме. Но есть еще проблема и принцип компании:
1) Два буклета не могут соприкасаться, из-за некачественного полиграфического покрытия они склеиваются и портятся. Газеты выполняют еще и роль прокладки между ними.
2) Каждая посылка должна быть уникальная, то есть отличаться от других порядком укладки или количеством различных типов изданий (буклет/газета). Это дополнительный рекламный ход компании, который состоит в том, что каждый клиент должен получать индивидуальную укладку или содержание посылки.

Необходимо заранее определить максимальное количество вариантов правильной комплектации посылки в зависимости от N.

Входные данные:

В начале файла "SPAM.IN" записано количество экземпляров изданий (некоторое N).

Выходные данные:

В первой строке файла "SPAM.OUT" нужно указать число возможных вариантов комплектации.

Пример 1.

Файл "SPAM.IN"
4
Файл "SPAM.OUT"
8

Пример 2.

Файл "SPAM.IN"
13
Файл "SPAM.OUT"
610

Решение g6_1043:
Без лишних слов перейдем к решению задачи.
Для N = 1 мы имеем ответ 2 (0 или 1). Для N = 2 - ответ 3 (00, 01, 10). Для N = 3 - 5 (000, 001, 010, 100, 101). Исследую эту закономерность, мы придем к тому, что она представляет собой последовательность чисел Фибоначчи. Действительно, в любом случае мы можем приложить к уже имеющейся последовательности газету, т.е. F(x) = F(x - 1). Кроме того, для предыдущей мы также могли приложить газету (таких комбинаций F(x - 2)) и теперь мы можем смело приложить буклет. Т.е. общее количество F(x) = F(x - 1) + F(x - 2). Как определить последовательность Фибоначчи разобрано в задаче #1025 - Домино
Успехов!