Навигация по странице
О задании
Задание 26 ЕГЭ по информатике является одним из самых сложных заданий во всём экзамене. Оно требует от учащихся понимания алгоритмов сортировки, оптимизации и обработки числовых данных. Но такая сложность окупается количеством баллов, получаемых за решение этого задания, а именно, за дачу двух верных ответов на это задание можно получить целых два первичных балла.
В основе 26 задания лежит задача выбора оптимального подмножества элементов из заданного набора по определённым критериям. Например, вам предстоит выбрать подходящие под расписание мероприятия, самую выгодную стратегию покупки товаров в магазине или коробки, которые могут складываться друг в друга «матрёшкой».
Можно классифицировать задания 26 по нескольким базовым типам:
- Задачи на оптимальный выбор подмножества — необходимо выбрать максимальное количество элементов с ограничением по суммарному параметру
- Задачи на максимизацию выгоды — нужно выбрать элементы таким образом, чтобы получить максимальную прибыль или выгоду с учетом условий и ограничений
- Задачи на распределение ресурсов — требуется минимизировать количество используемых ресурсов при заданных требованиях
- Задачи на размещение объектов — оптимальное заполнение контейнера или распределение элементов в порядке их поступления
При этом есть множество различных алгоритмических техник, которыми можно решать эти задания:
- Сортировка массива — ключевой прием, позволяющий упорядочить данные по нужному параметру (возрастанию или убыванию)
- Жадные алгоритмы — стратегия последовательного выбора локально оптимальных решений для достижения глобального оптимума
- Итеративный подсчет — пошаговое суммирование параметров с проверкой ограничений
- Динамическое программирование — в редких случаях для более сложных версий задания
- Двухпроходные алгоритмы — когда необходимо сначала определить один параметр, а затем на его основе вычислить второй
Алгоритм решения
Все типы 26 заданий в этой статье расположены по возрастанию сложности. При этом алгоритмы их решения никак не связаны друг с другом. Единственное, что стоит отметить: значительная часть 26 заданий может решаться с помощью электронных таблиц. Но мы крайне рекомендуем вам научиться решать эти задания именно программным способом.
Такой подход гораздо более универсален и позволяет глубже понять используемые методы и алгоритмы. К тому же не каждое задание может решиться с помощью электронной таблицы, но программным способом решаются абсолютно все задания.
Как обычно в наших статьях мы сначала разберём решение какой-либо одной задачи, опишем идею решения, по возможности иллюстрируя каждый шаг, а в конце напишем алгоритм решения на языке Python.
Этот же алгоритм мы впоследствии и применим для решения примера. Правда, подробно описывать решения примера не будем — в дальнейшем вы и сами убедитесь, что решения заданий будут практически идентичны.
Тип 1
Начнём разбор 26 заданий с самого базового и простого типа. Для простоты назовем этот тип «жадная сортировка». Слово «жадная» здесь не просто так: дело в том, что использовать мы будем именно жадный алгоритм. Давайте вспомним, что такое жадные алгоритмы.
Жадный алгоритм — это алгоритм, который на каждом шаге делает локально оптимальный выбор в надежде, что это приведет к глобально оптимальному решению. Основной принцип — «бери лучшее сейчас, не думая о будущем».
Рассмотрим его применение к заданию с такой формулировкой:
Задание 2601
«В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны меньше длины стороны другой коробки не менее чем на 9 единиц.
Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле:
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», не менее 3 единиц.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32»
Итак, начнём с абстракции. Нам даны некоторые коробки. Пусть их будет 4 штуки со следующими длинами сторон:
- Коробка с длиной 40
- Коробка с длиной 32
- Коробка с длиной 28
- Коробка с длиной 50
Теперь предположим, что их нужно вложить друг в друга «матрёшкой», но так, чтобы длина сторон вложенной коробки была меньше длины сторон той коробки, в которую она вкладывается, не менее чем на 10 единиц.
То есть вложить коробку с длиной сторон 20 в коробку с длиной сторон 30 – можно, а такую же коробку вложить в другую, у которой длина сторон 29 – уже нельзя. Как нам поступить в такой ситуации?
Очевидно, что для начала нам следует взять самую большую коробку – ведь в неё точно поместится любая другая коробка. Но, правда, есть одно условие. Длина сторон вкладываемой коробки должна быть на 10 и более единиц меньше, чем длина сторон этой большой коробки.
В нашем случае самая большая коробка имеет длину 50 единиц. Теперь надо определить, какую же коробку в неё возможно вложить. Можно, конечно, перебирать все оставшиеся коробки. Самая маленькая – с длиной сторон 28 – точно же влезет в нашу большую коробку. Правда никакую другую коробку поместить в эту «матрёшку» мы уже не сможем.
Надо придумать какой-то удобный порядок проверки этих коробок. Раз мы взяли самую большую, то поставим её на первое место в нашем новом расположении коробок. Самую маленькую тогда поставим в конец. А между ними расположим все коробки в порядке убывания длины сторон.
То есть нам необходимо отсортировать коробки по убыванию длины сторон. Получаем следующий порядок коробок: 50 – 40 – 32 – 28.
Такая сортировка нам позволит за один проход цикла перебрать все коробки в нужном порядке: таким образом, чтобы каждая последующая имела длину сторон гарантировано меньшую (или равную) предыдущей коробки.
Первая коробка нам гарантированно подходит. Значит, идем перебирать каждую последующую и сверять её длину сторон с предыдущей. Если разница в длинах сторон не менее 10 единиц, то новая коробка нам тоже подходит. Например, здесь вторая по порядку коробка имеет длину сторон 40, следовательно, она нам подходит.
Но следующая коробка нам не подойдёт. Длина сторон у неё 32, что не удовлетворяет нашему условию. Тогда её мы просто пропускаем.
Последняя коробка с длиной сторон 28 нам подходит: разница между длинами сторон у предыдущей коробки (40) и этой (28) составляет 12 единиц, что удовлетворяет поставленному условию.
Таким образом, мы получаем наибольшее количество коробок, которое можно вложить друг в друга: это коробки с длинами 50, 40 и 28.
На таком абстрактном примере мы вывели алгоритм для определения наибольшего количества коробок, которые можно вложить друг в друга:
- Сортируем длины сторон по убыванию
- Берём первую коробку, то есть помещаем её в список с используемыми коробками
- Проверяем, что разница длин между текущей и следующей коробкой не менее заданного значения
- Если условие в пункте 3 пройдено, то добавляем новую коробку в список с используемыми; если не пройдено – пропускаем
- В ответ даём количество элементов в списке с используемыми коробками
Отлично, теперь проверим этот алгоритм на примере, который описан у нас в условии, и только потом перейдём к реальным данным.
У нас есть 5 коробок с длинами: 43, 40, 32, 40 и 30.
Отсортируем все коробки в порядке убывания длин: 43, 40, 40, 32 и 30.
Коробка с длиной 43 нам точно подходит, следующая с длиной 40 – тоже подойдет. Вторую коробку с длиной 40 мы пропускаем, а последней подходящей будет коробка со стороной 32.
Следовательно, максимальное количество подходящих коробок здесь 3, а максимальная длина самой маленькой – 32.
Наш алгоритм отлично работает, переходим к реальным данным. Считываем сначала первое число из файла в переменную N, а затем все остальные в список data, при этом приводя каждое значение к целочисленному типу.
with open('2601.txt') as file:
N = int(file.readline())
data = list(map(int, file))
Далее сортируем список data по убыванию значений:
# Сортируем по убыванию
data = sorted(data, reverse=True)
Работу с функцией sorted() и всеми её параметрами мы подробно рассматривали в прошлой статье. Настоятельно рекомендуем ознакомиться с ней!
В переменной res будем хранить список всех подходящих нам значений. Сразу поместим в него первый элемент из data – самую большую коробку.
# Самая большая коробка точно подходит
res = [data[0]]
Теперь в цикле проходимся по оставшимся элементам в data и сравниваем значения между собой. Если разность между предыдущим значением в res и элементом текущей итерации больше или равна 9, то добавляем этот элемент в res.
for i in data[1:]:
# Проверяем, что разница длин не менее 9
if res[-1] - i >= 9:
res.append(i)
В конце выводим количество элементов в списке res и значение последнего элемента в нём.
print(len(res), res[-1])
Полный код для решения этого задания выглядит так:
with open('2601.txt') as file:
N = int(file.readline())
data = list(map(int, file))
# Сортируем по убыванию
data = sorted(data, reverse=True)
# Самая большая коробка точно подходит
res = [data[0]]
for i in data[1:]:
# Проверяем, что разница длин не менее 9
if res[-1] - i >= 9:
res.append(i)
print(len(res), res[-1])
В результате получаем два ответа: 1040 и 57.
Пример
Задание 2607
«В кондитерской есть N круглых форм для коржей. Специализация кондитерской – многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 4 единицы меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.
Входные данные
В первой строке входного файла находится число N – количество форм для коржей в кондитерской (натуральное число, не превышающее 10 000). В следующих N строках находятся значения диаметров форм для коржей (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой в форме.
Запишите в ответе два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем – максимально возможный диаметр самого маленького коржа в таком торте.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящих для изготовления многоярусного торта, составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коржей равно 3, а максимально возможный диаметр самого маленького коржа равен 32»
В целом, задание идентично предыдущему. Разве что теперь используются коржи вместо коробок, и разница в диаметрах двух коржей должна быть не менее 4.
Подробно останавливаться на коде решения не будем, он практически идентичен рассмотренному ранее. Выглядит код к этому заданию так:
with open('2607.txt') as file:
N = int(file.readline())
data = list(map(int, file))
# Сортируем по убыванию
data = sorted(data, reverse=True)
# Самый большой корж точно подходит
res = [data[0]]
for i in data[1:]:
# Проверяем, что разница длин не менее 4
if res[-1] - i >= 4:
res.append(i)
print(len(res), res[-1])
В ответ здесь запишем числа 2172 и 50.