В магазине для упаковки подарков есть кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число – количество коробок в магазине (натуральное число, не превышающее ). В следующих строках находятся значения длин сторон коробок (все числа натуральные, не превышающие ), каждое – в отдельной строке. Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет единицы. При таких исходных данных условию задачи удовлетворяют наборы
коробок с длинами сторон , и или , и соответственно, т.е. количество коробок равно , а длина стороны самой маленькой коробки равна .
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файл с данными
Решение:
Python
file_name = open('26-1.txt')
nums_count = int(file_name.readline())
nums = list(map(int, file_name.readlines()))
nums.sort(reverse=True)
box_count = 1
last_box = 0
last_size = nums[0]
for idx in range(1, nums_count):
if nums[last_box] - nums[idx] > 2:
last_box = idx
last_size = nums[idx]
box_count += 1
print(box_count, last_size)
Ответ: