Определите наибольшее количество коробок, которое можно использовать
Условие
В магазине для упаковки подарков есть N кубических коробок красного цвета и M кубических коробок зеленого цвета Самой интересной считается упаковка подарка по принципу матрешки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом цвет коробок чередуется. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 5 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.Входные данные: Задание 26В первой строке входного файла находятся число N — количество коробок красного цвета в магазине (натуральное число, не превышающее 10 000) и через пробел число M — количество коробок зеленого цвета в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок красного цвета (все числа натуральные, не превышающие 10 000) и через знак табуляции значения длин сторон коробок зеленого цвета (все числа натуральные, не превышающие 10 000 ), каждая пара таких значений в отдельной строке; в последних N - M строках второе число опускается, и числа, соответствующие длинам сторон коробок красного цвета, идут каждое в отдельной строке.Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.Типовой пример организации данных во входном файле:5 439 5540 4244 4440 5550Пример входного файла приведён для случая пяти коробок красного цвета и четырёх коробок синего цвета, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы. При таких исходных данных ответом будет являться 4, 40. Ответ:
Ответ
17704
Решение по шагам
Как рассуждать
Решение. Приведём решение на языке 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
Осталось ещё 1 шаг — откроются после входа:
- Шаг 2
Бесплатно · займёт минуту