Задача I. Регистрация участников
Задачу добавил: alef
Успешно сдано решений: 24
Поскольку каждому участнику чемпионата выдается сертификат, очень важно сверить его данные с теми, которые были заявлены при предварительной регистрации. Поэтому, когда участник приходит на чемпионат, сначала он должен подойти к студентам-волонтерам, которые выполнят эту сверку (и, разумеется, отметят, что участник прибыл), и уже затем отправиться в аудиторию, где проводится организационное собрание.
Волонтеру, стоящему с плакатом «Студенческий командный чемпионат по программированию» было немного скучно, и он стал записывать время (с точностью до секунды) прихода участников в университет и их ухода после сверки данных на организационное собрание. Фамилий участников волонтер не знал, и поэтому записи выглядели как время (в формате ЧЧ:ММ:СС), после которого стоит знак «+», если в этот момент участник вошел в университет, и «-», если он отправился на организационное собрание.
Сверку данных проводят N студентов-волонтеров. Пришедший участник направляется к любому свободному в данный момент волонтеру; если же все они заняты, то ожидает, пока кто-нибудь из них освободится.
Когда регистрация завершилась, скучавший с плакатом волонтер захотел определить, каково было максимальное время ожидания участником своей очереди при сверке данных. Ваша задача — вычислить это время.
Считайте, что все участники приходили в университет и уходили на организационное собрание в разное время.
Формат входного файла input.txt
Первая строка — целые числа K (1 <= K <= 200) и N (1 <= N <= 20) через пробел — количество участников чемпионата и количество студентов-волонтеров соответственно.
В каждой из следующих строк записано время в формате ЧЧ:ММ:СС и через пробел знак «+» или «—» — в зависимости от того, вошел ли участник в университет или отправился на организационное собрание.
Времена записаны в порядке возрастания.
Формат выходного файла output.txt
Первая строка — максимально возможное время ожидания участником своей очереди на сверку данных в формате ЧЧ:ММ:СС
Пример входного файла — 1
2 1
09:00:54 +
09:02:30 +
09:06:12 –
09:09:00 -
Пример выходного файла — 1
00:03:42
Пример входного файла — 2
2 1
09:00:54 +
09:02:30 -
09:06:12 +
09:09:00 -
Пример выходного файла — 2
00:00:00