Решение: Упаковка коробок-матрёшек
В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и так далее. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 11 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
В первой строке входного файла находится число $N$ — количество коробок в магазине, не превышающее 10 000. В следующих $N$ строках находятся значения длин сторон коробок, каждое в отдельной строке. Все числа натуральные и не превышают 10 000.
Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
5 шаговСчитаем размеры коробок из файла и сортируем их по возрастанию. Одинаковые размеры сохраняем, поскольку коробки являются отдельными предметами.
$$a_1 \leq a_2 \leq \dots \leq a_N$$Для фиксированной самой маленькой коробки последовательно выбираем первую подходящую коробку справа: её сторона должна быть не меньше предыдущей стороны плюс 11.
$$a_j - a_i \geq 11$$Жадный выбор самой ранней подходящей коробки оставляет максимально возможный запас для продолжения цепочки, поэтому даёт максимальную длину цепочки для выбранной первой коробки.
$$next \geq current + 11$$Перебираем все возможные начальные коробки и сравниваем полученные длины цепочек. Если длина совпадает, сохраняем большую сторону начальной коробки.
После обработки файла выводим максимальное количество коробок и максимальный размер самой маленькой коробки через пробел.
Два целых числа: максимальная длина цепочки и максимальный размер её первой коробки.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать, что разность размеров должна быть ровно 11, хотя она должна быть не меньше 11.
Удалять повторяющиеся размеры коробок.
При одинаковой длине цепочки выбирать меньшую первую коробку.
Выводить размеры коробок вместо количества коробок и размера самой маленькой коробки.