Переполненные впечатлениями после фильма, вы вышли из кинотеатра. Как написать программу?

Question

1.92K просмотров25.10.2023Информатика

0

Tridi 13.32K 25.10.2023 0 комментариев

Переполненные впечатлениями после фильма, вы вышли из кинотеатра. «Побег из матрицы» оставил очень много вопросов без ответа.

В самом конце фильма была показана битовая строка S, состоящая из символов, каждый из которых был равен 0 или 1. Играла напряжённая музыка, и Мебиусу предстояло принять судьбоносное решение. Он должен был выбрать два индекса l и r, после чего инвертировать биты на подотрезке Sl, Sl+1…, Sr. Иными словами, на выбранном подотрезке Мебиус должен был заменить каждый символ, равный 0, на 1 и наоборот.

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

И вот, в самый интересный момент фильм закончился, а зрители так и не узнали, какой выбор сделал Мёбиус. Не желая дожидаться следующей части фильма, вы захотели сами разгадать тайну. Для этого вы решили написать программу, которая по заданной строке S, состоящей из n символов, найдёт такие индексы l и г, что после инвертирования битов на подотрезке Sl, Sl+1,…, Sr, строка S будет состоять из одинаковых символов.

Arnfinn изменил статус на опубликованный 25.10.2023

1 Ответ

Answer 1 · 2023-10-25T08:05:25+00:00

Ответ на задачу решаем с помощью С++ и Python

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:

1. import math
4. n = int(input())
5. s = input()
6. l = -1
7. r = -1
8. for i in range(len(s)):
9. if s[i] != s[0]:
10. l = i
11. break
12. if l == -1:
13. print(«1», n)
14. exit(0)
15. for i in range(n — 1, -1, -1):
16. if s[i] != s[-1]:
17. r = i
18. break
19. if r < l:
20. print(«1», l)
21. exit(0)
22. for i in range(l, r + 1):
23. if s[i] != s[l]:
24. print(«-1»)
25. exit(0)
26. print(l + 1, r + 1)
27. exit(0)