Задача 36: Принцип компании (отборочный тур
на Самарскую областную олимпиаду 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
Решение:
Без лишних слов перейдем к решению задачи.
Для 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). Как
определить последовательность Фибоначчи разобрано в задаче
Домино
Успехов!
Далее
ð
