Задание 26 ЕГЭ по информатике · 0C1433

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

1. Считаем все размеры коробок и сортируем их по неубыванию. Одинаковые размеры нельзя использовать последовательно, поскольку их разность меньше 7.

2. Для каждой позиции вычисляем длину максимальной цепочки, которая заканчивается коробкой на этой позиции: рассматриваем предыдущие коробки с размером не больше текущего минус 7.

3. Для каждой цепочки максимальной длины восстанавливаем размер самой маленькой коробки. Из всех таких цепочек выбираем максимальный размер первой коробки.

4. В ответ выводим максимальную длину цепочки и максимальный размер её самой маленькой коробки. Конкретные числа зависят от содержимого прилагаемого файла.