Задача по теме: "Сортировки"
В магазине для упаковки подарков есть N кубических коробок и М декоративных замочков к ним (М < N). Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом к каждой коробке подбирается подходящий замочек. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 6 единиц меньше длины стороны другой коробки. Замочек подходит к коробке, если маркировка замочка совпадает с длиной стороны коробки. Известно, что коробка, в которой будет находиться подарок, должна быть упакована в синюю коробку. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находятся число N - количество коробок в магазине (натуральное число, не превышающее 10 000) и через пробел число М - количество декоративных замочков в магазине (натуральное число, не превышающее 10 000). В следующих M строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000) и через знак табуляции значения, указанные как маркировки на замочках (все числа натуральные, не превышающие 10 000), каждая пара таких значений - в отдельной строке; в последних N - М строках второе число, соответствующее маркировке замочка, опускается, и числа, соответствующие длинам сторон коробок, идут каждое в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5 4
43 40
40 30
32 43
40 31
31
Пример входного файла приведён для случая пяти коробок и четырёх замочков, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют набор коробок с длинами сторон 30, 40 и 43, или 31, 40 и 43 или 32, 40, и 43 т. е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 31 (поскольку замочка для коробки с длиной 32 в магазине нет.
Типовой пример имеет иллюcтративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение:
Для решения задачи напишем программу на языке Python:
array = [] #создаем массивы для удобства сортировки
A = []
B = []
C = []
D = []
f=open('26var03.txt') #открываем файл
array = f.readlines() #заносим данные файла в массив
N1,N2 = map (int, array[0].split()) #заносим первые 2 значения в переменные N1 и N2
del (array[0])
for i in range(N2):
a, b = map (int, array[i].split()) #заносим в переменные a и b значения по строкам, как они распределены в файле
A.append(a)
B.append(b)
for i in range(N2,N1):
A.append( int(array[i]) ) #заносим значения в массив А
A.sort (reverse=True)
for i in A:
for j in B:
if i == j: C.append(i) #если элементы совпадают, то заносим их в массив С
x = C[0]
D.append(x) #заносим в массив D первый элемент из массива С
for i in C:
if x - i >= 6:
x = i
D.append(x) #проходим по всему массиву С и если есть элементы, меньше или равные 6, то добавляем их в массив D
print(len(D), min(D))
Программа прочитает данные из файла, отсортирует их по убыванию и выведет правильный ответ.
Ответ: 585 227
Сообщение об ошибке
Расскажите, в каком месте допущена ошибка, мы как можно быстрее её исправим. Спасибо за обратную связь!
| МГ | Pro | ProMax | |
| Практика на платформе |  |
|
|
| Отслеживание прогресса обучения | |
|
|
| Двухуровневое домашнее задание после каждого вебинара | |
|
|
| Все материалы составлены экспертом ЕГЭ | |
|
|
| Персональный менеджер | |
|
|
| Личный куратор | |
|
|
| Разбор ошибок личным куратором | |
|
|
| Еженедельные созвоны с куратором для закрытия индивидуальных пробелов | |
||
| Составление индивидуального расписания | |
счёта
средств
подтверждено!
Теперь вы можете приступить
к следующему уроку
курса по математике
замены
Для смены номера телефона
мы отправили Вам код по СМС,
введите его в поле ниже.
Электронная почта
На почту придет чек об оплатеНажимая кнопку "купить", Вы выражаете своё согласие с офертой оказания услуг и принимаете их условия
Здравствуйте!
Выберите информацию о себе ниже
Оплата прошла успешно!
