Задача #4034

Сортировка

Уровень ЕГЭ

(М. Коктышев) В аквапарке посетители могут оставлять вещи в камерах хранения. Камеры хранения бывают двух типов: обычные и холодильные. Обычная камера обозначается цифрой 0, холодильная - цифрой 1. Все камеры пронумерованы натуральными числами начиная с 1.

Для каждой камеры известны её тип и объём. Посетитель может воспользоваться камерой хранения, если тип камеры совпадает с требуемым типом заявки, а объём камеры не меньше объёма его багажа.

В течение суток посетители отправляют заявки на использование камер хранения. В каждой заявке указаны время начала хранения, время окончания хранения, необходимый объём камеры и требуемый тип камеры. Перед обработкой все заявки упорядочиваются по возрастанию времени начала, а при одинаковом времени начала - по возрастанию времени окончания. Если время начала и время окончания у нескольких заявок совпадают, они обрабатываются в том порядке, в котором записаны во входном файле.

Для каждой заявки администратор выбирает свободную подходящую камеру минимального объёма. Если таких камер несколько, выбирается камера с наименьшим номером. Камера считается свободной для нового посетителя только начиная со следующей минуты после окончания предыдущего хранения. Если в момент обработки заявки подходящей свободной камеры нет, посетитель уходит.

Определите, сколько посетителей смогут воспользоваться камерами хранения в течение суток, и номер камеры, которая будет выдана посетителю последней. Если несколько камер были выданы в самое позднее время, укажите наименьший номер такой камеры.

Входные данные

В первой строке входного файла находятся два натуральных числа K и N: K - количество камер хранения, N - количество заявок посетителей. Значения K и N не превышают 10 000.

В следующих K строках находятся по два числа: тип камеры и её объём. Объём камеры - натуральное число, не превышающее 100 000.

В следующих N строках находятся по четыре числа: время начала хранения, время окончания хранения, необходимый объём камеры и требуемый тип камеры. Время указывается в минутах от начала суток и не превышает 1440. Необходимый объём камеры не превышает 100 000.

Выходные данные

Запишите в ответе два натуральных числа: сначала количество посетителей, которые смогут воспользоваться камерами хранения, затем номер камеры, которая будет выдана посетителю последней.

Типовой пример организации данных во входном файле

4 9
0 50
1 60
0 100
1 120
20 40 55 0
10 30 45 0
31 50 55 1
15 25 60 1
41 70 90 0
26 35 50 0
51 80 100 1
36 60 110 1
71 90 40 0

При таких исходных данных камеры хранения смогут получить 7 посетителей. Заявка с временем начала 26 не будет выполнена, так как в этот момент нет свободной обычной камеры подходящего объёма. Заявка с временем начала 51 также не будет выполнена, так как в этот момент нет свободной холодильной камеры подходящего объёма. Последней будет выдана камера №1 для заявки с временем начала 71.

Ответ:
7 1

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файлы к задаче

Скачать 26.txt

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

1989

40

f=open('26_30401.txt')
k,n=map(int,f.readline().split())
tp=[]
vl=[]
for i in range(k):
    t,v=map(int,f.readline().split())
    tp+=[t]
    vl+=[v]
a=[]
for i in range(n):
    x,y,z,t=map(int,f.readline().split())
    a+=[(x,y,i,z,t)]
a.sort()
tm=[0]*k
c=lt=cm=0
for x,y,p,z,t in a:
    bi=-1
    bv=100001
    bn=100001
    for i in range(k):
        if tm[i]<x and tp[i]==t and vl[i]>=z:
            if vl[i]<bv or vl[i]==bv and i+1<bn:
                bi=i
                bv=vl[i]
                bn=i+1
    if bi!=-1:
        tm[bi]=y
        c+=1
        if x>lt:
            lt=x
            cm=bi+1
        elif x==lt and bi+1<cm:
            cm=bi+1
print(c,cm)

Номер