Задание 26. Информатика. ЕГЭ. Шастин. 18.12.2024

(Д. Бахтиев) Николай устроился работать гардеробщиком в крупнейший кинотеатр города. Всего в гардеробе доступно \(M\) мест. При покупке билетов на какой-либо сеанс, они резервируются на уникальный \(ID\) клиента, причём на один \(ID\) может быть зарегистрировано сразу несколько билетов. Каждый посетитель кинотеатра обязан сдать одежду в гардероб, при этом взаимодействовать с Николаем может только клиент, \(ID\) которого использован для покупки билетов. Если посетитель подходит к гардеробу впервые, он сдаёт одежду за себя и всю свою группу и получает столько номерков, за сколько человек одежда была сдана. При повторном визите посетитель забирает свою одежду и одежду своей группы, и номерки становятся свободными. Считается, что одежда развешивается и выдаётся моментально, то есть, если клиент подошёл в минуту \(t\) для получения одежды, то в минуту \(t\) этой одежды в гардеробе уже нет. Если клиент сдал одежду в минуту \(t,\) то всю минуту \(t\) одежда уже висит в гардеробе. Если несколько посетителей подошли в одно время, то они обслуживаются в порядке возрастания их \(ID.\) Если свободных номерков нет или их меньше, чем количество человек, которые хотят сдать одежду, то им отказывается в обслуживании, на что каждый клиент группы один раз злобно топает ножкой и моментально покидает кинотеатр, второй раз при этом они подходить не будут.

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

Примечание: считается, что в момент открытия кинотеатра все места в гардеробе свободны.

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

В первой строке входного файла записаны два числа \(N\) и \(K:\) \(N\) — общее количество мест в гардеробе; \(K\) — количество людей, на чьё имя были куплены билеты в кинотеатр. Далее следуют строки с информацией о посетителях кинотеатра за последние сутки. Каждая строка содержит три числа, разделённых пробелами:\(ID\) — уникальный идентификатор клиента; \(t\) — время подхода клиента к гардеробу в минутах от начала суток; \(M\) — количество билетов, оформленных на текущий \(ID.\) Гарантируется, что каждый идентификатор \(ID\) появляется в данных не более двух раз: первый раз — для сдачи одежды, второй раз — для её получения.

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

\(5 \, 3\)
\(20 \, 15 \,4\)
\(4 \, 5 \, 2\)
\(1996 \, 28 \, 3\)
\(1996 \, 34 \, 3\)
\(20 \, 40 \, 4\)
\(4 \, 50 \, 2\)

Пример входного файла приведён для гардероба, имеющего \(5\) мест, и трёх клиентов. При таких исходных данных клиент с \(ID = 4\) получит \(2\) номерка, клиент с \(ID = 20\) не сможет разместить вещи в гардеробе, поэтому \(4\) посетителя топнут ножкой; клиент с \(ID = 1996\) получит \(3\) номерка и все \(5\) номерков гардероба в момент времени \(t = 28\) будут заняты до тех пор, пока этот же клиент при \(t = 34\) не заберёт вещи. Ответ:\(4 \, 6\)

base = ''

fd = open(base + '26.txt')
N, K = map(int, fd.readline().split())
clients = []

for line in fd:
    ID, t, M = map(int, line.split())
    clients.append((t, ID, M))

clients.sort()
q_top = 0 #кол-во клиентов, топнувших ножкой
full_time = 0 #общее время, когда в гардеробе нет свободных номерков
obizh = set() #мн-во ID обиженных клиентов
sdal = set() #мн-во ID клиентов, сдавших вещи в гардероб
ft = 0  #момент времени, когда в гардеробе не стало свободных номерков
for cl in clients:
    t, ID, M = cl
    if ID in obizh:
        continue
    if ID not in sdal:
        if M <= N:
            sdal.add(ID)
            N -= M
            if N == 0:
                ft = t
        else:
            obizh.add(ID)
            q_top += M
    else:
        if N == 0:
            full_time += t - ft
        N += M
print(q_top, full_time)