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

• Метод двух указателей помогает решать задачи ЕГЭ по информатике.  

• Задачи можно найти на сайте комп.егэ.ру.  

• Метод полезен для задач 24 и 27, которые считаются сложными.  

• Метод двух указателей позволяет решать задачи 24 и 27.  

• Он шаблонный и меняется только принцип сдвига указателей.  

• Метод можно использовать для задач, которые решаются с помощью сплита.  

• Курс на платформе Степика с множеством задач и теорией.  

• Подходит для новичков и опытных учеников.  

• Возможность общения и поддержки через беседу ВКонтакте.  

• Найти наибольшую подстроку, в которой буква "игрек" встречается не более 150 раз.  

• Пример с подстрокой, в которой "игрек" встречается два раза.  

• Важно выбрать наибольшую подстроку, удовлетворяющую условию.  

• Метод позволяет выбрать подстроку, удовлетворяющую условиям.  

• Используется два указателя: левый и правый.  

• Левый указатель указывает на начало подстроки, правый - на конец.  

• Левый указатель указывает на начало фрагмента, правый - на конец.  

• Фрагмент строки находится между индексами левого и правого указателей.  

• Все символы фрагмента находятся между индексами левого и правого указателей.  

• Длина фрагмента подстроки определяется как разность указателей р минус эль плюс один.  

• Пример с тремя символами: длина равна два минус ноль плюс один, что равно трем.  

• Важно понимать, что это часто встречается в задачах.  

• Указатели р и эль начинаются с первого символа строки.  

• Цель - выбрать фрагмент наибольшей длины, удовлетворяющий условию.  

• Условие: не более двух вхождений игрека в фрагмент.  

• Левая граница не может двигаться, чтобы не нарушить условие.  

• Правая граница может сдвигаться вправо для увеличения длины фрагмента.  

• Пример: сдвиг р вправо увеличивает длину фрагмента до трех символов.  

• Проверка количества вхождений игрека в фрагмент.  

• Если вхождений больше двух, левая граница сдвигается влево для уменьшения количества игреков.  

• Пример: сдвиг эль влево уменьшает количество игреков до двух.  

• Описание строки и счетчика вхождений игрека.  

• Сдвиг правого указателя увеличивает счетчик, сдвиг левого уменьшает.  

• Пример реализации на Python для описания и сдвига указателей.  

• Рассматриваются два варианта реализации сдвига вправо: цикл while и цикл for.  

• Цикл for проще в реализации, так как не нужно думать о завершении сдвига.  

• Цель - выбрать максимальный фрагмент, содержащий два символа.  

• Перебор правой границы начинается с нулевого индекса и продолжается до конца строки.  

• Сдвиг правой границы на один индекс каждый раз.  

• Под отрезок может стать плохим, если в нем больше двух символов.  

• Проверка текущего символа на символ "игрек".  

• Увеличение счетчика при обнаружении "игрека".  

• Под отрезок считается хорошим, если счетчик не превышает двух.  

• Если счетчик больше двух, левая граница сдвигается до тех пор, пока счетчик не станет равным двум.  

• Проверка текущего символа и уменьшение счетчика на единицу при удалении символа.  

• Под отрезок становится хорошим после сдвига левой границы.  

• Под отрезок считается хорошим, если он соответствует условиям.  

• Обновление максимальной длины фрагмента.  

• Проверка правильности алгоритма на примере.  

• Алгоритм эффективен, так как оба указателя двигаются только вперед.  

• Сложность алгоритма линейная, так как делается два прохода по строке.  

• Алгоритм работает всегда и является универсальным.  

• Применение алгоритма к задачам из сборника Крылова.  

• Скачивание и подготовка файлов для работы.  

• Оптимизация кода для улучшения производительности.  

• Открытие нового файла и чтение условий задачи.  

• Определение максимальной подстроки, в которой буква "а" встречается не более 700 раз, а буква "е" не встречается.  

• Введение переменных для левого и правого указателей.  

• Инициализация всех переменных значениями по умолчанию.  

• Сдвиг левого указателя и проверка наличия буквы "а".  

