Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
21. Строки Фибоначчи
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание ( 8B) |
| 19/07/2006 | Лето 2006 - 8 (B) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Строку Фибоначчи `F(K)` для натуральных чисел `K` определим так: `F(1)` = 'A', `F(2)` = 'B', `F(K)\ =\ F(K\ -\ 1)\ +\ F(K\ -\ 2)` при `K\ >\ 2`, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки `S`, состоящей из символов A и B, в строку Фибоначчи `F(N)`.
Ввод
В первой строке содержится число `N\ (1\ ≤\ N\ ≤\ 45)`, во второй – строка `S` длиной от 1 до 25 символов.
Вывод
Выводится одно число – количество вхождений строки `S` в строку Фибоначчи `F(N)`.
Примечание: длина `F(45)` равна 1 134 903 170.
Пример ввода 1
1 A
Пример вывода 1
1
Пример ввода 2
2 ABA
Пример вывода 2
0
Пример ввода 3
8 BBABAB
Пример вывода 3
3
Пример ввода 4
35 BBABAB
Пример вывода 4
1346268
