Задача 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