14. Памятники
В связи с 20-летием со дня распада СССР в городе Н-ске решили поставить два памятника. Один памятник должен изображать серп, а другой, соответственно, молот. Руководить изготовлением памятников поручили Департаменту культурного наследия (ДКН) города Н-ска.
Каждый памятник планируется сделать из гранита, причём две болванки гранита уже лежат на складе. Остаётся лишь обработать болванки, чтобы получить готовые памятники. В городе Н-ске имеются цеха, которые могут принять участие в обработке памятников. Поскольку каждый цех хочет поучаствовать в проекте, но не каждый цех может выполнять все необходимые функции, то решено было разделить работу на части.
ДКН составил планы обработки памятников. В каждом плане перечислены все части работы в порядке их выполнения. Для каждой части имеется подробная техническая документация, указаны цех, который должен эту часть работы выполнить, и расчетное время, необходимое для выполнения. Никакой цех не может вести работу над обоими памятниками одновременно, а значит, может возникнуть ситуация, когда один из памятников придётся временно поместить обратно на склад. Цех может прервать обработку памятника ночью и переключиться на работу над другим памятником. В этом случае памятник отправляется на склад до возобновления работы над ним.
Перед ДКН поставили задачу закончить оба памятника к 26 декабря 2011 года (день X). Если памятник будет закончен на A дней позже, то из ДКН уволят A2 служащих. Вам поручили следить за ходом выполнения работы. Поскольку вы не хотите остаться без работы, вам нужно избежать увольнений, если это возможно, или минимизировать суммарное количество увольнений в противном случае.
Входные данные
Во входном файле сначала описан план работы над памятником «Серп», а затем план работы над памятником «Молот».
Описание плана работы начинается с целого числа K – количества частей, на которые разделена работа над памятником (1 <= K <= 400). В следующих K строках содержится информация о частях в порядке их выполнения. Для каждой части записано название цеха, который будет выполнять эту часть работы, а также необходимое для этого время в днях – целое число от 1 до 10^6 включительно. Название имеет длину от 1 до 1000 символов и состоит из латинских букв и цифр. Техническая документация для решения задачи вам не потребуется. Каждый цех имеет сво? уникальное имя.
В последней строке записано целое число T – количество рабочих дней, которое осталось до дня X (0 <= T <= 10^9).
Выходные данные
В первую строку выходного файла выведите минимально возможное количество увольнений. Затем выведите подробную историю ведения работ над памятником «Серп» и аналогичную историю для памятника «Молот». Минимальное количество увольнений должно достигаться при осуществлении этих историй.
История ведения работ над памятником начинается с целого числа P – количества отрезков времени в истории (1 <= P <= 10000). Каждая из последующих P строк должна содержать запись об отрезке времени. Запись состоит из целых чисел B, E и строки S, записанных через пробел. B – номер первого дня отрезка, E – номер последнего дня отрезка, S – название цеха, в котором деталь находится в этом отрезке времени (1 <= B <= E <= 10^9). Если деталь находится на складе, то S равно - "[storehouse]" (без кавычек). Первый день работы имеет номер 1. Отрезки времени не должны перекрываться, они должны идти подряд без пропусков дней, первый отрезок должен начинаться с первого дня работы.
Примеры
input.txt
2
Zubilo 3
Nazhdachka 2
2
Kuvalda 2
Kley 1
output.txt
10
0
2
1 3 Zubilo
4 5 Nazhdachka
4
1 1 Kuvalda
2 2 Kuvalda
3 3 [storehouse]
4 4 Kley
input.txt
4
Floor1 3
Floor2 1
Floor4 2
Floor4 3
3
Floor5 2
Floor2 3
Floor4 2
output.txt
7
17
5
1 3 Floor1
4 4 Floor2
5 6 Floor4
7 8 [storehouse]
9 11 Floor4
5
1 2 Floor5
3 3 Floor2
4 4 [storehouse]
5 6 Floor2
7 8 Floor4
Соревнование: XI Открытая Всесибирская олимпиада по программированию имени И.В. Поттосина 2010
Источник: http://olimpic.nsu.ru
| 