Задача C. Кристаллы
Задачу добавил: alef
Успешно сдано решений: 0
Сотрудники НИИ хотят усовершенствовать придуманный замок. В частности, они предлагают использовать для изготовления каждого слоя замка не отдельные кубики, а заготовки из специальных кристаллов, которые выращиваются на прямоугольной пластине.
Происходит это следующим образом.
Будем считать, что прямоугольная пластина разделена на квадратики с единичной стороной. В любой из квадратиков в какой-либо момент времени может быть помещен кристалл-заготовка. По прошествии единицы времени каждый свободный соседний с ним квадратик также будет заполнен кристаллом (соседними считаются квадратики, которые имеют по крайней мере одну общую точку). Эти кристаллы спустя единицу времени также порождают новые кристаллы в соседних (с ними) свободных квадратиках. Процесс будет продолжаться до тех пор, пока все квадратики пластины не будут заполнены кристаллами.
Если на пластину было помещено несколько кристаллов-заготовок, через некоторое время окажется, что одни и те же свободные квадратики являются предметом конкуренции. Допустим, что некоторый свободный квадратик является соседним как с квадратиком, заполненным кристаллом, ведущим свое происхождение от заготовки N1, так и с квадратиком, заполненным кристаллом, происходящим от заготовки N2.
Тогда этот свободный квадратик будет заполнен кристаллом, происходящим от заготовки N1, если в предшествующую заполнению единицу времени количество кристаллов, происходящих от заготовки N1, было больше количества кристаллов, происходящих от заготовки N2. Если же, напротив, количество кристаллов, происходящих от заготовки N2, превосходит количество кристаллов, ведущих свое происхождение от заготовки N1, то свободный квадратик будет заполнен кристаллом, происходящим от заготовки N2.
Если же количества кристаллов, происходящих от обеих заготовок, одинаковы, то свободный квадратик будет заполнен кристаллом, происходящим от заготовки, которая была помещена на пластину раньше. Если и времена размещения заготовок также совпадают, то преимущество имеет заготовка с меньшим значением координаты X, при равных координатах X — с меньшим значением координаты Y. Двух (или более) заготовок, у которых были бы одинаковы координаты (X, Y) и время размещения (T), нет.
По заданному расположению заготовок и моментам времени, в которые они были помещены на пластину, требуется определить момент времени, когда пластина будет полностью заполнена, и количества кристаллов, которые ведут свое происхождение от этих заготовок.
Формат входного файла input.txt
Первая строка — целые числа N и M (1 <= N, M <= 10000) через пробел — количество квадратиков на пластине по горизонтали и по вертикали.
Вторая строка — целое число K (1 <= K <= 200) — количество заготовок, которые будут размещены на пластине.
Каждая из следующих K строк содержит по три целых числа Xj, Yj, Tj через пробел — координата заготовки по горизонтали, координата заготовки по вертикали, время помещения заготовки на пластину.
Примечание. Заготовка не может быть помещена на пластину, если к моменту времени Tj квадратик с координатами Xj, Yj будет заполнен.
Формат выходного файла output.txt
Первая строка — целое число T — время, которое потребуется для полного заполнения пластины кристаллами
Вторая строка — K целых чисел через пробел — количества кристаллов, ведущих свое происхождение от заготовок в порядке их размещения во входном файле, которое получается спустя время T
|
Пример входного файла 10 10 3 7 3 1 10 2 3 1 10 0 Пример выходного файла 8 67 1 32 |
Пояснение к выходному файлу: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 3 3 1 1 1 1 1 1 1 1 3 3 3 1 1 1 1 1 1 1 3 3 3 3 3 1 1 1 1 1 3 3 3 3 3 3 1 1 1 1 3 3 3 3 3 3 3 1 1 1 3 3 3 3 3 3 3 3 1 1 |