Задание 26 ЕГЭ: вложенные коробки

Вложенные коробки («матрёшка»). Тема номера — обработка данных и моделирование. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Для упаковки подарков используют коробки разного размера. Коробку можно положить в другую, если её размер меньше размера другой коробки не менее чем на 64 условных единиц. Набор вложенных коробок собирают так, чтобы каждая коробка набора, кроме самой большой, лежала в следующей по размеру коробке набора.

По заданному списку коробок определите наибольшее количество коробок в одном наборе и наибольший возможный размер самой маленькой коробки в наборе из такого количества коробок.

Входные данные. В первой строке входного файла 26.txt записаны два натуральных числа: N — количество коробок и d — наименьшая допустимая разница размеров. В каждой из следующих N строк записано натуральное число — размер очередной коробки.

Запишите в ответе два числа: сначала наибольшее количество коробок в наборе, затем наибольший возможный размер самой маленькой коробки такого набора.

Скачать файл к примеру

Решение

Сортируем размеры по убыванию и жадно собираем набор сверху: самая большая коробка, затем каждый раз самая большая из тех, что меньше последней взятой хотя бы на 64. Так набор получается самым длинным, а каждая коробка в нём — наибольшей из возможных на своём месте; значит, и самая маленькая коробка набора наибольшая.

Ответ: 1161 90.

f = open('26.txt')
n, d = map(int, f.readline().split())
a = sorted((int(f.readline()) for _ in range(n)), reverse=True)
chain = [a[0]]
for x in a[1:]:
    if x <= chain[-1] - d:
        chain.append(x)
print(len(chain), chain[-1])

Решить такую задачу — новый вариант с проверкой