Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.

В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.

Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.

Несколько школьников решили отпраздновать Новый Год вместе. Для празднования они закупили гору продуктов, и в том числе батон колбасы. Количество еды было настолько велико, что об этом батоне вспомнили только через два с лишним часа после боя курантов. И, конечно, в честь столь знаменательного момента времени школьники решили как можно быстрее съесть этот батон. Но на этом пути их поджидала одна трудность: батон надо разрезать на N (по числу школьников) равных частей, причём как можно быстрее, чтобы не упустить момент. Для этой цели нашёлся очень длинный и острый нож, который смог бы при необходимости разрезать даже N батонов колбасы за один раз. Кроме того, нашлась линейка, с помощью которой можно отмерять любую наперёд заданную часть батона, выбирая место будущего разреза с достаточной точностью. Батон колбасы оказался настолько тонким и длинным, что резать его имело смысл только перпендикулярно его оси.

Конечно, школьники быстро сообразили, что для ускорения процесса можно резать несколько кусков батона одновременно. Батон колбасы оказался прямым и негнущимся, поэтому сэкономить число действий за счёт складывания батона перед разрезанием нельзя. Им осталось определить минимальное количество движений ножом, с помощью которых можно осуществить их намерения. Помогите им в этом. В процессе разрезания школьник может приложить некоторые имеющиеся у него куски батона колбасы друг к другу как он хочет (напомним, что батон очень длинный и тонкий, поэтому имеет смысл прикладывать куски только параллельно друг другу), и одним движением ножа разрезать все куски. Изначально у школьника есть один кусок — сам батон; в конце у него должно быть N одинаковых по длине кусков (каждый длиной в начального батона). Например, разрезать батон на 6 частей (N = 6) школьник может всего за 3 действия ножом:

1. Отмерить длины всего батона и в этом месте разрезать батон.
2. Больший из получившихся кусков разрезать пополам (в итоге получаются три куска равной длины).
3. Приложив их вплотную друг к другу, выровнять концы и разрезать все три куска посередине, в результате чего получится шесть одинаковых кусков.

Чтобы разрезать батон на 5 равных частей (N = 5), также необходимо 3 действия ножом, например:

1. Отмеряем длины батона и разрезаем батон в этом месте.
2. Получившиеся куски складываем вместе так, чтобы середина меньшего куска находилась против трети большего, и разрезаем их так, чтобы меньший разрезать пополам, а больший — в отношении 1: 2. Получаем три куска длиной в всего батона и один — длиной .
3. Больший из имеющихся кусков разрезаем пополам и получаем пять одинаковых кусков.

Фирма, в которой всё ещё работает ваш друг, решила установить в своих маршрутках автоматы по продаже чая и кофе, чтобы во время поездок и, особенно, во время ожидания в пробках, пассажиры могли с толком провести время.

Стоимость стакана чая и кофе в автомате предполагается установить равной пяти рублям. Автоматы будут принимать монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда пассажиру надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100- рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же пассажир бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим пассажирам. Ясно, что, чтобы обеспечить возможность выдачи сдачи всем покупателям, может потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет. Сейчас на маршрутках фирмы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед выездом маршрутки в рейс. Вам дан протокол одного из таких испытаний: известен порядок, в котором пассажиры оплачивали свои покупки различными монетами и купюрами. Определите, какое минимальное количество пятирублёвых монет должно было изначально находиться в автомате, чтобы всем пассажирам хватило сдачи.

Одно из известных развлечений со словами — составление палиндромов. Палиндромом называется предложение, которое, после удаления из него всех пробелов и знаков препинания, читается одинаково справа налево и слева направо. Создатели одного известного текстового редактора пишут новую версию модуля для проверки орфографии. Они хотят реализовать возможность вывода подсказки для пользователя на тот случай, если он допустил опечатку при наборе какого-нибудь палиндрома. Конечно же, они решили обратиться именно к вам.

Более точно, по заданной строке нужно определить, может ли она быть результатом замены, удаления или добавления одного символа в некотором палиндроме. При этом строчные и прописные латинские буквы не различаются, а все остальные символы должны игнорироваться.