Напомним, что палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, палиндромами являются строки «abba» и «madam».
Для произвольной строки s введем операцию деления пополам, обозначаемую half(s). Значение half(s) определяется следующими правилами:
Если s не является палиндромом, то значение half(s) не определено;
Если s имеет длину 1, то значение half(s) также не определено;
Если s является палиндромом четной длины 2m, то half(s) — это строка, состоящая из первых m символов строки s;
Если s является палиндромом нечетной длины 2m + 1, большей 1, то half(s) — это строка, состоящая из первых m + 1 символов строки s.
Например, значения half(inforamatics) и half(i) не определены, half(аbbа) = ab, half(madam) = mad. Палиндромностью строки s будем называть максимальное число раз, которое можно применить к строке s операцию деления пополам, чтобы результат был определен.
Например, палиндромность строк «informatics» и «i» равна 0, так как к ним нельзя применить операцию деления пополам даже один раз. Палиндромность строк «abba» и «madam» равна 1, а палиндромноств строки «totottotot» равна 3, посколвку операция деления пополам применима к ней три раза:
«totottotot» —> «totot» —> «tot» —> «to».
Задана некоторая строка s. Необходимо изменить в ней минимальное число символов так, чтобы ее палиндромность стала равной k.