вентилятор
Удачи на экзаменах!

Два указателя в 24 Задании ЕГЭ по информатике



Привет! В этой статье мы посмотрим метод двух указателей в 24 Задании ЕГЭ по информатике.


Данный метод является мощным ответом на сложные задачи из 24 Задания ЕГЭ по информатике.


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





Задача (Классическая, минимальная цепочка)

Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле минимальное количество идущих подряд символов (длину не прерывной последовательности), среди которых символ F встречается ровно 2025 раз.


Для выполнения следует написать программу.


Скачать файл

Решение:

Напишем программу и потом разберём её.


f=open('24_du_1.txt')
s = f.read().strip()

l=r=count=0
kmin=10**10

for r in range(len(s)):
    if s[r]=='F': count += 1
    while count == 2025:
        kmin = min(kmin, r-l+1)
        if s[l]=='F': count -= 1
        l += 1
        
print(kmin)

В начале программы подвязываемся к файлу. Считываем всё содержимое в переменную s. С помощью функции strip() убираем символ переноса строки, если он там вдруг, случайно, есть.


Далее заводим левую границу l, правую границу r цепочки, которую мы рассматриваем в данный момент времени. Заводим счётчик count, который будет следить за количеством букв F в этой цепочке.


Левая и правая граница находятся на нулевом символе в самом начале. Те символы, где находятся левый и правый указатели так же включаются в рассматриваемую цепочку.


Переменная kmin отвечает за ответ.


В цикле for мы начинаем растягиваем правую границу от начала. С помощью условия мы проверяем, что нам встречается на правой границе. Если встречается символ F, счётчик count увеличивается на 1.





В определённый момент количество букв F в цепочке достигнет нужно значения (2025). Дальше нет смысла тянуть правую границу, ведь нужно найти минимальную цепочку! В подобных задачах дальше пишется цикл while. Всегда нужно подумать, какое условие написать в этом цикле. Мы ищем минимальную цепочку, поэтому ПОКА в счётчике значение 2025, нас всё устраивает, можно проверять цепочку на минимальность для ответа.


Длина цепочки в подобных задачах вычисляется по формуле:


Правая граница - Левая граница + 1

Откуда берётся +1 ?


ЕГЭ по информатике - Задание 24 (Два указателя, минимальная цепочка)

Посмотрите на рисунок. Левый указатель находится на 0. Правый указатель находится на 2. Если просто найти разницу, то получится 2-0=2. А символов на самом деле три. Поэтому нужно сделать +1.


В подобных задачах всегда нужно думать, когда делать проверку на ответ. Мы выбрали идеальное место. Если мы вошли в цикл While, то сейчас как раз нужно количество символов в нашей цепочке (2025), можно проверять.


Цикл for отвечает за правую границу, за расширение цепочки. Цикл While отвечает за левую границу, за уменьшение цепочки. Мы проверили цепочку на минимальность, и теперь в цикле while пытаемся уменьшить цепочку ещё, ведь нам нужна самая маленькая цепочка, которая отвечает условию задачи.


Если на левой границе встречается символ F, мы двигаем левую границу на 1 символ, и из счётчика count вычитаем 1. Если это произошло, то значение в счётчике count изменится, и мы выйдем из цикла while, можно дальше будет двигать правую границу. Если условие не сработает, то левая граница сдвинется вправо, цепочка уменьшится, но в ней останется нужно количество букв F. Мы добились своей цели, цепочку сделали ещё меньше.





Таким образом, мы будем двигать то правый указатель, то левый указатель. Так проверятся все нужные цепочки и мы получим ответ.


Метод двух указателей работает достаточно эффективно и программа не будет зависать даже на больших объёмах данных.


Ответ: 7270

Похожая задача разобрана в видеоролике:







Задача (Классическая, максимальная цепочка)

Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной последовательности), среди которых символ B встречается не более 300 раз.


Для выполнения следует написать программу.


Скачать файл

Решение:
f=open('24_du_1.txt')
s = f.read().strip()

l=r=count=0
kmax=0

for r in range(len(s)):
    if s[r]=='B': count += 1
    while count > 300:
        if s[l]=='B': count -= 1
        l += 1

    if count <= 300: kmax = max(kmax, r-l+1)
        
print(kmax)

В этой задаче нужно найти уже максимальную цепочку. Самое главное в методе двух указателей подумать, какое условие поставить в цикле while и где делать проверку нашей цепочки на максимальность (минимальность).


