Решение задачи Префиксы с Codeforces
Без пояснения   Просмотров: 159
У Николая есть строка s четной длины n, состоящая из латинских букв 'a' и 'b'. Позиции букв пронумерованы от 1 до n.
Он хочет изменить свою строку таким образом, чтобы в любом её префиксе четной длины было поровну букв 'a' и 'b'. Для этого Николай может производить следующую операцию любое количество раз (возможно, нулевое): выбрать позицию в своей строке и заменить букву на этой позиции на другую (то есть заменить букву 'a' на букву 'b' или заменить букву 'b' на букву 'a'). Использовать какие-либо другие буквы, кроме 'a' и 'b', Николай не может.
Префиксом строки s длины l (1≤l≤n) называется строка s[1..l].
Например, для строки s=«abba» существует два префикса чётной длины. Первый из них — это s[1…2]=«ab», второй из них — это s[1…4]=«abba». Оба префикса содержат одинаковое количество букв 'a' и 'b'.
Ваша задача — посчитать минимальное количество операций, которое должен сделать Николай со строкой s, чтобы в любом ее префиксе четной длины строки стало поровну букв 'a' и 'b'.
Он хочет изменить свою строку таким образом, чтобы в любом её префиксе четной длины было поровну букв 'a' и 'b'. Для этого Николай может производить следующую операцию любое количество раз (возможно, нулевое): выбрать позицию в своей строке и заменить букву на этой позиции на другую (то есть заменить букву 'a' на букву 'b' или заменить букву 'b' на букву 'a'). Использовать какие-либо другие буквы, кроме 'a' и 'b', Николай не может.
Префиксом строки s длины l (1≤l≤n) называется строка s[1..l].
Например, для строки s=«abba» существует два префикса чётной длины. Первый из них — это s[1…2]=«ab», второй из них — это s[1…4]=«abba». Оба префикса содержат одинаковое количество букв 'a' и 'b'.
Ваша задача — посчитать минимальное количество операций, которое должен сделать Николай со строкой s, чтобы в любом ее префиксе четной длины строки стало поровну букв 'a' и 'b'.