Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача I. Час пик

Задачу добавил: alef

Успешно сдано решений: 7

А робот явно быстрее теперь мембрану складывает, – обратил внимание Кеша, когда они с Михаилом вернулись к монитору Виктора. – Программа уже поменялась?

— Нет, час пик наступил, – улыбнулся Виктор.

— Час пик? – удивился Кеша

— Ну да, время, когда институтские компьютеры максимально загружены. Так что расчеты по Глобальному Проекту приостанавливаются.

В проектно-исследовательском институте пространства в каждой лаборатории есть несколько довольно мощных компьютеров. Все компьютеры связаны в локальную вычислительную сеть. На каждом компьютере ведутся расчеты проектов, выполняемых лабораторией. Кроме этого, все компьютеры задействованы в расчетах по Глобальному Проекту. До недавнего времени эти расчеты велись круглосуточно. Однако сотрудники постоянно жаловались, что расчеты по Глобальному Проекту очень сильно влияют на скорость расчетов по другим проектам. Поэтому руководство института приняло решение – приостанавливать расчеты по Глобальному Проекту в то время, когда максимальное количество институтских компьютеров загружено другими задачами. Для этого каждый заведующий лабораторией составляет график суточной загрузки компьютеров лаборатории. После этого вычисляются временные отрезки, в течение которых расчеты ведутся на максимальном (в данные сутки) количестве компьютеров. Именно в это время расчеты по Глобальному Проекту и должны быть приостановлены.

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

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

Формат входного файла input.txt

Первая строка – целое число L (1 <= L <= 1000) – количество лабораторий в институте

Вторая строка содержит числа N1, N2, …, NL (1 <= NJ <= 1000, J = 1, 2, …, L) – количество компьютеров в каждой из лабораторий.

В каждой из следующих строк (а всего их будет N1 + N2 + … + NL) содержится информация о суточной загрузке очередного компьютера в следующем формате. Сначала в строке записано целое число Q (1 <= Q <= 10) – количество временных отрезков, в течение которых соответствующий компьютер будет занят расчетами по проектам. Затем следует Q пар вида <чч1>:<мм1> <пробел> <чч2>:<мм2>, обозначающих начало и конец расчетов. Часы и минуты всегда записываются двумя цифрами (при необходимости в записи присутствует ведущий ноль). Гарантируется, что время, указывающее начало расчета, всегда меньше времени конца расчетов. Все времена находятся в диапазоне от 00:00 и до 23:59. Пары также отделены друг от друга пробелами.

Формат выходного файла output.txt

Первая строка – целое число K – количество временных отрезков, на которых расчеты по Глобальному Проекту будут приостановлены.

Вторая строка – K пар вида <чч1>:<мм1> <пробел> <чч2>:<мм2>, также разделенные пробелом. Каждая из пар описывает начало и конец временного отрезка, на котором расчеты приостанавливаются.

Пример входного файла

2
2 1
2 00:17 00:23 20:09 20:46
2 10:03 21:03 21:27 21:33
1 00:20 04:11

Пример выходного файла

2
00:20 00:23 20:09 20:46

Сдать задачу

Задать вопрос жюри по этой задаче