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

Задача G. Разделение ресурса

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

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

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

В результате долгих обсуждений было принято разрешить-таки использовать диван – творение средневекового мастера Бен-Бецалеля в научных целях. Однако возникли проблемы.

В принципе, диван можно использовать в нескольких экспериментах одновременно. Для каждого эксперимента известно, сколько (в процентах) ресурса дивана он задействует. Разумеется, в один и тот же момент можно задействовать не более 100% ресурса дивана. Однако некоторые эксперименты могут быть несовместимы или совместимы частично. Несовместимость означает, что нельзя проводить эксперименты одновременно, даже если они вместе задействуют диван на 100% или менее. Частичная совместимость означает, что можно начинать один эксперимент после начала другого, чтобы он не повлиял на уже идущий (обратный порядок недопустим).

Считайте, что все эксперименты начинаются в начале рабочего дня и заканчиваются в конце рабочего дня. Нужно составить расписание, позволяющее использовать диван наиболее эффективно – т.е. провести все необходимые эксперименты за минимально возможное количество дней. Также требуется указать, в какой последовательности нужно начинать эксперименты в каждый из дней.

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

Первая строка содержит целое число N (0 <= N <= 100) – количество экспериментов, которые планируется проводить с помощью дивана. В следующих 3N строках содержится информация о каждом из N экспериментов (по порядку нумерации). Эксперимент описывается группой из трех строк. Первая строка группы содержит целое число Pj (1 <= j <= N, 0 <= Pj <= 100) – процент использования ресурса дивана в эксперименте № j. Вторая строка группы содержит целые числа через пробел – список экспериментов, с которыми эксперимент № j несовместим (номер эксперимента может встречаться в строке только один раз) Третья строка группы содержит целые числа через пробел – список экспериментов, с которыми эксперимент № j совместим частично. В списке указаны эксперименты, до начала которых нельзя начинать эксперимент № j, но после начала которых это делать можно. Файл завершается группой из трех строк, в каждой из которых содержится единственное число 0.

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

Первая строка содержит целое число D – минимально возможное количество дней, которое потребуется для проведения всех экспериментов. В каждой из следующих D строк содержится список экспериментов, проводящихся в соответствующий день, в том порядке, в котором их следует начинать. Если порядок не имеет значения, то первым указывается эксперимент с меньшим номером.

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


0
0
0

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

Сдать задачу

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