В магазине для упаковки подарков есть N кубических коробок красного цвета и M кубических коробок зеленого цвета 
Самой интересной считается упаковка подарка по принципу матрешки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом цвет коробок чередуется. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 5 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные:
В первой строке входного файла находятся число N — количество коробок красного цвета в магазине (натуральное число, не превышающее 10 000) и через пробел число M — количество коробок зеленого цвета в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок красного цвета (все числа натуральные, не превышающие 10 000) и через знак табуляции значения длин сторон коробок зеленого цвета (все числа натуральные, не превышающие 10 000 ), каждая пара таких значений в отдельной строке; в последних
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле:
5 4
39 55
40 42
44 44
40 55
50
Пример входного файла приведён для случая пяти коробок красного цвета и четырёх коробок синего цвета, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы. При таких исходных данных ответом будет являться 4, 40.
Ответ:
Приведём решение на языке Python.
f = open("2681493.txt")
n, m = map(int, f.readline().split())
boxes = []
for i in range(m):
red_box, green_box = map(int, f.readline().split())
boxes.append([red_box, 'red'])
boxes.append([green_box, 'green'])
for i in range(n-m):
red_box = int(f.readline())
boxes.append([red_box, 'red'])
boxes.sort(reverse=True)
present = [boxes[0]]
for box in boxes:
if present[-1][0] - box[0] >= 5:
if present[-1][1] != box[1]:
present.append(box)
print(len(present), present[-1][0])
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 1770 4.
Ответ: 1770 4.
Приведём решение Юрия Красильникова на языке Python.
f=open('2681493.txt')
f.readline()
boxes=[]
for s in f:
x=list(map(int,s.split()))
boxes.append((x[0],'R'))
if len(x)>1: boxes.append((x[1],'G'))
boxes.sort(key=lambda x: x[0], reverse=True)
matr=[boxes[0]]
for b in boxes:
if b[1]!=matr[-1][1] and matr[-1][0]-b[0]>=5: matr.append(b)
print(len(matr),matr[-1][0])