26.09 Прочие прототипы
Ошибка.
Попробуйте повторить позже
В магазине для упаковки подарков есть 
кубических коробок и 
декоративных замочков к ним 
Самой
интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою
очередь в другую коробку и т. д., при этом к каждой коробке подбирается подходящий замочек. Одну коробку можно
поместить в другую, если длина её стороны хотя бы на 
единиц меньше длины стороны другой коробки. Замочек
подходит к коробке, если маркировка замочка совпадает с длиной стороны коробки. Определите наибольшее количество
коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой
маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую
коробку.
Входные данные
В первой строке входного файла находятся число 
- количество коробок в магазине (натуральное число, не
превышающее 
) и через пробел число 
- количество декоративных замочков в магазине (натуральное число, не
превышающее 
).
В следующих 
строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 
) и через знак табуляции значения, указанные как маркировки на замочках (все числа натуральные, не превышающие
), каждая пара таких значений - в отдельной строке; в последних 
строках второе число, соответствующее
маркировке замочка, опускается, и числа, соответствующие длинам сторон коробок, идут каждое в отдельной
строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
Пример входного файла приведён для случая пяти коробок и четырёх замочков, когда минимальная
допустимая разница между длинами сторон коробок, подходящих для упаковки "матрёшкой составляет 
единицы.
При таких исходных данных условию задачи удовлетворяют набор коробок с длинами сторон 
, 
и 
или 
, 
и 
или 
, 
и 
соответственно, т.е. количество коробок равно 
, а длина стороны
самой маленькой коробки равна 
(поскольку замочка для коробки с длиной стороны 
в магазине
нет).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
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)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
