Решение задачи Красивая строка с Codeforces

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


Строка называется красивой, если никакие два последовательных символа строки не равны. Например, строки «ababcb», «a» и «abab» красивые, тогда как «aaaaaa», «abaa» и «bb» нет.

Ahcl хочет построить красивую строку. У него есть строка s, состоящая только из символов 'a', 'b', 'c' и '?'. Ahcl должен поменять каждый символ '?' на один из трех символов 'a', 'b' или 'c', так что получившаяся строка будет красивой. Помогите ему!

Более формально, после замены всех символов '?', условие si≠si+1 должно быть выполнено для всех 1≤i≤|s|−1, где |s| это длина строки s.

Код

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

const int N = 1e5 + 5;
char s[N];

void Solve(){
	scanf("%s", s+1);
	int n = strlen(s+1);
	s[0] = s[n+1] = '?';
	for(int i=1; i<=n; i++){
		if(s[i] == '?'){
			for(char c='a'; c<='c'; c++)
				if(s[i-1] != c && s[i+1] != c)
					s[i] = c;
		}
		if(s[i] == s[i+1]){
			printf("-1\n");
			return;
		}
	}
	
	for(int i=1; i<=n; i++)
		printf("%c", s[i]);
	printf("\n");
}

int main(){
	int t; scanf("%d", &t);
	while(t--) Solve();

	return 0;
}

         

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



Комментарии

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