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

[@Benhooky]

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

[@iceak001]

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

[@babysya696]

спасибо, Лёня, за разбор!

[@unthinkable1854]

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

[@Vadim-yz2bd]

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

[@leoshastin]

спасибо за фидбек) ближе к экзамену, возможно, запишу подобное видео

[@Vadim-yz2bd]

спасибо, буду ждать @@leoshastin

[@Alam_pang]

Красавчик, понятно и ясно объяснил!

[@positivedegree4029]

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

[@Kattik]

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

[@sosechhh]

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

[@килбос99]

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

[@violsil2854]

Еще пара замечаний. 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]. Такой код тратит время на преобразование списка, но зато не делает второй проход.

[@nikkropinoff]

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

[@violsil2854]

Леонид, с Вашего позволения сделаю замечание к временной отметке 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 # зафиксировал изменения в счетчике Понятно, что с точки зрения алгоритма это одно и то же, но комментарии к коду должны быть корректными, в противном случае начинающий программист может воспринять суть искаженно, и, впоследствии, сделать ошибку.

[@osmanof9209]

Ваше решение ошибочно

[@violsil2854]

@@osmanof9209 Это не решение. Это запись фрагмента кода "другими словами". На суть процесса это вообще никак не влияет.

[@polx990]

Леонид, я ваш фанат

[@yuwier]

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

[@kev1n232]

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

[@violsil2854]

По задаче 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, как в предложенном методе). Хотя, по сути, это просто вариация "сплита".

[@luckytima2315]

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

[@теперьэтоаккаунтигорька]

Классный метод

[@froppe5781]

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

[@leoshastin]

Возьми любой небольшой примерчик (строчку длиной 10-15 символов) и выполни трассировку алгоритма на этой строке. Это лучший способ понять, как это работает, никакие словесные объяснения не дадут более глубокого понимания

[@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

[@leoshastin]

Левый указатель будет сдвигаться до тех пор, пока выражение a > 1 or b > 1 даёт истину, т.е., в данном случае пока значения a, b не станут

[@realMiska]

@@leoshastin понял, спасибо

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

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

[@leoshastin]

По условию нужно конкретное число Y. В разборе все правильно

[@a7kerkh]

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

[@leoshastin]

привет, однозначно не стоит, если у тебя финансовый вопрос стоит на первом месте

[@crushitelyoutuba]

спасибо братан за этот способ, заменяет сплит, а сплит я просто ненавижу!)

[@TankucT_AC]

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

[@ДмитрийМихеев-у6о]

почему то на платном курсе на степике не могу перейти по ссылке с конспектом для номера 13, хотя раньше получалось. Проверьте, пожалуйста, работает ли у Вас.

[@leoshastin]

Всё работает, попробуйте чуть позже ещё раз. Скорее всего какой-то временный технический сбой

[@covid0668]

а этот алгоритм почти под все задачи может подойти?

[@leoshastin]

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

[@covid0668]

боже зачем составители усложняют 24 задание а 25 оставляют супер простым?

[@MAXMAXBETOBSO2]

А почему в 5 задаче именно s[r-7:r+1], почему когда пишешь s[r-8:r] ответ другой?

[@leoshastin]

Правая граница среза не включается, как и в range

[@DopamineDetox-o6k]

А во 2 задаче не будет такого, что левый указатель будет находиться дальше правого?

[@leoshastin]

В момент "телепортации" будет, иначе никогда

[@andr779]

Зачем так сложно

[@leoshastin]

Если вы знаете, как сделать проще, тогда будьте добры нам продемонстрировать

[@АнтонКузьмин-р5ъ]

вот первую ты подробно разжевал. а третью? вот все ....вот все....Все бы уже так тогда разжевывал!

[@leoshastin]

Там нечего разжёвывать, какие-то дополнительные пояснения избыточны, ибо задача минимально отличается от предыдущих

[@alexeyich1104]

объясните, что я делаю не так(задание РЕШУ ЕГЭ 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]

но мой код работает быстрее