Решение: Упаковка коробок-матрёшек
В магазине для упаковки подарков есть $N$ кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
В первой строке входного файла находится число $N$ — количество коробок в магазине, не превышающее 10 000. В следующих $N$ строках находятся значения длин сторон коробок, каждое — в отдельной строке. Все числа натуральные и не превышают 10 000.
Решение по шагам
4 шагаСортируем длины сторон коробок по возрастанию. В цепочке коробки идут в порядке возрастания, а разность между соседними сторонами должна быть не меньше 9.
$$a_{i_{k+1}} \geq a_{i_k}+9$$Для каждого элемента массива справа налево вычисляем максимальную длину цепочки, начинающейся с него. Если следующего подходящего элемента нет, длина цепочки равна 1; иначе к длине цепочки после следующего элемента прибавляем 1.
$$dp_i = 1 + dp_j,\quad j=\min\{k>i\mid a_k\geq a_i+9\}$$Находим максимальное значение $dp_i$. Среди всех элементов, для которых достигается эта длина, выбираем наибольшее значение $a_i$ — это максимально возможная длина стороны самой маленькой коробки.
В ответ записываем найденную максимальную длину цепочки и выбранное значение её первого элемента. Численные значения зависят от содержимого прилагаемого входного файла, которое в условии не представлено.
Определяется по прилагаемому входному файлу: количество коробок и максимальная сторона самой маленькой коробки.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать достаточной разность ровно больше 9 вместо разности не меньше 9.
Максимизировать только количество коробок и не выбирать среди таких цепочек максимальную сторону самой маленькой коробки.
Использовать каждую коробку более одного раза.
Принять типовой пример из условия за реальные данные прилагаемого файла.