Решение задачи "Префиксы" с Codeforces

Без пояснения   Просмотров: 11


У Николая есть строка 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'.

Код

#include <bits/stdc++.h>
using namespace std;
int a,b,ans;
string s;
main () {
	cin >>a >>s;
	for (int i = 0; i < a; i+=2)
	{
		if (s[i] == s[i + 1]) {
			if (s[i] == 'a') s[i] = 'b';
			else
			s[i] = 'a';
			ans++;
		}
	}
	cout <<ans <<endl <<s;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться