Решение задачи Красивая гирлянда с Codeforces

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


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

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

Гирлянда называется красивой, если две любые лампы одинакового цвета находятся на расстоянии, делящемся на три. То есть если получилась гирлянда t, тогда для всех i,j таких, что ti=tj, должно выполняться |i−j| mod 3=0. Значение |x| означает абсолютную величину x, операция x mod y означает остаток от деления x на y.

Например, следующие гирлянды являются красивыми: «RGBRGBRG», «GB», «R», «GRBGRBG», «BRGBRGB». Следующие гирлянды не являются красивыми: «RR», «RGBG».

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

Код

#include <bits/stdc++.h>
using namespace std;

string s,t[6]={"RGB","RBG","GRB","GBR","BRG","BGR"};
int main(){
    int n,a,b,r,i,j;
	cin >> n >> s;
	for(a = n,j = 0; j < 6; j++){
		for(r = i = 0; i < n; i++)
            r += s[i] != t[j][i % 3];
		if(r < a)
            a = r, b = j;
	}
	cout << a << endl;
	for(i = 0; i < n; i++)
        cout << t[b][i % 3];
}

         

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



Комментарии

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