В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т. д. Все коробки, которые будут использованы для упаковки подарка, нумеруются с единицы, начиная с той коробки, в которой будет находиться подарок. Одну коробку можно поместить в другую, если они изготовлены из разных материалов, а длина её стороны хотя бы на K + 3000 единиц меньше длины стороны другой коробки, где K — порядковый номер помещаемой коробки. Известны длины сторон и материал коробок, имеющихся в наличии. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка и минимально возможную длину стороны самой большой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится одно число N (N ≤ 1 000 000) — количество коробок. Каждая из следующих N строк содержит два разделённых пробелом натуральных числа, каждое из которых не превышает 1 000 000: длину стороны и условное обозначение вида материала коробки (0 или 1).
Запишите в ответе два числа: сначала наибольшее количество коробок, подходящих для упаковки подарка «матрёшкой», затем минимально возможную длину стороны самой большой коробки.
Типовой пример организации данных во входном файле
6
43 1
41 0
39 0
38 1
26 0
24 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 = 0
last_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 в соответствии с условием задачи.
# k — это номер уже лежащей в pack коробки, которая помещается в новую.
while pt[curr] < ml[curr] and m[curr][pt[curr]] - pack[-1] < 3000 + k:
pt[curr] += 1
if pt[curr] < ml[curr]:
pack.append(m[curr][pt[curr]])
k += 1
if kmax < k:
kmax = k
last_edge = pack[-1]
elif kmax == k:
last_edge = min(last_edge, pack[-1])
print(kmax, last_edge)
Ответ: 2300 9996036.