Определите наибольшее количество коробок, которое можно использовать
Условие
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные.
Задание 26В первой строке входного файла находится число N — количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе. Пример входного файла:54340324030Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, то есть количество коробок равно 3, а длина стороны самой маленькой коробки равна 32. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Сначала считаем в список boxes данные из файла. После этого отсортируем список в порядке убывания. В список answer сначала поместим самую большую коробку. Далее пройдём по оставшимся коробкам и будем добавлять в список answer очередную коробку, если длина её стороны будет как минимум на 3 единицы меньше последнего элемента списка answer. Приведём решение на языке Python.f = open('26.txt')n = f.readline()boxes = sorted([int(i) for i in f], reverse=True)answer = [boxes[0]]for box in boxes[1:]: if answer[-1] - box >= 3: answer.append(box)print(len(answer), answer[-1]) В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 2767
Осталось ещё 1 шаг
Примечание. Путь к файлу необходимо указать…
Бесплатно · займёт минуту