Задание №24 - Метод двух указателей | Информатика ЕГЭ 2024

Учимся применять метод двух указателей для решения 24-х задач из ЕГЭ по Информатике. Готовимся на 100 баллов вместе :)

😉 Записывайся на индивидуальные и групповые занятия:

💯 Промокод - ZASOTKOI

📚 Мои Бесплатные Курсы на Stepik :

💰 Мои Платные Курсы на Stepik :

🔗 Ссылки :
▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃

🎬 Навигация :
00:00 Приветствие
00:17 О методе двух указателей
02:39 Задание 1
30:21 Задание 2
39:06 Задание 3
44:45 Задание 4
48:05 Задание 5
54:56 Задание 6
57:18 Задание 7 (сложное)
01:16:57 Итоги и напутствие

📷 Информация о Видео :
➤ Запись Видео - OBS Studio
➤ Язык Программирования - Python 3.10
➤ Среда Разработки - IDLE
➤ Превью Видео - Adobe Photoshop 2020

#кегэ #егэ #информатика

[iceak]

с первого раза все у вас понимаю) лёня, спасибо

[Benhooky]

Мне еще нравится ребятам объяснять через окно, в целом идея схожая, но будто бы сделать буфер - окно и потом его обрезать может быть попонятнее, хотя, конечно, метод двух указателей лучше потому что это база для литкода )
Спасибо за контент!

[unthinkable]

Большое спасибо Вам за видео, Леонид!

[positivedegree]

Спасибо, очень красивое решение и просто для понимания!

[Kattik]

Спасибо за такой подробный разбор💗
Очень полезный метод!

[Vadim-yzbd]

Здравствуйте, спасибо вам за вашу работу! Не могли бы вы записать видео по тайм-менеджменту на экзамене, как лучше распределить время на разные задачи/части, буду очень вам благодарен❤

[violsil]

Еще пара замечаний.
1) На отметке 10:36 вы вводите ограничение (l <= r), но в коде используете строку (l = r + 1). Т.е. реализация кода противоречит Вашим исходным допущениям. Какой тогда был смысл их делать??? Раз уж Вы сделали такие допущения, передвигайте (l) на позицию (r): l = r. Ибо, так как s(l) = s(r) = 'E', счетчик букв 'A' все равно будет сбрасываться до нуля.
2) Зачем пересчитывать значение (m) на КАЖДОЙ итерации? Это нужно делать лишь в случае регистрации (s[r] == 'E') или (k > 700). Т.к. в противном случае очевидно, что разрешенный фрагмент еще не достиг своей предельной длины. Регистрируем истинность логического выражения "(s[r] == 'E') or (k > 700)", корректируем значение (m). При этом длина корректирующего отрезка равна не (r - l + 1), а (r - l), ибо текущий символ, стоящий на позиции (r), запрещен.
Код может выглядеть как-то так:

s = open('24var04 (1).txt').readline()
k = l = m = 0
for r in range(len(s)):
k += s[r] == 'A'
if (s[r] == 'E') or (k > 700):
m = max(m, r - l)
if s[r] == 'E':
l = r
k = 0
while k > 700:
k -= s[l] == 'A'
l += 1
print(m)

Такая программа работает в полтора раза быстрее. Ясное дело, что это мелочь, но если Вы стремитесь сделать код эффективным, зачем делать лишние телодвижения?
К слову, еще эффективнее может быть код, который запоминает последние 701 позиций символа 'A' (допустим, в список pointers), и при нахождении 702-го символа вычисляет разность (r - l - 1), т.е. отбрасывает начальную и конечную буквы 'A', определяя максимальную длину допустимого отрезка. С последующей циклической перестановкой указателей: pointers = pointers[1:] + [i]. Такой код тратит время на преобразование списка, но зато не делает второй проход.

[килбос]

Я от Алексея Кабанова. Респект за метод))

[nikkropinoff]

большое спасибо! крайне ценный контент

[violsil]

Леонид, с Вашего позволения сделаю замечание к временной отметке 25:35

while k>2:
if s[l] == 'Y': # убрал один Y из фрагмента
k -= 1
l += 1 # сдвигаю левую границу

