Задание №24 - Метод двух указателей | Информатика ЕГЭ 2024
Учимся применять метод двух указателей для решения 24-х задач из ЕГЭ по Информатике. Готовимся на 100 баллов вместе :)
😉 Записывайся на индивидуальные и групповые занятия:
➤ t.me/Princess_Leonid
💯 Промокод - ZASOTKOI
📚 Мои Бесплатные Курсы на Stepik :
➤ Python 3 - stepik.org/122809
➤ "С Нуля до 40+ Баллов" - stepik.org/122795
➤ Тренировочные варианты - stepik.org/171835
➤ "Задание №27: переборные алгоритмы" - stepik.org/175944
💰 Мои Платные Курсы на Stepik :
➤ Задания 1-23 - stepik.org/a/121057
➤ Задание 24 - stepik.org/a/113430
➤ Задание 25 - stepik.org/a/115478
➤ Задание 26 - stepik.org/a/118263
➤ Задание 27 - stepik.org/a/111154
➤ Задания 1-27 - stepik.org/a/123226
➤ Задания 24-27 - stepik.org/a/123227
➤ Задания 1-26 - stepik.org/a/171738
➤ Задания 26-27 - stepik.org/a/171737
🔗 Ссылки :
➤ Группа ВК - shastin_ege
➤ Беседа в ВК - vk.me/join/yD5wZwEGSTFR9QzLU7...
➤ Я в ВК - leonid_shastin
➤ Telegram: t.me/infkege
▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃
🎬 Навигация :
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
#кегэ #егэ #информатика
Пікірлер: 50
Спасибо за детальный разбор!) Вдохновили снова начать ботать эти задачи)
Мне еще нравится ребятам объяснять через окно, в целом идея схожая, но будто бы сделать буфер - окно и потом его обрезать может быть попонятнее, хотя, конечно, метод двух указателей лучше потому что это база для литкода ) Спасибо за контент!
Леонид, с Вашего позволения сделаю замечание к временной отметке 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 # зафиксировал изменения в счетчике Понятно, что с точки зрения алгоритма это одно и то же, но комментарии к коду должны быть корректными, в противном случае начинающий программист может воспринять суть искаженно, и впоследствии сделать ошибку.
По задаче 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, как в предложенном методе). Хотя, по сути, это просто вариация "сплита".
Большое спасибо Вам за видео, Леонид!
спасибо, Лёня, за разбор!
Спасибо за такой подробный разбор💗 Очень полезный метод!
с первого раза все у вас понимаю) лёня, спасибо
Спасибо, очень красивое решение и просто для понимания!
большое спасибо! крайне ценный контент
Красавчик, понятно и ясно объяснил!
Еще пара замечаний. 1) На отметке 10:36 вы вводите ограничение (l 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]. Такой код тратит время на преобразование списка, но зато не делает второй проход.
Огромное спасибо за разбор, я от Алексея Михайловича 🙃 Лайк и подписка
Леонид, я ваш фанат
Здравствуйте, спасибо вам за вашу работу! Не могли бы вы записать видео по тайм-менеджменту на экзамене, как лучше распределить время на разные задачи/части, буду очень вам благодарен❤
@leoshastin
4 ай бұрын
спасибо за фидбек) ближе к экзамену, возможно, запишу подобное видео
@Vadim-yz2bd
4 ай бұрын
спасибо, буду ждать @@leoshastin
Здравствуйте! Я от Алексея Кабанова) Спасибо за видео!
Ну слушай братик это имба так то дикая
Я от Алексея Кабанова. Респект за метод))
привет, можешь объяснить, как работает while в 3-ей задачке? у нас же внутри вайла при попадании в 'X' будет уменьшаться их счетчик. Сам вайл живой, пока счетчик >= 500, то есть после цикла мы получим счетчик с максимальным значением 499, как он зайдет в проверку условия, если условие от 500?
@leoshastin
Ай бұрын
Возьми любой небольшой примерчик (строчку длиной 10-15 символов) и выполни трассировку алгоритма на этой строке. Это лучший способ понять, как это работает, никакие словесные объяснения не дадут более глубокого понимания
почему то на платном курсе на степике не могу перейти по ссылке с конспектом для номера 13, хотя раньше получалось. Проверьте, пожалуйста, работает ли у Вас.
@leoshastin
4 ай бұрын
Всё работает, попробуйте чуть позже ещё раз. Скорее всего какой-то временный технический сбой
Классный метод
Здравствуйте, вот отрывок кода: 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
@leoshastin
2 ай бұрын
Левый указатель будет сдвигаться до тех пор, пока выражение a > 1 or b > 1 даёт истину, т.е., в данном случае пока значения a, b не станут
@realMiska
2 ай бұрын
@@leoshastin понял, спасибо
1:16:04 , стоп, если r - l +1 >= 3, то r - l >= 2, нет разве?
на 19:05 неправильно же. Просто строка так совпала, не гарантировано, что строка, где больше Y по длине больше. Допустим, XYXY - два Y, XXXXXXXXXXY - один Y, но строка длинней.
@leoshastin
15 күн бұрын
По условию нужно конкретное число Y. В разборе все правильно
Привет! Можешь сказать сколько примерно зарабатываешь на курсе в месяц? Очень интересно тоже начать преподавать информатику для ЕГЭ и думаю стоит ли оно того
@leoshastin
27 күн бұрын
привет, однозначно не стоит, если у тебя финансовый вопрос стоит на первом месте
А почему в 5 задаче именно s[r-7:r+1], почему когда пишешь s[r-8:r] ответ другой?
@leoshastin
3 ай бұрын
Правая граница среза не включается, как и в range
а этот алгоритм почти под все задачи может подойти?
@leoshastin
5 ай бұрын
Многие актуальные задачи влёт решаются с помощью этого алгоритма. Способ нужно выбирать в зависимости от задачи, где-то гораздо легче обычная динамика или разбиение через split
@covid0668
5 ай бұрын
боже зачем составители усложняют 24 задание а 25 оставляют супер простым?
Всем привет, однозначно лайк, кто тоже с веба Алексея Кабанова
спасибо братан за этот способ, заменяет сплит, а сплит я просто ненавижу!)
А во 2 задаче не будет такого, что левый указатель будет находиться дальше правого?
@leoshastin
5 ай бұрын
В момент "телепортации" будет, иначе никогда
Зачем так сложно
@leoshastin
5 ай бұрын
Если вы знаете, как сделать проще, тогда будьте добры нам продемонстрировать
вот первую ты подробно разжевал. а третью? вот все ....вот все....Все бы уже так тогда разжевывал!
@leoshastin
4 ай бұрын
Там нечего разжёвывать, какие-то дополнительные пояснения избыточны, ибо задача минимально отличается от предыдущих
объясните, что я делаю не так(задание РЕШУ ЕГЭ 59729) s = open('24.txt').readline() k=0 l=0 m=999999999 for r in range(1,len(s)): if s[r-1:r+1]=="TT": k+=1 while k>150: if s[l:l+2]=="TT": k-=1 l+=1 if k==150: m=min(m,r-l+1) print(m)
@revlze
Ай бұрын
я бы так написал f = open('24.txt').readline() const = 150 q = [0] * 151 k = 0 m = 10 ** 10 for r in range(1, len(f)): if f[r - 1:r + 1] == 'TT': q += [r - 1] k += 1 if k == const: m = min(r - q[-const] + 1, m) k -= 1 print(m)
@revlze
Ай бұрын
так лол, 3 задание, в данном видео - есть на твой вопрос. ниже немного переделанный код из 3 задания f = open('24.txt').readline() k = l = 0 m = 10**10 const = 150 for r in range(1, len(f)): k += f[r-1:r+1] == 'TT' while k - (f[l:l+2] == 'TT') >= const: k -= f[l:l+2] == 'TT' l += 1 if k == const: m = min(m, r-l+1) print(m)
@revlze
Ай бұрын
но мой код работает быстрее