Решение: Коробки-матрёшки
В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и так далее. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 7 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
В первой строке входного файла находится число $N$ — количество коробок в магазине. В следующих $N$ строках находятся значения длин сторон коробок, каждое — в отдельной строке. Все числа натуральные и не превышают 10 000.
Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
4 шагаСчитаем все размеры коробок и сортируем их по неубыванию. Одинаковые размеры нельзя использовать последовательно, поскольку их разность меньше 7.
Для каждой позиции вычисляем длину максимальной цепочки, которая заканчивается коробкой на этой позиции: рассматриваем предыдущие коробки с размером не больше текущего минус 7.
Для каждой цепочки максимальной длины восстанавливаем размер самой маленькой коробки. Из всех таких цепочек выбираем максимальный размер первой коробки.
В ответ выводим максимальную длину цепочки и максимальный размер её самой маленькой коробки. Конкретные числа зависят от содержимого прилагаемого файла.
Определяется по данным прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать допустимой разность размеров меньше 7.
Использовать каждую коробку несколько раз.
Максимизировать размер самой маленькой коробки, не обеспечив максимальное количество коробок.
Не учитывать несколько коробок одинакового размера как отдельные элементы, если они могут участвовать в разных местах цепочки.