Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1771. Язык Мумба-Юмба
ПредрешениеОлимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 6F) |
| 04/07/2012 | Лето 2012 - 6 (F) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Слова в языке Мумба-Юмба могут состоять только из букв a, b и при этом:
- никогда не содержат двух букв b подряд,
- ни в одном слове никогда не встречается три одинаковых подслова подряд. Например, по этому правилу в язык Мумба-Юмба не могут входить слова aaa (так как три раза подряд содержит подслово a), ababab (так как три раза подряд содержит подслово ab), aabababa (также три раза подряд содержит подслово ab).
Все слова, удовлетворяющие вышеописанным правилам, входят в язык Мумба-Юмба.
Напишите программу, которая подсчитает количество слов длины ровно `K` символов в языке племени Мумба-Юмба.
Вводится одно число `K` (`1\ ≤\ K\ ≤\ 100\ 000`)
Выведите одно число — количество слов в этом языке длины `K`.
Пример ввода 1
1
Пример вывода 1
2
Пример ввода 2
2
Пример вывода 2
3
Пример ввода 3
3
Пример вывода 3
4
Пример ввода 4
5
Пример вывода 4
7
Пояснение
Слова длины 1 — это слова a, b
Слова длины 2 — это слова aa, ab, ba
Слова длины 3 — это слова aab, aba, baa, bab
Слова длины 5 — это слова aabaa, aabab, abaab, ababa, baaba, babaa, babab
Источник: Московская командная олимпиада школьников по программированию, 2009/10 учебный год
