Определите наибольшее количество коробок, которое можно использовать
Условие
В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т. д. Все коробки, которые будут использованы для упаковки подарка, нумеруются с единицы, начиная с той коробки, в которой будет находиться подарок. Одну коробку можно поместить в другую, если они изготовлены из разных материалов, а длина её стороны хотя бы на K + 3000 единиц меньше длины стороны другой коробки, где K — порядковый номер помещаемой коробки. Известны длины сторон и материал коробок, имеющихся в наличии. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка и минимально возможную длину стороны самой большой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку. Входные данныеЗадание 26В первой строке входного файла находится одно число N (N ≤ 1 000 000) — количество коробок. Каждая из следующих N строк содержит два разделённых пробелом натуральных числа, каждое из которых не превышает 1 000 000: длину стороны и условное обозначение вида материала коробки (0 или 1).Запишите в ответе два числа: сначала наибольшее количество коробок, подходящих для упаковки подарка «матрёшкой», затем минимально возможную длину стороны самой большой коробки. Типовой пример организации данных во входном файле643 141 039 038 126 024 1 Пример входного файла приведён для шести коробок.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. ##Приведём решение на языке Python.fd = open('26.txt')N = int(fd.readline()) m = [[], []] # список списков коробок из разных материалов for line in fd: edge, mat = map(int, line.split()) m[mat].append(edge) m[0].sort()m[1].sort()ml = [len(m[0]), len(m[1])] # кол-во коробок 0 и 1 материаловkmax = 0last_edge = float('inf') for t in (0, 1): curr = t # текущий материал коробок pt = [0, 0] # указатели на коробки pack = [m[curr][pt[curr]]] # список длин рёбер коробок в упаковке k = 1 # порядковый номер текущей коробки while pt[0] < ml[0] and pt[1] < ml[1]: curr = (curr +
Осталось ещё 1 шаг
% 2 # Константа изменена на 3000 в…
Бесплатно · займёт минуту