Задание 26 ЕГЭ информатика: № 26014. Типовые варианты

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

Входные данные

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

Типовой пример организации данных во входном файле
5             4
39          55
40          42
44          44
40          55
50

Пример входного файла приведён для пяти коробок красного цвета и четырёх коробок синего цвета, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 39, 42, 50 и 55 или 40, 44, 50 и 55 соответственно, т.е. количество коробок равно 4, а длина стороны самой маленькой коробки равна 40.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

2614.txt 19,7 КБ

with open('2614.txt') as file:
    N, M = map(int, file.readline().split())
    boxes = []
    for line in file:
        line = line.split()
        if len(line) == 2:
            boxes.append((int(line[0]), 'red'))
            boxes.append((int(line[1]), 'blue'))
        else:
            boxes.append((int(line[0]), 'red'))

boxes.sort(reverse=True)
start_red = [max(boxes, key=lambda x: x[1] == 'red')]
start_blue = [max(boxes, key=lambda x: x[1] == 'blue')]

for box in boxes:
    if start_red[-1][1] != box[1] and start_red[-1][0] - box[0] >= 5:
        start_red.append(box)
    if start_blue[-1][1] != box[1] and start_blue[-1][0] - box[0] >= 5:
        start_blue.append(box)

ans = max(start_red, start_blue, key=len)
print(len(ans), ans[-1][0])

Рекомендуемые статьи