Задачи с ограниченным количеством в №24

Задачи с ограниченным количеством в №24

👋 Продолжаем серию постов с обзором типов 24 задач и всех способов решения!

✅ Повторяющиеся комбинации

✅ Запрещённые комбинации

👉 Ограниченное количество

➡️ Анализ индексов (сейчас)

🔜 Метод двух указателей

🔜 Двойной цикл и split() + join()

🔜 Сложные шаблоны

🔜 Несколько строк

🔜 Частотный анализ

Сегодня рассмотрим задачи про ограниченное количество - тип, от которого все были в шоке на ЕГЭ-2023, позже он встречался и на ЕГЭ-2025. По сравнению с предыдущими двумя типами тут прям заметен скачок по сложности, поэтому я расскажу максимальное количество способов решения, чтобы каждый выбрал своё!

Во всём разбираться уже по традиции будем сразу на практике, возьмем задачу №24.10017 из базы bank-kege.ru

Условие:

Текстовый файл состоит из символов T, U, V, W, X, Y и Z. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ T встречается ровно 100 раз.

Общие замечания:

Так как необходимо найти максимальную длину, необходимо строку, в которой 100 букв T максимально расширять влево и вправо, вплоть до букв T, которые входить не должны. Рассмотрим пример для строки с тремя буквами T.

Дана строка: ATAATAAATAAAATAATA

3 буквы T встречаются в строке TAAATAAAAT, но для поиска максимума расширяем ее вправо и влево: AATAAATAAAATAA. Задача сводится к тому, чтобы посмотреть все строки со 100 буквами T, захватывая как можно больше символов слева и справа от них.

1⃣ Анализ индексов

Идея: Сделаем список с индексами всех букв T. Будем рассматривать по 100 подряд идущих T (с i + 1 по i + 100 включительно). Слева захватываем всё до предыдущей T (i-ой), а справа - до следующей (i + 101). Чтобы корректно рассмотреть не только строки в середине, но и в начале и в конце файла (у которых с одной из сторон нет не входящей T), сами допишем эти буквы в начало и в конец, входить в рассматриваемые подстроки они не будут, просто помогут нам оттолкнуться. Сами индексы можете использовать другие, главное правильно подстроить range() для их перебора.

Код:

s = open('24.10017.txt').readline()

s = 'T' + s + 'T'

ind_T = []

for i in range(len(s)):

if s[i] == 'T':

ind_T.append(i)

mx = 0

for i in range(len(ind_T) - 101):

start = ind_T[i] + 1

end = ind_T[i + 101] - 1

mx = max(mx, end - start + 1)

print(mx)

Короткий код:

s = open('24.10017.txt').readline()

s = 'T' + s + 'T'

ind_T = [i for i in range(len(s)) if s[i] == 'T']

print(max(ind_T[i + 101] - ind_T[i] - 1 for i in range(len(ind_T) - 101)))

Ставьте 🔥, если понравился способ! А еще задам вам домашку! Порешайте 24.10014, 24.10027

в bank-kege.ru! Это всё задачи с реальных ЕГЭ) Решениями можете делиться в комментариях. В следующем посте расскажу целых 3 варианта метода двух указателей!

#информатика

#задание24