Задание 26. Матрёшка: самая длинная цепочка – ЕГЭ по информатике

Что проверяет задание

Задание 26 – файл с данными и два числа в ответе. В этом сюжете данные – размеры коробок: из них собирается цепочка «матрёшка», где каждая следующая коробка меньше предыдущей хотя бы на 9 единиц. Спрашивают длину самой длинной такой цепочки и размер её самой маленькой коробки.

2 балла, норматив 35 минут. Два числа проверяются независимо: одно верное число – 1 балл, оба верных, но переставленных местами, – тоже 1 балл.
Что нужно знать заранее:

чтение файла построчно и int от строки – чтение файлов;
sort с reverse=True и заодно без него: цепочку собирают в двух направлениях;
жадный выбор: каждый раз берём ближайшую подходящую коробку.

Типовой пример

Задача из банка kompege.ru (№ 21910).

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

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

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

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

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон подходящих коробок составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43, то есть количество коробок равно 3, а длина стороны самой маленькой коробки равна 32. Длина у обоих наборов одна, и выбирает между ними вторая половина вопроса – «максимально возможную длину стороны самой маленькой»: в ответ идёт набор, где маленькая коробка крупнее.

Ответ для приведённого примера: 3 32.

Файл с данными: bank-26_21910_26_1.txt – 10 000 строков с размерами коробок и строка с их количеством. Положите его рядом со скриптом, не переименовывая: код ниже открывает bank-26_21910_26_1.txt – то самое имя, под которым файл скачивается.

Как рассуждать

Представьте, что коробки стоят перед вами на столе. Как собрать из них матрёшку подлиннее? Естественно – расставить по размеру и идти от одного края, каждый раз беря следующую коробку, которая подходит. Это и будет решением, осталось понять три вещи:

Как упорядочить коробки – файл перемешан, а цепочка идёт по размеру.
Почему «брать первую подходящую» даёт самую длинную цепочку, а не какую-то случайную.
С какого края идти: снизу вверх или сверху вниз – от этого зависит второе число ответа.

Дальше – по шагу на каждый пункт.

Шаг 1. Читаем и сортируем

Первая строка файла – количество коробок N, а не размер коробки. Её читаем отдельно через readline, и цикл for line in f продолжает уже со второй строки: в список sides попадают только размеры.

Порядок в файле ничего не значит – сортируем. В примере из условия числа стоят 43, 40, 32, 40, 30. Сортируем по убыванию, reverse=True.

with open('bank-26_21910_26_1.txt') as f:
    n = int(f.readline())                # первая строка – количество, не коробка
    sides = []
    for line in f:
        sides.append(int(line))
sides.sort(reverse=True)                 # от самой большой к самой маленькой

Шаг 2. Собираем цепочку

Самая большая коробка – первая в списке, с неё цепочка и начинается: chain = [sides[0]]. Дальше идём по остальным коробкам, от больших к маленьким, и каждую сравниваем с последней взятой, chain[-1]. Если разница достаточная – коробка помещается внутрь, добавляем её в цепочку. Если нет – пропускаем: следующие коробки ещё меньше, и какая-то из них подойдёт.

Почему жадность, а не перебор. Брать в цепочку ближайшую подходящую коробку никогда не хуже, чем любую другую: она оставляет больше места для следующих.

«Хотя бы на 9 единиц меньше» – это >= d. Разница ровно в 9 единиц допустима, строгое > теряет часть коробок. «Хотя бы на d» и «более чем на d» – разные задачи, и различаются они одним знаком.

Вот как это выглядит на примере из условия, где d = 3:

Коробка	Последняя в цепочке	Разница	Берём?
43	–	–	начало цепочки
40	43	3	да, 3 не меньше 3
40	40	0	нет, 0 меньше 3
32	40	8	да, 8 не меньше 3
30	32	2	нет, 2 меньше 3

Подсвечены коробки, вошедшие в цепочку: 43, 40, 32.

d = 9
chain = [sides[0]]                       # начинаем с самой большой коробки
for x in sides[1:]:
    if chain[-1] - x >= d:               # помещается в последнюю взятую
        chain.append(x)

Шаг 3. Почему сверху вниз

Цепочку можно собирать и с другого края: снизу вверх, от самой маленькой коробки, каждый раз беря самую маленькую подходящую. Количество коробок выйдет то же самое. Но самая маленькая коробка в такой цепочке – просто самая маленькая в файле, а спрашивают «максимально возможную длину стороны самой маленькой».

Сверху вниз каждый элемент цепочки получается максимально большим из возможных – значит, и последний, самый маленький. Поэтому один проход сверху вниз отвечает сразу на оба вопроса: len(chain) – сколько коробок, chain[-1] – самая маленькая из них.

На примере это видно сразу. Сверху вниз цепочка – 43, 40, 32, снизу вверх – 43, 40, 30. Коробок столько же, 3, а самая маленькая – 32 против 30.

print(len(chain), chain[-1])             # 1040 57

Программа целиком

Три шага подряд – это и есть решение. Перед запуском на файле прогоните его на примере из условия: сохраните пример в отдельный файл, подставьте это имя в open и поменяйте d = 9 на d = 3 – в примере разница своя. Должно выйти 3 32.

Решение

with open('bank-26_21910_26_1.txt') as f:
    n = int(f.readline())                # первая строка – количество, не коробка
    sides = []
    for line in f:
        sides.append(int(line))
sides.sort(reverse=True)                 # от самой большой к самой маленькой

d = 9
chain = [sides[0]]                       # начинаем с самой большой коробки
for x in sides[1:]:
    if chain[-1] - x >= d:               # помещается в последнюю взятую
        chain.append(x)

print(len(chain), chain[-1])             # 1040 57

Если спрашивают другое

Сюжет один, и проход один – меняется то, что спрашивают, а вместе с вопросом направление прохода и последняя строка.

Что в условии	Что править
«многоярусный торт, корж на d единиц меньше»	тот же сюжет, меняется только `d`
«наименьший возможный размер самой маленькой коробки»	это просто `min(sides)`: цепочку снизу всегда можно закончить самой маленькой коробкой
«наибольший возможный размер самой большой коробки при наибольшем количестве»	это просто `max(sides)`: цепочку сверху всегда можно начать с самой большой коробки
«разница не меньше d» / «разница больше d»	`>= d` / `> d` – читать условие дословно

Во всех вариантах первым делом прогоните программу на примере из условия.

Типичные ошибки

Строгое сравнение. chain[-1] - x > d вместо >= d – и разница ровно в 9 единиц перестаёт считаться подходящей: 935 коробок вместо 1040. Слова «хотя бы на 9» означают «не меньше», то есть 9 тоже можно.
Набрали цепочку снизу вверх и взяли её первый элемент. Второе число – не «самая маленькая из подходящих», а «максимально возможная длина стороны самой маленькой коробки в наборе наибольшей длины». Проход снизу вверх даёт те же 1040 коробок, но самая маленькая в нём – 50 вместо 57: первое число сошлось, второе нет, и один балл из двух потерян на выборе направления.
Прочитали первую строку как коробку. В первой строке файла стоит количество коробок, а не размер. Если скормить её тому же списку, коробок станет на одну больше – 1041 вместо 1040. Ошибка на единицу, которую глазами не поймать: строка выглядит как обычное число в столбце чисел.