Задача 5878. Источник: Поляков. Задание КИМ 24
(Е. Джобс) Текстовый файл 24-237.txt состоит не более чем из 106 символов и содержит только символы A, B, C, D, E, F. Найдите максимальную длину подстроки, которая состоит из подряд идущих троек одинаковых символов. Например, в строке BBCDDDEEEFGGGEEEDDDDK такая подстрока GGGEEEDDD. Следовательно, ответ в этом случае – 9.
Решение
Не смотря на всю простоту формулировки, решение данной задачи совсем не так просто. Если ваше решение выдает правильный ответ для предоставленного файла - это совершенно не означает, что оно даст правильный ответ на других исходных данных. В указанном файле решением является подстрока CCCAAAAAADDDCCC, справа и слева от которой находится по одному символу C, что является одним из вариантов средней сложности. Обязательно проверяйте решение для различных ситуаций.
Анализируем последовательность тройками. Если подряд идут три одинаковых символа, добавляем их к текущей последовательности. При прерывании последовательности важно правильно инициализировать счетчик новой подстроки или откатить индекс первого обрабатываемого символа новой подстроки. Например, в строке AAADDDDDDDDCCCEEE первые шесть символов D являются окончанием подстроки AAADDDDDD, а последние шесть символов D - началом подстроки DDDDDDCCCEEE.
В первом варианте решения будем сохранять символ последней тройки last и длину подстроки полных троек, содержащей данный символ kl. При прерывании подстроки, идем по строке дальше до первого символа, отличного от last, а длину новой последовательности инициализируем kl.
Python
s = open("24-237.txt").readline()
k = 0
mx = 0
i = 0
last = " "
kl = 0
while i < len(s) - 2:
if s[i] == s[i + 1] and s[i] == s[i + 2]:
k += 3
mx = max(mx, k)
if s[i] == last:
kl += 3
else:
last = s[i]
kl = 3
i += 3
else:
if s[i] != last:
k = 0;
i += 1
else:
k = kl
while i < len(s) and s[i] == last:
i += 1
last = " "
kl = 0
print(mx)
PascalABC
var
i, k, max, kl: Integer;
s: String;
last: Char;
f: TEXT;
begin
Assign(f, '24-237.txt');
Reset(f);
Readln(f, s);
k := 0;
max := 0;
i := 1;
last := ' ';
kl := 0;
while i <= s.Length - 2 do
begin
if (s[i] = s[i + 1]) and (s[i] = s[i + 2]) then
begin
k := k + 3;
if max < k then
max := k;
if s[i] = last then
kl := kl + 3
else
begin
last := s[i];
kl := 3;
end;
i := i + 3;
end
else
begin
if s[i] <> last then
begin
k := 0;
i := i + 1;
end
else
begin
k := kl;
while (i <= s.Length) and (s[i] = last) do
i := i + 1;
end;
last := ' ';
kl := 0;
end;
end;
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("24-237.txt");
string s;
f >> s;
int k = 0, max = 0, i = 0, kl = 0;
char last = ' ';
while (i < s.length() - 2)
{
if (s[i] == s[i + 1] && s[i] == s[i + 2])
{
k += 3;
if (max < k)
max = k;
if (s[i] == last)
kl += 3;
else
{
last = s[i];
kl = 3;
}
i += 3;
}
else
{
if (s[i] != last)
{
k = 0;
i++;
}
else
{
k = kl;
while (i < s.length() and s[i] == last)
i++;
}
last = ' ';
kl = 0;
}
}
cout << max << endl;
}
В другом решении сохраняем только last и, при прерывании подстроки, откатываем индекс текущего обрабатываемого символа i до первого символа полной тройки с конца с символом last.
Python
s = open("24-237.txt").readline()
k = 0
mx = 0
i = 0
last = " "
while i < len(s) - 2:
if s[i] == s[i + 1] and s[i] == s[i + 2]:
k += 3
mx = max(mx, k)
last = s[i]
i += 3
else:
if s[i] == last:
if i < len(s) - 1 and i > 0 and s[i + 1] == last and s[i - 1] == last:
i -= 1
elif i > 1 and s[i - 1] == last and s[i - 2] == last:
i -= 2
while i > 2 and s[i - 1] == last and s[i - 2] == last and s[i - 3] == last:
i -= 3
else:
i += 1
k = 0
last = " "
print(mx)
PascalABC
var
i, k, max: Integer;
s: String;
last: Char;
f: TEXT;
begin
Assign(f, '24-237.txt');
Reset(f);
Readln(f, s);
k := 0;
max := 0;
last := ' ';
i := 1;
while i <= s.Length - 2 do
begin
if (s[i] = s[i + 1]) and (s[i] = s[i + 2]) then
begin
k := k + 3;
if max < k then
max := k;
last := s[i];
i := i + 3;
end
else
begin
if s[i] = last then
begin
if (i < s.Length) and (i > 1) and (s[i + 1] = last) and (s[i - 1] = last) then
i := i - 1
else if (i > 2) and (s[i - 1] = last) and (s[i - 2] = last) then
i := i - 2;
while (i > 3) and (s[i - 1] = last) and (s[i - 2] = last) and (s[i - 3] = last) do
i -= 3;
end
else
i := i + 1;
k := 0;
last := ' ';
end;
end;
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("24-237.txt");
string s;
f >> s;
int k = 0, max = 0, i = 0;
char last = ' ';
while (i < s.length() - 2)
{
if (s[i] == s[i + 1] && s[i] == s[i + 2])
{
k += 3;
if (max < k)
max = k;
last = s[i];
i += 3;
}
else
{
if (s[i] == last)
{
if (i > 0 && s[i] == s[i + 1] && s[i] == s[i - 1])
i--;
else if (i > 1 && s[i] == s[i - 1] && s[i] == s[i - 2])
i -= 2;
while (i > 2 and s[i - 1] == last and s[i - 2] == last and s[i - 3] == last)
i -= 3;
}
else
i++;
k = 0;
last = ' ';
}
}
cout << max << endl;
}
Ответ
15