Задача к ЕГЭ по информатике на тему «прочие прототипы» №8

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

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

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

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

Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.

Типовой пример организации данных во входном файле

5 4

43 40

31 30

32 43

40 31

30

Пример входного файла приведён для случая пяти коробок и четырёх замочков, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой составляет 3  единицы.

При таких исходных данных условию задачи удовлетворяют набор коробок с длинами сторон 30  , 40  и 43  или 31  , 40  и 43  или 32  , 40  и 43  соответственно, т.е. количество коробок равно 3  , а длина стороны самой маленькой коробки равна 31  (поскольку замочка для коробки с длиной стороны 32  в магазине нет).

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

f = open(’26.txt’)
n, m = map(int, f.readline().split())
length = []
locks = set()
for i in range(m):
    x, y = map(int, f.readline().split())
    length.append(x)
    locks.add(y)
for i in range(n - m):
    x = int(f.readline())
    length.append(x)
length = sorted([i for i in length if i in locks], reverse=True)
ans = 1
x = length[0]
for i in range(1, len(length)):
    if (x - length[i]) >= 6:
        ans += 1
        x = length[i]
print(ans, x)

Ответ: 650 103
Оцените статью
Я решу все!