Задача 5936. Источник: Поляков. Задание КИМ 24
(Е. Джобс) Текстовый файл 24-239.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита X, Y и Z. Найдите максимальную длину подстроки, которая состоит из сочетаний XY, YZ, YZZ, записанных в произвольном порядке. В ответе укажите наибольшую длину подходящей подстроки. Например, в строке ZZXZXZZXYYZYZZYYY самая длинная подходящая подстрока – XYYZYZZ имеет длину 7.
Решение
В данной задаче важен правильный порядок поиска сочетаний символов (сначала нужно искать YZZ и только потом YZ) и правильная манипуляция индексом следующего обрабатываемого символа, когда подстрока прервалась. Символ Y в сочетании XY может являться первым символом новой цепочки, если за ним идет символ Z, и тогда индекс нужно уменьшить на единицу, в противном случае, переходим к следующему символу. Более компактным будет решение с использованием срезов.
Python
s = open("24-239.txt").readline()
k = 0
mx = 0
i = 0
while i < len(s):
if s[i:i + 3] == "YZZ":
k += 3
i += 3
elif s[i:i + 2] == "XY" or s[i:i + 2] == "YZ":
k += 2
i += 2
else:
if i > 0 and s[i - 1:i + 1] == "YZ":
i -= 1
else:
i += 1
k = 0
mx = max(mx, k)
print(mx)
PascalABC
var
i, k, max: Integer;
s: String;
f: TEXT;
begin
Assign(f, '24-239.txt');
Reset(f);
Readln(f, s);
k := 0;
max := 0;
i := 1;
while i <= Length(s) do
begin
if s[i:i + 3] = 'YZZ' then
begin
k := k + 3;
i := i + 3;
end
else if (s[i:i + 2] = 'XY') or (s[i:i + 2] = 'YZ') then
begin
k := k + 2;
i := i + 2;
end
else
begin
if (i > 1) and (s[i - 1:i + 1] = 'YZ') then
i := i - 1
else
i := i + 1;
k := 0;
end;
if k > max then
max := k;
end;
Writeln(max);
end.
Решение с посимвольным сравнением.
Python
s = open("24-239.txt").readline()
k = 0
mx = 0
i = 0
while i < len(s):
if s[i] == "Y" and s[i + 1] == "Z" and s[i + 2] == "Z":
k += 3
i += 3
elif s[i] == "X" and s[i + 1] == "Y" or s[i] == "Y" and s[i + 1] == "Z":
k += 2
i += 2
else:
if i > 0 and s[i - 1] == "Y" and s[i] == "Z":
i -= 1
else:
i += 1
k = 0
mx = max(mx, k)
print(mx)
PascalABC
var
i, k, max: Integer;
s: String;
f: TEXT;
begin
Assign(f, '24-239.txt');
Reset(f);
Readln(f, s);
k := 0;
max := 0;
i := 1;
while i <= Length(s) do
begin
if (s[i] = 'Y') and (s[i + 1] = 'Z') and (s[i + 2] = 'Z') then
begin
k := k + 3;
i := i + 3;
end
else if (s[i] = 'X') and (s[i + 1] = 'Y') or (s[i] = 'Y') and (s[i + 1] = 'Z') then
begin
k := k + 2;
i := i + 2;
end
else
begin
if (i > 1) and (s[i - 1] = 'Y') and (s[i] = 'Z') then
i := i - 1
else
i := i + 1;
k := 0;
end;
if k > max then
max := k;
end;
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("24-239.txt");
string s;
f >> s;
int k = 0, max = 0, i = 0;
while (i < s.length())
{
if (s[i] == 'Y' and s[i + 1] == 'Z' and s[i + 2] == 'Z')
{
k += 3;
i += 3;
}
else if (s[i] == 'X' and s[i + 1] == 'Y' or s[i] == 'Y' and s[i + 1] == 'Z')
{
k += 2;
i += 2;
}
else
{
if (i > 0 and s[i - 1] == 'Y' and s[i] == 'Z')
i--;
else
i++;
k = 0;
}
if (k > max)
max = k;
}
cout << max << endl;
}
Ответ
314