Как мы говорили, цикл while отвечает за уменьшение цепочки (за сдвиг левой границы), поэтому в этой задаче нет смысла входить в цикл while, пока в счётчике count нужное количество букв B. В этом случае будет двигаться правая граница, и мы будем получать цепочку как можно больше.


В определённый момент мы превысим допустимое значение букв B. В этом случае мы войдём цикл while, чтобы скорректировать цепочку, уменьшить её, т.к. дальше тянуть правую границу бессмысленно.





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


После цикла while мы делаем проверку на максимальность, т.к. именно в этом месте наша цепочка после корректировки содержит нужно количество букв B.


Дополнительную проверку на количество букв B (if count <= 300 ...) именно в этой задаче можно, наверное, не делать, но предлагаю всегда делать ещё раз эту проверку, потому что в некоторых задачах это может с нами сыграть злую шутку.


Ответ: 3268

Смотрите разбор похожей задачи в видеоролике:







Задача (символ C не встречается совсем)

Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной последовательности), среди которых символ F встречается не более 450 раз, а символ C не встречается совсем.


Для выполнения следует написать программу.


Скачать файл

Решение:
f=open('24_du_1.txt')
s = f.read().strip()

l=r=count=0
kmax=0

for r in range(len(s)):
    if s[r]!='C':
        if s[r]=='F': count += 1
        while count > 450:
            if s[l]=='F': count -= 1
            l += 1

        if count <= 450: kmax = max(kmax, r-l+1)
    else:
        l=r+1
        count=0
        
print(kmax)

В этой задачке начинаем с проверки, что на правой границе не встретился символ C. Если это так, то решаем, как в прошлый раз.


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


ЕГЭ по информатике - Задание 24 (Два указателя, символ C не встречается совсем)




Нужно передвинуть левую границу так, чтобы исчез символ C. Мы передвигаем левую границу в R+1.


ЕГЭ по информатике - Задание 24 (Два указателя, теперь в цепочке не будет символа E)

После этого счётчик count сбрасываем на 0, как будто начинаем наш поиск с самого начала.


Ответ: 1981

Похожую задачу смотрите в видео:







Задача (Следим за двумя символами)

Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ A встречается ровно 200 раз, а символ B — ровно 25 раз.


Для выполнения следует написать программу.


Скачать файл

Решение:
f=open('24_du_1.txt')
s = f.read().strip()

l=r=countA=countB=0
kmax=0

for r in range(len(s)):

    if s[r]=='A': countA += 1
    if s[r]=='B': countB += 1

    while countA > 200 or countB > 25:
        if s[l]=='A': countA -= 1
        if s[l]=='B': countB -= 1
        l += 1

    if countA == 200 and countB == 25: kmax = max(kmax, r-l+1)
        
print(kmax)

Здесь нужно уже следить за двумя буквами.


Если какая-то буква превысила допустимое значение, нужно корректировать левую границу (уменьшать цепочку).


Ответ: 369

Похожую задачу посмотрите в видеоролике:







Задача (Идём вперёд)

Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Найдите непрерывную цепочку символов наибольшей длины, для которой выполняются два условия:


  • символы идут в алфавитном порядке,
  • в последовательности находится не более одной гласной (AEIOUY).

В ответе укажите длину найденной цепочки. Для выполнения следует написать программу.


Скачать файл

Решение:
f=open('24-157.txt')
s = f.read().strip()

l=r=count=0
kmax=1
gl='AEIOUY'

if s[0] in gl: count = 1

for r in range(len(s)-1):
    if s[r] <= s[r+1]:
        if s[r+1] in gl: count += 1
        while count>1:
            if s[l] in gl: count -= 1
            l += 1
        if count <= 1: kmax = max(kmax, r+1-l+1)
    else:
        l=r+1
        if s[r+1] in gl:
            count = 1
        else:
            count=0
        
print(kmax)

Итак, счётчик count будет следить за количеством гласных в цепочке.





В начале цикла for проверяем, что мы имеем дело с цепочкой, в которой символы идут в алфавитном порядке. Если всё в порядке, действуем по привычной схеме. Правая граница следит за количеством гласных букв, но теперь правая граница - это r+1!


Из-за того, что происходит обращение "к соседу", то идём в цикле for до len(s)-1. Т.к. настоящая правая граница r+1, то когда вычисляем длину цепочки пишем r+1-l+1.


