РУҚА
26

Упаковка коробок матрёшкой

ЕГЭ · Информатика · Задание 26 · Массивы и строки
ВысокаяФИПИ1F25B2Короткий ответ≈ 10 минут

В магазине для упаковки подарков есть $N$ кубических коробок. Подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и так далее. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 13 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.

Входной файл содержит в первой строке число $N$, а в следующих $N$ строках — длины сторон коробок. Все значения — натуральные числа, не превышающие 10 000. Для выполнения задания используйте данные из прилагаемого файла.

Условие как в банке ФИПИ — открыть и сверить
Впишите правильный ответ.

Задание выполняется с использованием прилагаемых
файлов.

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 13 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

Входные данные

В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000).
В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.

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

Типовой пример организации данных во входном файле

5

43

40

32

40

30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40
и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.



Ваш ответ

Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.

!
3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, когда прочитан предыдущий, — чтобы не перепрыгнуть сразу к ответу.
1Мягкая — с чего смотретьуровень 1 из 3

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

2Наводящая — какие числа считатьуровень 2 из 3

После сортировки поддерживайте максимальную длину цепочки для каждой коробки: следующая коробка должна иметь сторону не менее чем на 13 больше.

3Прямая — фактически решениеуровень 3 из 3

Для каждой длины $a_i$ найдите предыдущую коробку с максимальной длиной цепочки среди всех значений $a_j \leq a_i - 13$. При одинаковой максимальной длине цепочки выберите больший размер самой маленькой коробки.

Всё равно не складывается?Полное решение с обоснованием каждого шага — на отдельной странице.
Открыть решение

Задание 26 ЕГЭ, информатика

Задача из темы «Массивы и строки»: в ней 238 задач с ответом и разбором по шагам. В 26-м номере бланка — 75 задач.

Ответ можно проверить здесь же, а если не выходит — открыть подсказку или разбор. Регистрация не нужна.