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

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

Ну что, работяги, погнали смотреть последние 2 способа для очень жесткого типа задач, отобравших надежды у многих желающих хоть раз увидеть 3 цифры в собственных результатах ЕГЭ 🥲

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

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

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

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

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

➡️ Двойной цикл и split() + join() (сейчас)

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

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

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

3⃣ Двойной цикл

Идея: Аналогично прошлому способу будем работать с двумя указателями - левым и правым. Только тут не паримся, просто оба перебираем циклами for, методом count() считаем количество T между ними, если 100 - обновляем максимум. Но главная проблема вложенного перебора - время. И чтобы её порешать, внедрим 2 оптимизации:

1) правый указатель перебираем так, чтобы смотреть только строки, длиннее максимальной;

2) когда расширили строку слишком сильно, что в ней больше 100 Т, перестаем расширять, останавливаем внутренний перебор правого указателя.

Код:

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

mx = 0

for l in range(len(s)):

for r in range(l + mx, len(s)):

s1 = s[l:r + 1]

if s1.count('T') == 100:

mx = max(mx, len(s1))

elif s1.count('T') > 100:

break

print(mx)

4⃣ Мегалайфхак: split() + join()

Идея: Рубим строку методом split() по буквам Т. Получаем список подстрок, между которыми было ровно по 1 букве Т. Если в исходной строке стояло 2 подряд, строка между ними будет пустой. Остаётся брать 101 подряд идущий кусочек (между ними ровно 100 Т), методом join() обратно склеивать в одну строку, возвращая уничтоженные Т, и обновлять максимум! И это работает быстро: split() и join() сами по себе очень оптимизированы в питоне!

Код:

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

a = s.split('T')

mx = 0

for i in range(len(a) - 100):

s1 = 'T'.join(a[i:i + 101])

mx = max(mx, len(s1))

print(mx)

По традиции дам домашку для закрепления! №24.40012 и №24.10029 из базы bank-kege.ru! Можете делиться в комментах своими решениями! Если освоили все 4 способа, то этот тип №24 у вас закрыт на все 100%. Я чаще всего пользуюсь первым из-за удобной короткой записи, но ученикам рассказываю по максимуму все.

Давайте по традиции голосовать, какой способ зашел больше?

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

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

😁 Двойной цикл

💘 split() + join()

Ну а дальше перейдем к следующему типу! Продолжаем серию!

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

#задание24