Задача C. Машинное время
Задачу добавил: alef
Успешно сдано решений: 0
Как заведующий вычислительным центром, Саша Привалов получал от сотрудников НИИЧАВО большое количество расчетных заданий. Конечно, проще всего было бы ставить эти задания в очередь на выполнение по мере их поступления. Однако в этом случае может случиться, например, так, что долгое время местный суперкомпьютер «Алдан» будет решать задачи только сотрудников одного отдела, и сотрудники других отделов (а, главное, начальники отделов) будут огорчены. Поэтому очень желательно, чтобы в течение рабочего дня была решена хотя бы одlfна задача для каждого отдела. Конечно, выполнить это требование можно не всегда – тем более, что заведующий ВЦ не знает заранее, когда именно принесут то или иное задание. И потому – при прочих равных – выбирает для постановки на выполнение то задание, которое на данный момент является самым коротким – т.е. требует наименьшего времени выполнения. Если задание выполняется, прервать его нельзя. Заметим также, что суперкомпьютер не должен простаивать – как только закончилось выполнение одного задания, должно начаться выполнение другого. Ваша задача состоит в том, чтобы по данным о расчетных заданиях установить, во-первых, для каждого ли отдела в течение рабочего дня была решена хотя бы одна задача (если нет – то сколько отделов оказались обделены машинным временем) и, во-вторых, сколько задач в целом было решено в течение рабочего дня. Заметим также, что если от отдела в течение рабочего дня не поступало расчетных заданий, то его не следует считать обделенным машинным временем.
Формат входного файла input.txt
Первая строка содержит целое число N (1<=N<=10) – количество отделов в НИИЧАВО и через пробел две записи в формате HH:MM – начало и конец рабочего дня соответственно (00<=HH<=23, 00<=MM<=59). Гарантируется, что промежуток между началом и концом рабочего дня составляет не более суток, и что начало рабочего дня всегда предшествует его концу. Вторая и последующие строки содержат информацию о поступивших заданиях. Первое число в каждой строке – целое J, номер отдела, из которого поступило задание (1<=J<=N). Далее через пробел следует запись вида HH:MM (00<=HH<=23, 00<=MM<=59) (гарантируется, что задание всегда поступает в течение рабочего дня). Затем через пробел указано целое число – время (в минутах), которое требуется на выполнение этого задания В последней строке файла содержится число 0.
Формат выходного файла output.txt
Первая строка содержит слово YES, если не было таких отделов, которые оказались обделены машинным временем, и слово NO, если таковые были. После слова NO через пробел указывается число отделов, которые были обделены машинным временем. Затем через пробел (после слова YES или после количества отделов, обделенных машинным временем) следует целое число, показывающее, сколько задач было решено в течение рабочего дня. Задачу считать решенной, если в течение рабочего дня ее поставили на выполнение.
Пример входного файла
5 08:00 17:00
1 08:00 900
1 09:00 100
2 08:20 300
3 12:50 45
2 11:30 80
4 15:40 25
5 13:30 44
0
Пример выходного файла
NO 4 1
Примечания
Конечно же, выполнение другого задания должно начаться сразу же, если другое задание в этот момент времени есть
При прочих равных – например, есть два отдела, задачи которых сегодня еще ни разу не ставились на выполнение. В этом случае будет выбрана самая короткая по времени среди их задач. Или же: от отдела поступили две задачи, требующие разного времени выполнения – в этом случае выбор также будет сделан в пользу более короткой по времени задачи. Наконец, если задачи требуют одинакового времени выполнения (и равноправны по всем другим параметрам), сначала выполняется та, которая поступила раньше.