Решение задачи "Разнообразная гирлянда" с Codeforces

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


У вас есть гирлянда, состоящая из n ламп. Каждая лампа — красная, зеленая или синяя. Цвет i-й лампы равен si ('R', 'G' и 'B' — цвета ламп в гирлянде).

Вы хотите перекрасить некоторые лампы в этой гирлянде (перекрашивание лампы означает изменение ее изначального цвета на другой) таким образом, чтобы получившаяся гирлянда стала разнообразной.

Гирлянда называется разнообразной, если любые ее две соседние (последовательные) лампы (то есть такие лампы, что расстояние между их позициями равно 1) имеют различные цвета.

Другими словами, если получилась гирлянда t, то для всех i от 1 до n−1 должно выполняться условие ti≠ti+1.

Среди всех способов перекрасить изначальную гирлянду в разнообразную вы должны выбрать тот, в котором количество перекрашенных ламп минимально. Если существует несколько оптимальных решений, выведите любое из них.

Код

#include<bits/stdc++.h>

using namespace std;

main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	int k = 0;
	for(int i = 0; i < n - 1; i++)
	{
		if(s[i] == s[i + 1])
		{
			set<char> v{'R', 'G', 'B'};
			v.erase(s[i]);
			if(i + 2 < n)
				v.erase(s[i + 2]);
			s[i + 1] = *v.begin();
			k++;
		}
	}
	cout << k << "\n" << s;
}

         

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


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

Комментарии

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