Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

26. Прикладная задача: Входной файл содержит информацию о заявках граждан, обращающихся во…

Задание #298065
Решено верно
Решено неверно
Сообщить о проблеме

Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток). Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с $1$. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение $24$ ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.

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

В первой строке входного файла находится натуральное число $K$, не превышающее $1000$, – количество окон в МФЦ. Во второй строке – натуральное число $N$ ($N \le 10000$), обозначающее количество граждан. Каждая из следующих $N$ строк содержит два натуральных числа, каждое из которых не превышает $1440$: указанные в заявке время начала и время окончания приёма (в минутах от начала суток).

Запишите в ответе два числа: количество граждан, которые смогут воспользоваться услугами МФЦ, и номер окна, в котором специалист примет последнего гражданина.

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

2
5
30 60
40 100
59 60
61 100
101 144

При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, – $1$, так как будут свободны окна $1$ и $2$.

Заявки в файле лежат вперемешку, поэтому сначала сортируем их по времени начала приёма — обслуживать граждан надо в порядке обращения. Для каждого окна храним одно число: момент, когда специалист освободится. Гражданин с временем обращения $t$ может попасть в окно, если это число меньше $t$ — так реализуется правило «начиная со следующей минуты после завершения приёма предыдущего».

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

f = open('26-17.txt')
K = int(f.readline())
N = int(f.readline())
req = [tuple(map(int, f.readline().split())) for _ in range(N)]
req.sort()                                # по времени обращения

free = [0] * K                            # время, когда окно освободится
cnt = 0
last_t, last_win = -1, None

for t, e in req:
    for i in range(K):
        if free[i] < t:                   # свободно со следующей минуты
            free[i] = e
            cnt += 1
            if t > last_t:
                last_t, last_win = t, i + 1
            elif t == last_t and i + 1 < last_win:
                last_win = i + 1
            break

print(cnt, last_win)   # 793 2

Проверка. Окон $267$, заявок $994$, на приём попали $793$ гражданина. Последнее обращение среди них произошло на $1437$-й минуте, и такой гражданин был один — его принял специалист в окне $2$. На типовом примере из условия программа выдаёт $4$ и $1$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение