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

Задача А. Приказ

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

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

Подготовка к чемпионату — это не только составление задач и тестов, написание решений и  настройка проверяющей системы. Приходится решать еще немало «организационных вопросов».

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

            Все эти «организационные вопросы», как правило, регламентируются некоторым документом, который назовем Приказом. Этот Приказ нужно завизировать у Руководителей разных Подразделений. Визы необходимо собирать в строго определенном порядке. Однако, если очень постараться, можно потратить на это не так уж много времени. Но нужно точно знать, как заняты в течение рабочего дня все Руководители Подразделений. Во время совещаний, переговоров или обеда побеспокоить их не получится.

            Члены Оргкомитета выяснили о каждом Руководителе Подразделения, во сколько сегодня он может поставить визу на Приказ. Ваша задача — узнать, могут ли они собрать все визы сегодня, и сколько минимально времени они могут на это потратить. Учтите, что на переход от кабинета одного Руководителя Подразделения до кабинета другого руководителя подразделения требуется единица времени (или более).

 

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

Первая строка — целое число N (2 <= N <= 100) — количество Руководителей Подразделений, визы которых требуются на Приказе.

Вторая строка — последовательность различных чисел (от 1 до N) — порядок, в котором необходимо получать визы.

Каждая из следующих N строк (строке #(J+2) соответствует Руководитель Подразделения # J) содержит :

целое число Kj (1 <= Kj <= 500 для любого j) — количество отрезков времени, в которое Руководитель Подразделения #J может поставить визу на Приказ. Далее через пробел следует Kj пар чисел (так же через пробел) — начала и концы этих отрезков времени: Sj1, Fj1, Sj2, Fj2, …, SjKj, FjKj; при этом 0 <= (Sj1 <=Fj1), (Sj2 <= Fj2), ...(SjKj  <= FjKj ) <= 1440, гарантируется, что никакие два временных отрезка (для одного руководителя) не имеют общих точек.

 

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

Первая строка — слово YES или NO, в зависимости от того, возможно ли собрать все визы в течение дня.

Вторая строка (в случае, если визы собрать возможно) — минимальное время (в минутах), которое потребуется для этого

 

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

4

1 2 4 3

2 200 400 600 800

2 200 300 401 401

2 400 600 700 800

2 200 300 410 900

 

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

YES

11

 

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

2

1 2

1 200 200

1 200 200

 

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

NO


Сдать задачу

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