Задание 26 ЕГЭ по информатике · 8091A9
Коробки и коржи: вложение с заданной разностьюВысокаяКЭС 3.10
В магазине для упаковки подарков есть N кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
В первой строке входного файла находится число N — количество коробок в магазине, не превышающее 10 000. В следующих N строках находятся значения длин сторон коробок, каждое — в отдельной строке. Все числа натуральные и не превышают 10 000.
1_8091A9.zipВ первой строке входного файла находится число N — количество коробок в магазине, не превышающее 10 000. В следующих N строках находятся значения длин сторон коробок, каждое — в отдельной строке. Все числа натуральные и не превышают 10 000.
Показать ответ
1040 57
Подсказки (3)
- Как изменится задача, если упорядочить длины сторон коробок по возрастанию?
- Для каждой коробки найдите максимальное количество коробок в цепочке, начинающейся с неё. Следующая коробка должна иметь сторону не меньше текущей плюс 9.
- Отсортируйте массив. Для каждого элемента справа налево вычислите длину цепочки через ближайший элемент со значением не меньше ai+9. Среди цепочек максимальной длины выберите ту, у которой первый элемент имеет наибольшее значение.
Решение
1. Сортируем длины сторон коробок по возрастанию. В цепочке коробки идут в порядке возрастания, а разность между соседними сторонами должна быть не меньше 9.
aiₖ₊₁≥aiₖ+9
2. Для каждого элемента массива справа налево вычисляем максимальную длину цепочки, начинающейся с него. Если следующего подходящего элемента нет, длина цепочки равна 1; иначе к длине цепочки после следующего элемента прибавляем 1.
dpi=1+dpj,j=min{k>i∣ak≥ai+9}
3. Находим максимальное значение dpi. Среди всех элементов, для которых достигается эта длина, выбираем наибольшее значение ai — это максимально возможная длина стороны самой маленькой коробки.
4. В ответ записываем найденную максимальную длину цепочки и выбранное значение её первого элемента. Численные значения зависят от содержимого прилагаемого входного файла, которое в условии не представлено.
aiₖ₊₁≥aiₖ+9
2. Для каждого элемента массива справа налево вычисляем максимальную длину цепочки, начинающейся с него. Если следующего подходящего элемента нет, длина цепочки равна 1; иначе к длине цепочки после следующего элемента прибавляем 1.
dpi=1+dpj,j=min{k>i∣ak≥ai+9}
3. Находим максимальное значение dpi. Среди всех элементов, для которых достигается эта длина, выбираем наибольшее значение ai — это максимально возможная длина стороны самой маленькой коробки.
4. В ответ записываем найденную максимальную длину цепочки и выбранное значение её первого элемента. Численные значения зависят от содержимого прилагаемого входного файла, которое в условии не представлено.
Частые ошибки
- Считать достаточной разность ровно больше 9 вместо разности не меньше 9.
- Максимизировать только количество коробок и не выбирать среди таких цепочек максимальную сторону самой маленькой коробки.
- Использовать каждую коробку более одного раза.
- Принять типовой пример из условия за реальные данные прилагаемого файла.
Источник: Открытый банк ФИПИ
Похожие задания
26В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 0C143326В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 38235A26В магазине есть N кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на…Коробки и коржи: вложение с заданной разностью · 553F8026В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 584C6A26В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · B1F57A26В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых…Коробки и коржи: вложение с заданной разностью · CBF8FC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.