Комментарий к коду логически ошибочен. Если s[l] == 'Y', то мы пока еще НЕ УБРАЛИ символ 'Y' из текущего фрагмента (символ находится на левой границе нашего фрагмента). Символ 'Y' мы убираем из фрагмента только ПОСЛЕ сдвига левого указателя на одну позицию вправо. Если все же хочется написать подобный комментарий в коде, следует переставить операторы местами:

while k>2:
l += 1 # сдвигаю левую границу
if s[l-1] == 'Y': # убрал сдвигом один Y из фрагмента
k -= 1 # зафиксировал изменения в счетчике

Понятно, что с точки зрения алгоритма это одно и то же, но комментарии к коду должны быть корректными, в противном случае начинающий программист может воспринять суть искаженно, и, впоследствии, сделать ошибку.

[sosechhh]

Здравствуйте! Я от Алексея Кабанова)
Спасибо за видео!

[yuwier]

Огромное спасибо за разбор, я от Алексея Михайловича 🙃
Лайк и подписка

[kevn]

Всем привет, однозначно лайк, кто тоже с веба Алексея Кабанова

[violsil]

По задаче 3: вообще подобные задачи (равно как и №2) удобнее делать с помощью метода split(). Но, понятное дело, речь в данном уроке про другой подход.
Касаемо реализации: а зачем такие сложные танцы с бубнами? Имхо, проще сделать следующим образом (но это вкусовщина, разумеется). С помощью метода find() найти индекс первого символа "X". Присвоить обоим указателям этот индекс. Далее, бежать правым указателем до тех пор, пока не насчитаем ровно 500 символов. Зафиксировать текущую длину (выбрать минимальное из текущей длины и ранее записанной в m). Перебросить оба указателя в позиции следующих символов "X" (левый до следующего и правый до следующего). Таким образом, мы снова выделим фрагмент, начинающийся с "X", заканчивающийся в "X", и содержащий ровно 500 символов "X". Фиксируем длину. И т.д.

Переброс указателей в следующие позиции можно делать не в цикле, а путем использования find() в срезе строки (начинать срез с позиции, стоящей непосредственно после позиции предыдущего символа "X"). Если в каком-то из допустимых фрагментов встречается "Y", попросту пропускать его и переходить к следующему. Поиск "Y" также можно делать с помощью find() в срезе между позициями левого и правого указателя.

Вообще говоря, можно вовсе не использовать два указателя, обходиться лишь одним. Находим c помощью find() первый символ "X". Обрезаем строку S до этого символа (включая сам символ). Бежим до тех пор, пока не насчитаем 499 символов "X". Фиксируем длину (+1, т.к. первый символ обрезали). Обрезаем строку S по текущую позицию. Бежим до тех пор, пока не насчитаем 499 символов "X". Фиксируем длину (+1, т.к. первый символ обрезали). и т.д. Если на пути встретился хотя бы один символ "Y", длину фрагмента не фиксируем (просто переходим к следующему). Все делается только в один проход (а не в 2, как в предложенном методе). Хотя, по сути, это просто вариация "сплита".

[luckytima]

Ну слушай братик это имба так то дикая

[Вергилий-кр]

на 19:05 неправильно же. Просто строка так совпала, не гарантировано, что строка, где больше Y по длине больше. Допустим, XYXY - два Y, - один Y, но строка длинней.

[froppe]

привет, можешь объяснить, как работает while в 3-ей задачке? у нас же внутри вайла при попадании в 'X' будет уменьшаться их счетчик. Сам вайл живой, пока счетчик >= 500, то есть после цикла мы получим счетчик с максимальным значением 499, как он зайдет в проверку условия, если условие от 500?

[TankucT_AC]

1:16:04, стоп, если r - l +1 >= 3, то r - l >= 2, нет разве?

[realMiska]

Здравствуйте, вот отрывок кода:
while a>1 or b>1:
a-=s[l]='A'

то есть если s[l] не 'А', то тогда уже будет s[l+1] и так далее, пока s[l+n] не станет 'А' (n-натур. число) ?
и еще не очень понял почему в count записываем r-l 1:04:50

[akerkh]

Привет! Можешь сказать сколько примерно зарабатываешь на курсе в месяц? Очень интересно тоже начать преподавать информатику для ЕГЭ и думаю стоит ли оно того