Задание 26 ЕГЭ по информатике · 05BFA6
Коробки и коржи: вложение с заданной разностьюВысокаяКЭС 3.10
В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно поместить в другую, если длина её стороны хотя бы на D единиц меньше длины стороны другой коробки, при этом любые две соседние коробки сделаны из разных материалов. Известны длины сторон и материалы коробок, имеющихся в наличии. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
Во входном файле сначала заданы N и D, затем для каждой коробки указаны длина стороны и материал — 0 или 1. В ответ запишите два числа: сначала максимальное количество коробок, затем максимально возможную длину стороны самой маленькой коробки. Для решения необходимы данные из прилагаемого входного файла.
1_05BFA6.zipВо входном файле сначала заданы N и D, затем для каждой коробки указаны длина стороны и материал — 0 или 1. В ответ запишите два числа: сначала максимальное количество коробок, затем максимально возможную длину стороны самой маленькой коробки. Для решения необходимы данные из прилагаемого входного файла.
Показать ответ
166 63
Подсказки (3)
- Отсортируйте коробки по длине стороны и рассмотрите построение цепочки от меньшей коробки к большей.
- Для коробки длины x можно использовать предыдущую коробку длины не больше x−D и другого материала. Храните лучшие результаты отдельно для обоих материалов.
- После сортировки поддерживайте максимальную длину цепочки для каждого материала среди уже обработанных коробок. Для каждой коробки вычисляйте длину цепочки через максимум по противоположному материалу среди коробок с длиной не более x−D; при равенстве максимальной длины выбирайте цепочку с большей длиной самой маленькой коробки.
Решение
1. Запишем каждую коробку как пару: длина стороны и материал. Отсортируем коробки по длине стороны. 2. Для коробки длины x и материала c допустимым предшественником является коробка материала 1−c с длиной не более x−D. 3. Для каждой группы коробок, проходя массив слева направо, найдём лучшие значения для обоих материалов среди ранее обработанных коробок. Чтобы не использовать коробку раньше времени, сначала вычислим значения для текущей группы, а затем добавим её в структуру лучших результатов. 4. Длина цепочки для текущей коробки равна единице плюс лучшая длина цепочки для противоположного материала среди допустимых предшественников. Одновременно сохраняем длину самой маленькой коробки в цепочке. 5. В конце выбираем цепочку с наибольшим количеством коробок. Если таких цепочек несколько, выбираем ту, у которой длина самой маленькой коробки максимальна.
Частые ошибки
- Не учитывать обязательное чередование материалов.
- Проверять разность длин как строго больше $D$, хотя требуется не менее $D$.
- Разрешать использовать коробки с одинаковой длиной, если условие $D=0$ не выполнено.
- Обновлять лучшие значения внутри одной группы до обработки всех коробок этой группы и тем самым использовать одну и ту же коробку повторно.
Источник: Открытый банк ФИПИ
Похожие задания
26В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 0C143326В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 38235A26В магазине есть N кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на…Коробки и коржи: вложение с заданной разностью · 553F8026В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 584C6A26В магазине для упаковки подарков есть N кубических коробок. Одну коробку можно поместить в другую, если длина…Коробки и коржи: вложение с заданной разностью · 8091A926В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · B1F57A26В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых…Коробки и коржи: вложение с заданной разностью · CBF8FC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.