Подразделы

Другие разделы

Дата и время

20/12/2024 14:32:08

Авторизация

Динамическое программирование

And Then There Was One Broken Sword: потерянный файл Decoding Morse Sequences SMS Бросание кубика Витрина Возрастающая подпоследовательность Гангстеры Головоломка умножения Зоопарк Копилка Кубический метр Маршрут Палиндром Разложение на простые слагаемые Скобки (3) Скобки (4) Сообщение Строки Фибоначчи

Строки Фибоначчи

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Пример ввода 2

2
ABA

Пример вывода 2

Пример ввода 3

8
BBABAB

Пример вывода 3

Пример ввода 4

35
BBABAB

Пример вывода 4

Источник: ACM SEERC, 1999, Меньшиков