• Увеличение счетчика при обнаружении "а" и сдвиг левого указателя при превышении 700 вхождений "а".  

• Проблема с буквой "е" в подстроке.  

• Решение: телепортировать левый указатель на позицию после "е".  

• Проверка и корректировка длины подстроки при необходимости.  

• Поиск минимальной подстроки, в которой буква "икс" встречается не менее 500 раз, а буква "игрек" не встречается.  

• Обрезка подстроки до достижения 500 вхождений "икс".  

• Реализация алгоритма с учетом контроля длины и количества "икс".  

• Проверка количества "икс" в подстроке и корректировка длины при необходимости.  

• Обрезка краев подстроки для достижения 500 вхождений "икс".  

• Проверка минимума длины подстроки и обновление ответа.  

• Проверка правильности ответа.  

• Уточнение алгоритма для достижения минимальной длины подстроки.  

• Завершение решения задачи.  

• Нужно найти максимальное количество символов, в которых ровно по одному разу встречаются буквы "а" и "б".  

• Используем файл из группы ВКонтакте для решения задачи.  

• Заводим две переменные "а" и "б" для хранения количества букв в фрагменте.  

• Контролируем, чтобы буквы "а" и "б" встречались ровно по одному разу.  

• Если условие нарушается, сдвигаем левый фрагмент на один индекс.  

• Проверяем, что буквы встречаются ровно по одному разу, и увеличиваем максимальную длину.  

• Выводим ответ: 182.  

• Решение простое, но требует контроля двух букв.  

• Для пяти букв можно использовать словарь или переменные.  

• Нужно определить максимальное количество идущих подряд символов, среди которых сочетание символов "инфинити" встречается ровно тысячу раз.  

• Проверяем символы с индекса "р" до "р плюс восемь".  

• Если найдено "инфинити", увеличиваем счетчик.  

• Проверяем символы с индекса "р минус семь" до "р плюс один".  

• Если "инфинити" не полностью встроено, уменьшаем счетчик.  

• Контролируем длину фрагмента, чтобы избежать ошибок.  

• Скачиваем файл и начинаем проверку.  

• Проверяем, что "к" больше тысячи, и корректируем до тысячи.  

• Если "к" ровно тысяча, увеличиваем максимальную длину.  

• Получаем ответ: 36747.  

• Концепция сдвига правой границы и подстройки левой границы применима ко многим задачам.  

• Важно понять принцип сдвига границ для успешного решения.  

• Рассматривается сложный номер, который сложно решить с помощью сплита.  

• Используется метод с двумя указателями для решения.  

• Проверяется количество гласных и точек в строке.  

• Рекомендуется решать задачи без использования вложенных циклов и брейков.  

• Задача сложная и требует оптимального решения.  

• Пример задачи, где нужно найти количество подстрок без определенных букв.  

• Пример задачи с подстроками длиной не менее трех символов.  

• Подстроки не должны содержать все три буквы одновременно.  

• Пример с подстроками, которые подходят и не подходят.  

• Проверка подстрок на наличие всех трех букв одновременно.  

• Использование индексов для проверки длины подстроки.  

• Пример с подстроками и проверка правильности ответа.  

• Обнаружена ошибка в подсчете подстрок.  

• Пример с добавлением символа для проверки.  

• Вывод подстрок для проверки правильности решения.  

• Обсуждение необходимости сдвига при подсчете подстрок.  

• Пример с подстроками длиной три и четыре символа.  

• Проверка правильности подсчета с помощью приборного решения.  

• Обнаружение ошибки в подсчете подстрок.  

• Проблема с учетом подстрок на разных итерациях.  

• Необходимость контроля учета подстрок при длине более четырех символов.  

• Предложение контролировать подсчет при длине более четырех символов.  

• Пример с подстроками длиной три и четыре символа.  

• Исправление ошибки в подсчете подстрок.  

• Подведение итогов решения задачи.  

• Обсуждение сложности задачи и необходимости использования двух указателей.  

• Призыв к использованию курса для подготовки к ЕГЭ по информатике.