Решение задачи K-полное слово с Codeforces
Без пояснения   Просмотров: 166
Слово s длины n называется k-полным, если
s — палиндром, то есть si=sn+1−i для всех 1≤i≤n;
s имеет период k, то есть si=sk+i для всех 1≤i≤n−k.
Например, «abaaba» — это 3-полное слово, а «abccba» нет.
Бобу вручили слово s длины n, состоящее только из строчных букв латинского алфавита, и целое число k такое, что n делится на k. Он хочет превратить слово s в любое k-полное слово.
Для этого Боб может выбирать некоторую позицию i (1≤i≤n) и заменять букву на позиции i на любую другую строчную букву латинского алфавита.
Поэтому теперь Боба интересует минимальное количество позиций, буквы на которых ему необходимо заменить, чтобы превратить s в любое k-полное слово.
Обратите внимание, что Боб может сделать ноль изменений, если слово s уже k-полное.
Требуется ответить на t независимых наборов входных данных.
s — палиндром, то есть si=sn+1−i для всех 1≤i≤n;
s имеет период k, то есть si=sk+i для всех 1≤i≤n−k.
Например, «abaaba» — это 3-полное слово, а «abccba» нет.
Бобу вручили слово s длины n, состоящее только из строчных букв латинского алфавита, и целое число k такое, что n делится на k. Он хочет превратить слово s в любое k-полное слово.
Для этого Боб может выбирать некоторую позицию i (1≤i≤n) и заменять букву на позиции i на любую другую строчную букву латинского алфавита.
Поэтому теперь Боба интересует минимальное количество позиций, буквы на которых ему необходимо заменить, чтобы превратить s в любое k-полное слово.
Обратите внимание, что Боб может сделать ноль изменений, если слово s уже k-полное.
Требуется ответить на t независимых наборов входных данных.