Решение: Коробки-матрёшки
В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 6 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
Во входном файле в первой строке задано число $N$ — количество коробок. В следующих $N$ строках записаны длины сторон коробок. Запишите сначала наибольшее количество коробок, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Решение по шагам
4 шагаСначала отсортируем все длины сторон коробок по возрастанию. Одинаковые коробки нельзя использовать последовательно, так как разность их сторон меньше 6.
$$a_1 \leqslant a_2 \leqslant \dots \leqslant a_N$$Будем просматривать отсортированный массив слева направо. Первую выбранную коробку включаем в цепочку, а следующую включаем только при выполнении условия размещения.
$$a_i-a_{\text{last}}\geqslant 6$$Для каждой возможной начальной коробки строится цепочка максимальной длины. Среди цепочек с одинаковой длиной выбирается цепочка с наибольшей стороной первой коробки.
Числа из прилагаемого входного файла в условии не представлены, поэтому вычислить конкретную пару значений невозможно.
Конкретный ответ нельзя определить без содержимого прилагаемого входного файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Используют условие разности не менее 6 как строгое превышение 6.
Выбирают только первую найденную цепочку максимальной длины и не сравнивают размер самой маленькой коробки.
Пытаются использовать коробки в исходном порядке, хотя порядок строк входного файла значения не имеет.