Подразделы

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

09/04/2025 20:17:13

Ограничения: время – 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, Меньшиков

03/07/2006	Лето 2006 дорешивание ( 8B)
19/07/2006	Лето 2006 - 8 (B)