Задача 6837. Источник: Поляков. Задание КИМ 24
(А. Богданов) Передатчик непрерывно повторяющуюся последовательность XYZ, вставляя полезные сообщения, как только они появляются. Повторяющаяся последовательность XYZ может быть прервана на любой букве вставкой полезного сообщения. После передачи полезного сообщения продолжается передача XYZ со следующего (ещё не переданного) символа. Известно, что первый и последний символы полезных сообщений не мешают их обнаружению. Длина фрагмента повторяющейся последовательности XYZ – не менее трёх символов. Переданные данные сохранены в текстовом файле 24-275.txt, который состоит не более чем из 106 символов – заглавных латинских букв и цифр. Найдите максимальную длину полезного сообщения.
Пример: XYZXYZXYUSEFULLMESSAGEZXYZXYZXYAVERYUSEFULLMESSAGEZXYZXYZXYZ. Наибольшую длину (19) имеет полезное сообщение AVERYUSEFULLMESSAGE.
Решение
В переменной xyz будем подсчитывать длину всех последовательностей XYZ и по ней определять ее продолжение. В переменной current_xyz будем подсчитывать длину текущей последовательности XYZ. В переменной k будем подсчитывать длину полезного сообщения. Если длина текущей последовательности не превышает 3, то полезное сообщение продолжает поступать, иначе сравниваем длину текущего полезного сообщение за вычетом добавленных букв последовательности XYZ с текущим найденным максимумом. Обратите внимание, что в данном решении после цикла не проверяется длина последней последовательности на максимум, т.к. файл завершается последовательностью XYZ, но, если в конце файла будет полезное сообщение, такую проверку нужно добавить.
Python
s = open('24-275.txt').readline()
k = 0
xyz = 0
current_xyz = 0
mx = 0
for i in s:
if i == 'X' and xyz % 3 == 0 or i == 'Y' and xyz % 3 == 1 or i == 'Z' and xyz % 3 == 2:
xyz += 1
current_xyz += 1
if current_xyz > 2:
mx = max(mx, k - 2)
k = 0
else:
k += 1
else:
k += 1
if current_xyz < 3:
xyz -= current_xyz
current_xyz = 0
print(mx)
PascalABC
var
k, max, xyz, current_xyz, i: Integer;
s: String;
f: TEXT;
begin
Assign(f, '24-275.txt');
Reset(f);
Readln(f, s);
k := 0;
xyz := 0;
current_xyz := 0;
max := 0;
for i := 1 to s.Length do
begin
if (s[i] = 'X') and (xyz mod 3 = 0) or
(s[i] = 'Y') and (xyz mod 3 = 1) or
(s[i] = 'Z') and (xyz mod 3 = 2) then
begin
xyz := xyz + 1;
current_xyz := current_xyz + 1;
if current_xyz > 2 then
begin
if k - 2 > max then
max := k - 2;
k := 0
end
else
k := k + 1;
end
else
begin
k := k + 1;
if current_xyz < 3 then
xyz := xyz - current_xyz;
current_xyz := 0;
end;
end;
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("24-275.txt");
string s;
f >> s;
int k = 0, xyz = 0, current_xyz = 0, max = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == 'X' && xyz % 3 == 0 ||
s[i] == 'Y' && xyz % 3 == 1 ||
s[i] == 'Z' && xyz % 3 == 2)
{
xyz++;
current_xyz++;
if (current_xyz > 2)
{
if (k - 2 > max)
max = k - 2;
k = 0;
}
else
k++;
}
else
{
k++;
if (current_xyz < 3)
xyz -= current_xyz;
current_xyz = 0;
}
}
cout << max << endl;
}
Ответ
1339