Задача #3893

Сортировка

Уровень ЕГЭ

(Д. Караулов) Входной файл содержит информацию о заявках пользователей, обращающихся в компьютерный клуб в течение суток. В заявке указаны время начала и время окончания использования компьютера (в минутах от начала суток).
Компьютеры пронумерованы натуральными числами начиная с 1. Если в момент обращения есть свободные компьютеры, пользователь получает компьютер с минимальным номером. Если свободных компьютеров нет, пользователь покидает клуб и не обслуживается. Компьютер освобождается в момент окончания работы пользователя и становится доступным для следующего клиента начиная со следующей минуты. Также известно, что каждый обслуженный пользователь приносит клубу прибыль — $p r o f i t = t * (t + 1) / / 2$ , где $t$ - время пользования компьютером. Определите количество клиентов, которые были обслужены в компьютерном клубе за сутки, и максимальную суммарную прибыль одного компьютера за сутки.
Входные данные:
В первой строке входного файла находится натуральное число К, не превышающее 1000, - количество компьютеров. Во второй строке натуральное число N (N ≤ 10 000), обозначающее количество заявок. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанные в заявке время начала и время окончания обслуживания (в минутах от начала суток).
Запишите в ответе два числа: количество обслуженных клиентов и максимальную суммарную прибыль одного компьютера.
Типовой пример организации данных
2
5
30 60
40 100
59 60
61 100
101 144
При таких исходных данных воспользоваться услугами компьютерного клуба смогут первый, второй, четвёртый и пятый клиенты. Первый, четвертый и пятый клиенты будут использовать первый компьютер, а четвертый клиент - второй компьютер. Тогда максимальная суммарная прибыль принадлежит первому компьютеру и она составит 2191 рубль.
Типовой пример имеет иллюстративный характер, Для выполнения задания используйте данные из прилагаемых файлов.

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

Скачать 26.txt

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

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

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

Ответ

3775

54798

f=open('26_29234.txt')
K = int(f.readline())
N = int(f.readline())


a=[]
comps = [0]*K
profit=[0]*K
k=0

for s in f:
    st,end = [int(x) for x in s.split()]
    a.append([st,end])

a.sort()

for st,end in a:
    for i in range(K):
        if comps[i]<st:
            comps[i] = end
            k+=1
            t=(end-st)
            profit[i] += (t*(t+1)//2)
            break

print(k,max(profit))

Номер