ЕГЭ по информатике · задание 24

Текстовый файл: самая длинная цепочка

В файле — длинная строка из букв и цифр. Нужно найти самую длинную цепочку подряд идущих символов с условием. К каждому варианту — файл; решать нужно программой.

Чтение файла

s = open('file.txt').readline().strip() — вся строка.
Позиции символа: [i for i, c in enumerate(s) if c == 'Y'].

Приёмы

Счётчик текущей цепочки: продолжаем или начинаем заново.
Окна между позициями особого символа: для «ровно K» и «не более K».
Не перебирать все пары (начало, конец) — для миллиона символов это слишком долго.

Типичные ошибки

Забыть начальное значение длины 1.
Не учесть цепочку в самом начале или в самом конце строки.
Считать пересекающиеся вхождения подстроки неправильно.

Разобранные варианты

Вариант 1

ровно 67 букв Y и 2025

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 151 раз и при этом содержится ровно 67 букв Y. В ответе запишите число — количество символов в найденной последовательности.

Файл к варианту: Ege24_v1.txt (200 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Возьмём 67 букв Y подряд (с i-й по (i + 66)-ю) и расширим окно влево до предыдущей буквы Y и вправо до следующей, не включая их. Получится самая длинная цепочка с ровно этими буквами: любая подходящая цепочка лежит внутри одного такого окна.

Условие на 2025. Чем длиннее окно, тем больше в нём вхождений 2025, поэтому достаточно проверить только эти «максимальные» окна: подходит окно, если в нём не меньше 151 вхождений.

Скорость. Позиции букв и начала вхождений 2025 записываем в списки один раз; количество вхождений в окне считаем через bisect — программа работает доли секунды.

Ответ для файла варианта: 3473.

Ответ: 3473

Решение на Python. Положите файл варианта рядом с программой.

from bisect import bisect_left, bisect_right

s = open('Ege24_v1.txt').readline().strip()
ys = [-1] + [i for i, c in enumerate(s) if c == 'Y'] + [len(s)]
occ = [i for i in range(len(s) - 3) if s[i:i + 4] == '2025']    # начала вхождений
M, K = 67, 151
best = 0
for i in range(1, len(ys) - M):
    l, r = ys[i - 1] + 1, ys[i + M] - 1          # ровно M букв внутри [l, r]
    cnt = bisect_right(occ, r - 3) - bisect_left(occ, l)
    if cnt >= K:
        best = max(best, r - l + 1)
print(best)

Вариант 2

без одинаковых соседних

Текстовый файл состоит из символов X, Y, Z. Определите максимальное количество идущих подряд символов, среди которых нет двух одинаковых соседних.

Файл к варианту: Ege24_v2.txt (200 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Идём по строке и держим длину текущей цепочки: если символ отличается от предыдущего, цепочка продолжается (+1), иначе начинается заново с длиной 1. Ответ — наибольшая длина за весь проход.

Ответ для файла варианта: 31.

Ответ: 31

Решение на Python. Положите файл варианта рядом с программой.

s = open('Ege24_v2.txt').readline().strip()
best = cur = 1
for i in range(1, len(s)):
    if s[i] != s[i - 1]:
        cur += 1
    else:
        cur = 1
    best = max(best, cur)
print(best)

Вариант 3

не более 88 букв A

Текстовый файл состоит из заглавных букв латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых буква A встречается не более 88 раз.

Файл к варианту: Ege24_v3.txt (150 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Самая длинная цепочка содержит ровно 88 букв A (или все, если их меньше) и упирается в соседние буквы A с обеих сторон. Запишем позиции букв A в список, добавив «границы» −1 и длину строки, и для каждого набора из 88 соседних букв найдём расстояние между ограничивающими буквами.

Ответ для файла варианта: 2822.

Ответ: 2822

Решение на Python. Положите файл варианта рядом с программой.

s = open('Ege24_v3.txt').readline().strip()
p = [-1] + [i for i, c in enumerate(s) if c == 'A'] + [len(s)]
K = 88
print(max(p[i + K + 1] - p[i] - 1 for i in range(len(p) - K - 1)))

Вариант 4

чередование букв и цифр

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите максимальное количество идущих подряд символов, в которых буквы и цифры чередуются (после буквы идёт цифра, после цифры — буква).

Файл к варианту: Ege24_v4.txt (100 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Как в задаче «без одинаковых соседних», только сравниваем не сами символы, а их тип: c.isdigit(). Если тип сменился — цепочка продолжается.

Ответ для файла варианта: 112.

Ответ: 112

Решение на Python. Положите файл варианта рядом с программой.

s = open('Ege24_v4.txt').readline().strip()
best = cur = 1
for i in range(1, len(s)):
    if s[i].isdigit() != s[i - 1].isdigit():
        cur += 1
    else:
        cur = 1
    best = max(best, cur)
print(best)

Вариант 5

ровно 84 букв Y и 2025

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 173 раз и при этом содержится ровно 84 букв Y. В ответе запишите число — количество символов в найденной последовательности.

Файл к варианту: Ege24_v5.txt (100 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Возьмём 84 букв Y подряд (с i-й по (i + 83)-ю) и расширим окно влево до предыдущей буквы Y и вправо до следующей, не включая их. Получится самая длинная цепочка с ровно этими буквами: любая подходящая цепочка лежит внутри одного такого окна.

Условие на 2025. Чем длиннее окно, тем больше в нём вхождений 2025, поэтому достаточно проверить только эти «максимальные» окна: подходит окно, если в нём не меньше 173 вхождений.

Ответ для файла варианта: 4146.

Ответ: 4146

Решение на Python. Положите файл варианта рядом с программой.

from bisect import bisect_left, bisect_right

s = open('Ege24_v5.txt').readline().strip()
ys = [-1] + [i for i, c in enumerate(s) if c == 'Y'] + [len(s)]
occ = [i for i in range(len(s) - 3) if s[i:i + 4] == '2025']    # начала вхождений
M, K = 84, 173
best = 0
for i in range(1, len(ys) - M):
    l, r = ys[i - 1] + 1, ys[i + M] - 1          # ровно M букв внутри [l, r]
    cnt = bisect_right(occ, r - 3) - bisect_left(occ, l)
    if cnt >= K:
        best = max(best, r - l + 1)
print(best)

Вариант 6

не более 102 букв D

Текстовый файл состоит из заглавных букв латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых буква D встречается не более 102 раз.

Файл к варианту: Ege24_v6.txt (150 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Самая длинная цепочка содержит ровно 102 букв D (или все, если их меньше) и упирается в соседние буквы D с обеих сторон. Запишем позиции букв D в список, добавив «границы» −1 и длину строки, и для каждого набора из 102 соседних букв найдём расстояние между ограничивающими буквами.

Ответ для файла варианта: 3420.

Ответ: 3420

Решение на Python. Положите файл варианта рядом с программой.

s = open('Ege24_v6.txt').readline().strip()
p = [-1] + [i for i, c in enumerate(s) if c == 'D'] + [len(s)]
K = 102
print(max(p[i + K + 1] - p[i] - 1 for i in range(len(p) - K - 1)))

Вариант 7

без одинаковых соседних

Файл к варианту: Ege24_v7.txt (200 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Ответ для файла варианта: 29.

Ответ: 29

Решение на Python. Положите файл варианта рядом с программой.

s = open('Ege24_v7.txt').readline().strip()
best = cur = 1
for i in range(1, len(s)):
    if s[i] != s[i - 1]:
        cur += 1
    else:
        cur = 1
    best = max(best, cur)
print(best)

Вариант 8

ровно 77 букв X и 2025

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 176 раз и при этом содержится ровно 77 букв X. В ответе запишите число — количество символов в найденной последовательности.

Файл к варианту: Ege24_v8.txt (150 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Возьмём 77 букв X подряд (с i-й по (i + 76)-ю) и расширим окно влево до предыдущей буквы X и вправо до следующей, не включая их. Получится самая длинная цепочка с ровно этими буквами: любая подходящая цепочка лежит внутри одного такого окна.

Условие на 2025. Чем длиннее окно, тем больше в нём вхождений 2025, поэтому достаточно проверить только эти «максимальные» окна: подходит окно, если в нём не меньше 176 вхождений.

Ответ для файла варианта: 3855.

Ответ: 3855

Решение на Python. Положите файл варианта рядом с программой.

from bisect import bisect_left, bisect_right

s = open('Ege24_v8.txt').readline().strip()
ys = [-1] + [i for i, c in enumerate(s) if c == 'X'] + [len(s)]
occ = [i for i in range(len(s) - 3) if s[i:i + 4] == '2025']    # начала вхождений
M, K = 77, 176
best = 0
for i in range(1, len(ys) - M):
    l, r = ys[i - 1] + 1, ys[i + M] - 1          # ровно M букв внутри [l, r]
    cnt = bisect_right(occ, r - 3) - bisect_left(occ, l)
    if cnt >= K:
        best = max(best, r - l + 1)
print(best)

Вариант 9

чередование букв и цифр

Файл к варианту: Ege24_v9.txt (100 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Ответ для файла варианта: 82.

Ответ: 82

Решение на Python. Положите файл варианта рядом с программой.

s = open('Ege24_v9.txt').readline().strip()
best = cur = 1
for i in range(1, len(s)):
    if s[i].isdigit() != s[i - 1].isdigit():
        cur += 1
    else:
        cur = 1
    best = max(best, cur)
print(best)

Вариант 10

не более 95 букв A

Текстовый файл состоит из заглавных букв латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых буква A встречается не более 95 раз.

Файл к варианту: Ege24_v10.txt (150 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Разбор

Идея. Самая длинная цепочка содержит ровно 95 букв A (или все, если их меньше) и упирается в соседние буквы A с обеих сторон. Запишем позиции букв A в список, добавив «границы» −1 и длину строки, и для каждого набора из 95 соседних букв найдём расстояние между ограничивающими буквами.

Ответ для файла варианта: 3180.

Ответ: 3180

Решение на Python. Положите файл варианта рядом с программой.

s = open('Ege24_v10.txt').readline().strip()
p = [-1] + [i for i, c in enumerate(s) if c == 'A'] + [len(s)]
K = 95
print(max(p[i + K + 1] - p[i] - 1 for i in range(len(p) - K - 1)))

Для самостоятельного решения

Вариант 11

ровно 46 букв Y и 2025

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 122 раз и при этом содержится ровно 46 букв Y. В ответе запишите число — количество символов в найденной последовательности.

Файл к варианту: Ege24_v11.txt (100 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Вариант 12

без одинаковых соседних

Текстовый файл состоит из символов Q, R, S, T. Определите максимальное количество идущих подряд символов, среди которых нет двух одинаковых соседних.

Файл к варианту: Ege24_v12.txt (100 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Вариант 13

не более 107 букв D

Текстовый файл состоит из заглавных букв латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых буква D встречается не более 107 раз.

Файл к варианту: Ege24_v13.txt (150 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Вариант 14

чередование букв и цифр

Файл к варианту: Ege24_v14.txt (100 000 символов в одной строке). Для выполнения этого задания следует написать программу.

Вариант 15

ровно 66 букв X и 2025

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых подстрока 2025 встречается не менее 157 раз и при этом содержится ровно 66 букв X. В ответе запишите число — количество символов в найденной последовательности.

Файл к варианту: Ege24_v15.txt (100 000 символов в одной строке). Для выполнения этого задания следует написать программу.