Задача к ЕГЭ по информатике на тему «прочие прототипы» №5

В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $3$ единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

Входные данные

В первой строке входного файла находится число $N$ – количество коробок в магазине (натуральное число, не превышающее $10000$ ). В следующих $N$ строках находятся значения длин сторон коробок (все числа натуральные, не превышающие $10000$ ), каждое – в отдельной строке. Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.

Типовой пример организации данных во входном файле

$5$

$21$

$19$

$13$

$31$

$40$

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет $3$ единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон $40,31,21$ и $13$ или $40,31,19$ и $13$ соответственно, т.е. количество коробок равно $4$ , а длина стороны самой маленькой коробки равна $13$ .

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Перенесем числовые значение количества коробок в магазине куда-нибудь, где оно нам не помешает. Сортируем числа столбца $A$ по убыванию. Выделим полностью столбец $A$ , перейдём в раздел Данные и нажимаем на инструмент Удалить дубликаты, в появившемся окне выбираем Выделить все и нажимаем ОК (это удалит коробки, которые были по записаны несколько раз). Запишем для первых ячеек максимальный размер подарка, который закончится на данной коробке. В ячейку $B4$ запишем формулу =МАКС(ЕСЛИ(A3-A4>=3;B3+1;1);ЕСЛИ(A2-A4>=3;B2+1;1);ЕСЛИ(A1-A4>=3;B1+1;1)), скопируем её на все свободные клеточки этого столбца. Находим маскимальное значение в столбце $B$ . Выписываем в ответ наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.

Решение 2 (Python)

f = open(’Задание 26.txt’)
n = int(f.readline())
a=[int(x) for x in f.readlines()]
a.sort(reverse=True)
gift = [a[0]]
for i in range(n):
    if gift[-1] - a[i] >= 3:
        gift.append(a[i])
print(len(gift), gift[-1])

Ответ: 2787 51