Задание 26 ЕГЭ по информатике · 38235A
Коробки и коржи: вложение с заданной разностьюПовышеннаяКЭС 3.10
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 6 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
Во входном файле в первой строке задано число N — количество коробок. В следующих N строках записаны длины сторон коробок. Запишите сначала наибольшее количество коробок, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
1_38235A.zipВо входном файле в первой строке задано число N — количество коробок. В следующих N строках записаны длины сторон коробок. Запишите сначала наибольшее количество коробок, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Показать ответ
1511 54
Подсказки (3)
- Как расположить длины сторон коробок, чтобы последовательно выбирать подходящие коробки?
- Отсортируйте длины сторон по возрастанию и при однократном просмотре выбирайте следующую коробку, если её сторона не меньше текущей стороны плюс 6.
- После построения максимально длинной цепочки запомните её количество и сторону первой выбранной коробки. Если цепочки одинаковой длины, выбирайте ту, у которой первая сторона больше.
Решение
1. Сначала отсортируем все длины сторон коробок по возрастанию. Одинаковые коробки нельзя использовать последовательно, так как разность их сторон меньше 6.
a1⩽a2⩽⋯⩽aN
2. Будем просматривать отсортированный массив слева направо. Первую выбранную коробку включаем в цепочку, а следующую включаем только при выполнении условия размещения.
ai−alast⩾6
3. Для каждой возможной начальной коробки строится цепочка максимальной длины. Среди цепочек с одинаковой длиной выбирается цепочка с наибольшей стороной первой коробки.
a1⩽a2⩽⋯⩽aN
2. Будем просматривать отсортированный массив слева направо. Первую выбранную коробку включаем в цепочку, а следующую включаем только при выполнении условия размещения.
ai−alast⩾6
3. Для каждой возможной начальной коробки строится цепочка максимальной длины. Среди цепочек с одинаковой длиной выбирается цепочка с наибольшей стороной первой коробки.
Частые ошибки
- Используют условие разности не менее 6 как строгое превышение 6.
- Выбирают только первую найденную цепочку максимальной длины и не сравнивают размер самой маленькой коробки.
- Пытаются использовать коробки в исходном порядке, хотя порядок строк входного файла значения не имеет.
Источник: Открытый банк ФИПИ
Похожие задания
26В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA626В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 0C143326В магазине есть N кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на…Коробки и коржи: вложение с заданной разностью · 553F8026В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 584C6A26В магазине для упаковки подарков есть N кубических коробок. Одну коробку можно поместить в другую, если длина…Коробки и коржи: вложение с заданной разностью · 8091A926В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · B1F57A26В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых…Коробки и коржи: вложение с заданной разностью · CBF8FC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.