Итак, мы обращаемся к r+1, чтобы проверить гласная там буква или нет, но в самом начале цепочки символ r (он же будет нулевой символ s[0]) никто не проверяет. Поэтому мы должны это сделать в самом начале до цикла for, ведь счётчик count должен показывать актуальную информацию о текущей цепочке.


Разберёмся с веткой else, что будет если символы не идут в алфавитном порядке? Мы должны разрушить эту ситуацию, т.к. дальше тянуть правую границу бессмысленно. Мы сдвигаем левую границу l на r+1. Если мы сдвинем левую границу на r, мы не добьёмся результата. Символы, идущие не в алфавитном порядке останутся в цепочке.





Так же мы должны проверить первый символ новой цепочки на гласную букву, как мы это делали в начале перед циклом for. Мы проверяем именно символ r+1. Сейчас это символ r+1, но на новой итерации это как раз будет символ r, и его нужно проверить.


В kmax мы в начале присвоили 1 для случая, если условие, которое следит за алфавитном порядком, не сработает ни разу, у нас будет ответ 1.


Ответ: 9

Похожую задачу смотрите в видеоролике:







Задача (Жёсткая задача)

Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых комбинация символов CE встречается ровно 5 раз, а комбинации символов ECE и CEC ни разу не встречаются.


Для выполнения следует написать программу.


Скачать файл

Решение:
f=open('24_du_1.txt')
s = f.read().strip()

l=r=count=0
kmax=0

if s[0]+s[1]=='CE':
    count = 1
    
for r in range(len(s)-2):
    if s[r]+s[r+1]+s[r+2] != 'ECE' and s[r]+s[r+1]+s[r+2] != 'CEC' :
        if s[r+1]+s[r+2] == 'CE': count += 1
        while count>5:
            if s[l]+s[l+1]== 'CE': count -= 1
            l += 1
        if count==5: kmax = max(kmax, r+2-l+1)
    else:
        l=r+1
        if s[r+1]+s[r+2]=='CE':
            count = 1
        else:
            count=0
        
print(kmax)

Мы начинаем с условия, что в нашей цепочке нет комбинаций "ECE" и "CEC". Идём уже тремя символами.


Правая граница должна следить за парами CE. Далее действуем по стандартной схеме.


Важно понимать, что настоящая правая граница теперь r+2.


Обратите внимание, что пару CE ищем символами r+1 и r+2, но в самом начале цепочки первые два символа тоже нужно проверить. Вдруг именно там находится комбинация CE. Это мы делаем в начале перед циклом for, ведь счётчик count должен хранить всегда актуальную информацию.





Внутри цикла while смещаем стандартно левый указатель на 1. Если на левой границе будет пара CE, достаточно один символ убрать, чтобы пара разрушилась.


Если всё-таки нам встретилась запретная комбинация (ECE или CEC), то мы переносим левую границу так, чтобы разрушить эту комбинацию. Переносим левую границу на r+1.


А так же в ветке else нужно проверить опять первые два символа следующей новой цепочки. Сейчас это символы r+1 и r+2, но на следующей итерации это будут символы r и r+1.


Ответ: 286

Похожую задачу смотрите в видеоролике:







Задача (Закрепление)

Текстовый файл состоит из символов A, B, С, D, E, F. Определите в прилагаемом файле минимальное количество идущих подряд символов, среди которых комбинация символов CD встречается ровно 15 раз.


Для выполнения следует написать программу.


Скачать файл

Решение:
f=open('24_du_1.txt')
s = f.read().strip()

l=r=count=0
kmin=10**10
    
for r in range(len(s)-1):
    if s[r]+s[r+1] == 'CD': count += 1
    while count == 15:
        kmin=min(kmin, r+1-l+1)
        if s[l]+s[l+1] == 'CD': count -= 1
        l += 1
        
print(kmin)

Ответ: 182

Похожую задачу смотрите в видеоролике:





Удачи на ЕГЭ по информатике в 24 Задании!




24-05-2024 в 14:18:18






Поддержать сайт:


Похожая статья:

ЕГЭ по информатике 2021 - Задание 23 (Опираемся на результаты предыдущих шагов)

Сегодня речь пойдёт о 23 задании из ЕГЭ по информатике 2021....

Категория: Информатика  Подкатегория: ЕГЭ
Дата: 17-12-2020 в 20:57:28 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:




Нажимая кнопку Отправить, Вы соглашаетесь с политикой конфиденциальности сайта.