Переполненные впечатлениями после фильма, вы вышли из кинотеатра. «Побег из матрицы» оставил очень много вопросов без ответа.
В самом конце фильма была показана битовая строка S, состоящая из символов, каждый из которых был равен 0 или 1. Играла напряжённая музыка, и Мебиусу предстояло принять судьбоносное решение. Он должен был выбрать два индекса l и r, после чего инвертировать биты на подотрезке Sl, Sl+1…, Sr. Иными словами, на выбранном подотрезке Мебиус должен был заменить каждый символ, равный 0, на 1 и наоборот.
Судьба Мёбиуса зависела от того, сможет ли он найти такие индексы, чтобы после инвертирования битов на соответствующем подотрезке битовая строка S состояла бы из одинаковых символов.
И вот, в самый интересный момент фильм закончился, а зрители так и не узнали, какой выбор сделал Мёбиус. Не желая дожидаться следующей части фильма, вы захотели сами разгадать тайну. Для этого вы решили написать программу, которая по заданной строке S, состоящей из n символов, найдёт такие индексы l и г, что после инвертирования битов на подотрезке Sl, Sl+1,…, Sr, строка S будет состоять из одинаковых символов.
Ответ
C++:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
string s; cin >> s;
int l = -1, r = -1;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != s[0]) {
l = i;
break;
}
}
if (l == -1) {
cout << «1 » << n << «\n»; return 0; } for (int i = n — 1; i > -1; —i) {
if (s[i] != s.back()) {
r = i;
break;
}
}
if (r < l) {
cout << «1 » << l << «\n»;
return 0;
}
for (int i = l; i <= r; ++i) {
if (s[i] != s[l]) {
cout << «-1\n»;
return 0;
}
}
cout << l + 1 << » » << r + 1 << «\n»;
return 0;
}
Python:
import math
n = int(input())
s = input()
l = -1
r = -1
for i in range(len(s)):
if s[i] != s[0]:
l = i
break
if l == -1:
print(«1», n)
exit(0)
for i in range(n — 1, -1, -1):
if s[i] != s[-1]:
r = i
break
if r < l:
print(«1», l)
exit(0)
for i in range(l, r + 1):
if s[i] != s[l]:
print(«-1»)
exit(0)
print(l + 1, r + 1)
exit(0)