0009. Филя II

Имя входного файла:	filya2.in
Имя выходного файла:	filya2.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Филя снова проводит свои опасные опыты из предыдущей задачи. Однако теперь у него более компактный прибор, и Филя смог поместить его у k-ого по счету контейнера. Узнайте, какое минимальное количество операций теперь потребуется Филе для получения антиматерии одного вида во всех контейнерах.

Формат входного файла

В первой строке входного файла дана строка, состоящая из заглавных и строчных латинских букв длиной от 1 до 4000 символов. i-ый символ строки означает вид антиматерии в i-ом контейнере. Во второй строке содержится единственное число k √ номер контейнера, к которому применяется операция.

Формат выходного файла

В выходной файлы необходимо вывести единственное число √ ответ на поставленный вопрос.

Пример:

filya2.in	filya2.out
ABBCCA 2	2

Примечание

Филя должен выполнить следующие операции: ABBCCA → ACCCCA → AAAAAA

Источник: Командное школьное первенство Республики Карелия по программированию, май 2008.

Обсудить       Отправить решение