Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 48%)

Строку Фибоначчи F(K) для натуральных чисел K определим так:

F(1) = 'A', F(2) = 'B',

F(K) = F(K-1) + F(K-2) при K > 2, где "+" означает конкатенацию строк.

Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 45), во второй строке записана не пустая строка S, состоящая не более, чем из 25 символов A и B.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число - количество вхождений строки S в строку Фибоначчи F(N).

Примеры

INPUT.TXTOUTPUT.TXT
11
A
1
22
ABA
0
38
BBABAB
3
435
BBABAB
1346268

Примечание

Длина строки F(45) равна 1 134 903 170.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Олимпиадные задачи по программированию, 2006
 Тренировка 1
 Тренировка 2
 Тренировка 3
 Тренировка 4
 Тренировка 5
 Тренировка 6
 Тренировка 7
 Тренировка 8
 Тренировка 9
 Тренировка 10
 Тренировка 11
 Тренировка 12
 Тренировка 13
 Тренировка 14
 Тренировка 15
 A. Анти-QuickSort
 B. Строки Фибоначчи
 C. Игра в зачеркивание
 D. Граница многоугольника
 E. Путь спелеолога
 F. Дырявая ткань

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru