ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2003

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Менеджер кладбища

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Так повелось, что самые нерешаемые задачи на олимпиадах УрГУ обычно называют гробами. А ведь распределять гробы — тоже очень сложная задача. Рассмотрим кладбище, «посадочные» места в котором расположены в форме прямоугольника из N рядов и M столбцов (1 ≤ N, M ≤ 100). В начальный момент времени 0 кладбище пусто. Поступающих нежильцов подселяют в первый (имеющий минимальный номер) ряд, из тех, в которых есть свободные места, а если в этом ряду несколько мест, то выбирают столбец с минимальным номером. Время от времени клиентов кладбища навещают живые друзья и родственники — считается, что клиентам от этого приятнее. Но менеджеру кладбища это приносит только расстройство — из-за этих временных посетителей он не может отдать старые площадки новым клиентам. К счастью, посетители — тоже люди, поэтому через некоторое время они забывают, где именно лежат их друзья. Поэтому если клиента не навещали больше 1000 дней подряд, то на 1001 день менеджер считает могилу свободной — её все равно не найдут. Правда, родственники соседних клиентов (тех, номера столбцов и строк которых отличаются не более чем на 1) могут обратить внимание на странные изменения обстановки, поэтому менеджер подселяет нового клиента на старое место только если все соседние могилы не навещали в течении последних 100 дней (за такое время друзья соседей успевают забыть имена тех, кто лежит рядом с их другом). Если, несмотря на все усилия менеджера, на кладбище совсем не остается свободных мест, то он посылает клиента в крематорий.
В наши руки попал полный список появления клиентов и их живых друзей за некоторый период времени с момента основания кладбища. Ваша задача — определить по этой информации, сколько же клиентов было отправлено в крематорий.

Исходные данные

В первой строке указаны числа N и M, определяющие размер кладбища. Каждая следующая строка описывает некоторое событие. Описание события начинается с времени в днях с момента основания кладбища, после чего указывается типа события: либо d (поступление нового клиента), либо v (визит родственников и друзей) и порядковый номер клиента, к которому пришли друзья. События упорядочены по времени. Общее количество новых клиентов и посещений не превосходит 15000, из них не более 10000 описывают появление новых клиентов.

Результат

Программа должна вывести число клиентов, которых менеджер кладбища был вынужден отправить в крематорий.

Пример

исходные данныерезультат
2 2
1 d
1 d
1 d
1 d
300 d
500 v 2
1001 d
1002 d
1002 d
1003 v 3
1003 d
1003 d
1236 v 2
2032 v 2
2033 d
3

Замечания

  1. У каждой могилы от 2 до 8 соседей.
  2. Если похоронили в день T и никто не навещал, то перекопать могилу (сделать пустой) можно в день T+1001, а в T+1000 нельзя.
  3. Если могилу навестили в день T, то соседей можно перекопать в день T+101, а в T+100 ещё нельзя.
  4. Как только есть возможность, могилка перекапывается.
  5. Во время похорон родственники, подавленные несчастьем, ничего вокруг могилы не замечают (и не видят соседей).
  6. Клиенты нумеруются в порядке поступления. Порядковый номер присваивается всем клиентам, а не только тем, кого удалось похоронить.
  7. Если могилы уже нет или клиент сразу был отправлен в крематорий, или такого клиента ещё нет, то посещение ни на что не влияет.
  8. В пустые могилки хоронить можно всегда, независимо от времени посещения соседей (родственники соседей не удивятся, обнаружив, что пустая могила стала занятой).
Автор задачи: Станислав Васильев
Источник задачи: Open collegiate programming contest for student teams, Ural State University, March 15, 2003
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1251. Менеджер кладбища