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

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


Вам дана строка s, состоящая из n строчных букв латинского алфавита.

Подстрока строки — это некоторый ее непрерывный подотрезок. Например, «acab» — подстрока строки «abacaba» (она начинается в позиции 3 и заканчивается в позиции 6), но «aa» и «d» не являются подстроками этой строки. То есть подстрока строки s с позиции l по позицию r — это строка s[l;r]=slsl+1…sr.

Вам нужно выбрать ровно одну подстроку данной строки и развернуть ее (то есть сделать s[l;r]=srsr−1…sl), чтобы полученная строка оказалась лексикографически меньше исходной. Обратите внимание, что не обязательно минимизировать полученную строку.

Если невозможно таким образом развернуть подстроку, выведите «NO». Иначе выведите «YES» и любую подходящую подстроку.

Строка x лексикографически меньше строки y, если либо x является префиксом y (и при этом x≠y), либо существует такое i (1≤i≤min(|x|,|y|)), что xi

Код

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

int main() {
	int n;
	string a;
	cin>>n>>a;
	for(int i=0;i<a.length()-1;i++){
		if(a[i]>a[i+1]){
			cout<<"YES\n";
			cout<<i+1<<' '<<i+2;
			return 0;
		}
	}
	cout<<"NO";
}

         

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



Комментарии

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