Задача С. Прогулки
Задачу добавил: alef
Успешно сдано решений: 7
Задача С. Прогулки
Как рассказала ребятам бабушка Тини (так представилась им пожилая женщина), в Хипе жизнь останавливается, и даже время отсчитывается с того момента, как произошла очередная установка Хипа, а все, на кого распространилось могущество господина Маллока, словно пребывают во сне, и могут лишь исполнять его приказания. Приказания же обычно состоят в том, чтобы всячески развлекать жен господина Маллока, когда они выходят на прогулку. При этом господин Маллок имел привычку сам разрабатывать график прогулок и определять места прогулок для своих жен таким образом, чтобы они никогда не могли встретиться. Однако с некоторых пор он принимает от своих жен предложения, где и когда они хотели бы гулять. Поэтому ему нужно проверить, выполняется ли его требование о невозможности встречи. Если оно не выполняется, то господин Маллок изменяет место или время прогулки для одной или нескольких своих жен.
Места прогулок задаются путем указания списка домов подданных господина Маллока, между которыми он разрешает гулять какой-либо из своих жен. Поэтому, чтобы его жены не встретились, необходимо, чтобы либо ни один из домов не был указан в списке жен, которые (даже в течение очень короткого времени) гуляют одновременно, либо времена прогулок не перекрывались.
Господин Маллок хочет изменить места и времена прогулки для как можно меньшего количества его жен. Ваша задача – написать программу, которая поможет ему в этом.
Формат входного файла input.txt
Первая строка – целые числа N (1 <= N <= 10000) и M (1 <= M <= 25) через пробел. N – количество домов подданных, M – количество жен господина Маллока, желающих выйти на прогулку.
Каждая из следующих M строк содержит через пробел:
— строку S, состоящую не более чем из 20 символов латинского алфавита и цифр и не содержащую внутри себя пробелов, – имя одной из жен господина Маллока;
— целое число T (0 <= T <= 1000000) – время, в которое она хотела бы отправиться на прогулку (отсчитывается от момента очередной установки Хипа);
— целое число D (0 <= D <= 1000) – время, в течение которого она хотела бы гулять;
— целое число K (0 <= K <= 1000) – количество домов подданных, которые определяют место планируемой прогулки
— K целых чисел J1, J2, …, JK через пробел (1 <= J1, J2, …, JK <= N) – номера домов подданных.
Формат выходного файла output.txt
Первая строка – целое число C – минимально возможное количество жен господина Маллока, место и время прогулки которых необходимо изменить, чтобы никакие две жены не могли встретиться друг с другом на прогулке.
Пример входного файла
100 5
calloc 0 100 2 1 2
realloc 100 100 2 2 3
free 150 100 2 3 4
brk 250 100 2 4 5
sbrk 350 1 6 5 6 7 8 9 99
Пример выходного файла
2