АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

240. Парикмахер

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Неизвестный

Петин папа работает парикмахером. Его парикмахерская совсем небольшая, он — единственный парикмахер, который в ней работает. Парикмахерская открывается в 9:00 и закрывается в 17:00, но папа остаётся на работе, пока не обслужит всех клиентов, которые зашли в парикмахерскую до 17:00.

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

В течение дня каждый момент времени, когда в парикмахерскую заходит очередной клиент, записывается в журнале регистрации. Также в журнале регистрации записывается время, когда последний клиент покидает парикмахерскую. Чтобы оптимизировать вою работу, парикмахер хочет определить, сколько может продолжаться самая долгая стрижка. К сожалению, по указанным записям не всегда можно определить это точно. Поэтому для начала парикмахер хочет определить предельное время стрижки, а именно, какое минимальное время могла продолжаться самая долгая стрижка. Известно также, что любая стрижка занимает не менее пяти минут.

Требуется написать программу, которая по информации о моментах входа в парикмахерскую всех клиентов, а также моменту окончания стрижки последнего клиента, определяет, какое минимальное время могла продолжаться самая долгая стрижка.

Формат входных данных

Первая строка входного файла содержит число n — количество клиентов, обслуженных в рассматриваемый день (1 <= n <= 50). Следующие n строк содержат моменты времени входа клиентов в парикмахерскую в формате hh:mm. Времена заданы в порядке входа клиентов в парикмахерскую и находятся в диапазоне от 09:00 до 17:00. Последняя строка содержит время выхода из парикмахерской последнего клиента также в формате hh:mm. Это время находится в диапазоне от 09:00 до 18:59.

Формат выходных данных

Выведите в выходной файл минимальное возможное время самой долгой стрижки в минутах. Ответ должен отличаться от правильного не более чем на 10-8. Если парикмахер не может обслужить клиентов за указанное время, выведите "-1".

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

stdin

stdout

2

09:00

16:22

17:52

90.0

3

09:00

09:22

09:22

10:11

23.666666666667

1

16:59

17:00

-1

Пояснения к примерам

Покажем, что в первом примере максимальное время стрижки не может быть меньше 90 минут от противного. Пусть любая стрижка продолжалась меньше 90 минут. Известно, что стрижка второго клиента завершилась в 17:52. Поскольку она продолжалась меньше 90 минут, то она началась позже, чем в 16:22. Значит, обслуживание второго клиента началось не сразу, как он пришёл, а после того, как закончилась стрижка первого клиента после 16:22. Но тогда первого клиента стригли больше 7 часов. А мы предполагали, что максимальное время стрижки меньше 90 минут. Пришли к противоречию. А расписание для 90 минут очевидно.

В последнем примере клиент был обслужен за одну минуту, чего не может быть по условию задачи.


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований и сборов / Школьные олимпиады и курсы Вологодской области / ВсОШ, региональные этапы / Областная олимпиада школьников 2005-2006 /
241. Домашние задания 240. 236. Перепутанные диски 237. Разнообразные строки 238. Разрезание торта
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.