Задача "Лекции"

Маша учится в школе, но безумно любит посещать открытые лекции в МГТУ им. Н.Э. Баумана. Маша старается всегда использовать своё свободное время максимально продуктивно, потому она заранее скачивает расписание преподавателей, чтобы посетить по лекции минимум 50% преподавателей в день, которые она выбрала.

Преподаватели читают одну и ту же лекцию несколько раз в день, в разные промежутки времени. Но у преподавателей есть негласное правило – можно опоздать на лекцию не больше, чем на 5 минут от начала. Можно уйти с лекции на 5 минут раньше.

Но иногда преподаватели разбросаны по расписанию очень сильно, иногда их время пересекается с другими. Поэтому Маше нужна помощь, чтобы по входному расписанию преподавателей определить, во сколько ей нужно быть в университете, чтобы посетить лекции минимум 50% преподавателей (если преподавателей нечётное количество, то округляем вверх (1 округляется до 1, 3 до 2 и так далее), а также провести минимальное количество времени в ожидании между лекциями (если они не подряд).



Входные данные:
На первой строке подаётся целое число N (1 <= N <= 100) – количество преподавателей, на лекции которых хочет сходить Маша.
Далее подаётся N наборов строк в виде:

• на одной строке указывается количество занятий для i-го преподавателя N_i (1 <= N_i <= 50);
• на N_i строках далее указываются временные промежутки занятий преподавателя (без самопересечений) в виде hh:mm-hh:mm (например, 09:10-10:15).

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

• На первой строке выведите, в какое время начнётся первая пара, на которую придёт Маша.
• На второй строке выведите общее количество в минутах, которое Маша проведёт на лекциях.
• На третьей строке выведите общее количество в минутах, которое Маша проведёт между лекциями.

Примечание:

• для удобства расчёта считаем, что путь с одной лекции до другой не занимает времени;
• время лекции у одного преподавателя всегда одинаковое;
• гарантируется, что Маша сможет посетить лекцию минимум 50% преподавателей;
• если задача имеет несколько ответов, то вывести тот, при котором Маша приедет как можно раньше;
• Маша пытается приехать как можно раньше, поэтому, как только она посетит 50% преподавателей, то она может уезжать домой, но приоритетом в задаче является в первую очередь минимальное время проведённое в ожидании между занятиями.

Входные данные
3
2
10:05-11:50
17:00-18:45
1
11:45-12:30
2
13:00-14:00
16:00-17:00

Выходные данные
10:05
145
0


Маше требуется посетить лекции 50% преподавателей, поэтому достаточно посетить 2 преподавателей. Маша пытается найти самое минимальное время для ожидания между занятиями. В данном случае возможны два варианта, когда Маша проведёт между занятиями 0 минут времени:

• посетив лекцию третьего преподавателя 16:00-17:00 и первого 17:00-18:45;
• посетив лекцию первого преподавателя 10:05-11:50 и второго 11:45-12:30.

Так как время ожидания между лекциями одинаковое, то выбираем тот вариант, при котором Маша приедет как можно раньше – 10:05.

0

А вопрос то в чём?

0