Задача по теме: "Сортировки"
В магазине для упаковки подарков есть N кубических коробок красного, зелёного и синего цвета. Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом цвета коробок отличаются. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 7 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N - количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000) и через пробел цвет коробки (буква R, G или B).
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5 4
39 55
40 42
44 44
40 55
50
Пример входного файла приведён для случая пяти коробок красного цвета и четырех коробок синего цвета, когда допустимая разница между длинами сторон коробок, подходящих для упаковки "матрешкой", составляет 3 единицы. При таких исходных данных условию задачи удовлетворяет набор коробок с длинами сторон 39, 42, 50 и 55 или 40, 44, 50 и 55 соответственно, то есть количество коробок равно 4, а длина стороны самой маленькой коробки 40.
Типовой пример имеет иллюcтративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение:
Для решения задачи напишем программу на языке Python:
array = [] #создаем массивы для удобства сортировки
A = []
B = []
C = []
f=open('26var04.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)
B.sort (reverse=True)
def f1(b): #функция, которая возвращает значение из массива А, если оно отличается на 5 или больше
for a in A:
if b - a >= 5:
C.append(a)
return f2(a)
def f2 (a):
for b in B: #функция, которая возвращает значение из массива B, если оно отличается на 5 или больше
if a - b >= 5:
C.append(b)
return f1(b)
x = max(A[0], B[0]) #выбираем максимальный элемент из первых двух элементов в массивах A и B и добавляем его в массив С
C.append(x)
if x in B:
f1(x)
else:
f2(x)
print(len(C), min(C))
Программа прочитает данные из файла, отсортирует их по убыванию и выведет правильный ответ.
Ответ: 536 306
Сообщение об ошибке
Расскажите, в каком месте допущена ошибка, мы как можно быстрее её исправим. Спасибо за обратную связь!
| МГ | Pro | ProMax | |
| Практика на платформе |  |
|
|
| Отслеживание прогресса обучения | |
|
|
| Двухуровневое домашнее задание после каждого вебинара | |
|
|
| Все материалы составлены экспертом ЕГЭ | |
|
|
| Персональный менеджер | |
|
|
| Личный куратор | |
|
|
| Разбор ошибок личным куратором | |
|
|
| Еженедельные созвоны с куратором для закрытия индивидуальных пробелов | |
||
| Составление индивидуального расписания | |
счёта
средств
подтверждено!
Теперь вы можете приступить
к следующему уроку
курса по математике
замены
Для смены номера телефона
мы отправили Вам код по СМС,
введите его в поле ниже.
Электронная почта
На почту придет чек об оплатеНажимая кнопку "купить", Вы выражаете своё согласие с офертой оказания услуг и принимаете их условия
Здравствуйте!
Выберите информацию о себе ниже
Оплата прошла успешно!
