|
Название задачи: Микрофония . |
 |
Условие
В драматическом театре им. Пушкина к юбилею Александра Сергеевича решили поставить оперу «Евгений Онегин». Артисты театра обладают красивыми, но не очень сильными голосами. По этой причине руководство театра дало указание приобрести радиомикрофоны. В начале и в конце спектакля все артисты находятся за кулисами. Артисты выходят на сцену и покидают ее через правую или левую кулису. Для того, чтобы петь на сцене, артист берет с собой один микрофон. Артист может выходить на сцену с микрофоном (одним), даже если ему не надо петь в этом выходе. Взяв микрофон, артист не может оставить его на сцене или передать другому артисту. При уходе артиста за кулисы микрофон остается за соответствующей кулисой до тех пор, пока его снова не возьмет какой-либо артист, выходящий на сцену.Очередность выходов артистов на сцену и их уходов за кулисы указывается в режиссерском плане. Кроме того, в этом плане указывается, через какие кулисы выходит (или уходит) артист и поет ли он в данном выходе.
Напишите программу, которая по заданному режиссерскому плану
определяет минимальное количество требуемых для постановки оперы
микрофонов, их начальное размещение по кулисам и для каждого выхода
указывает, брать или не брать микрофон.
Входные данные
Первая строка входного файла содержит целое число N – количество артистов,
участвующих в спектакле (1 ≤ N ≤ 1000). Во второй строке записано целое число K
– количество выходов артистов на сцену (1 ≤ K ≤ 3000). Далее идут 2K строк,
описывающих режиссерский план спектакля. Каждая из них содержит четверку
AiBiCiDi (1 ≤ i ≤ 2K):
Ai
– символ +, если в данный момент артист выходит на сцену, или символ
-, если артист со сцены уходит;
Bi
– номер артиста (целое число от 1 до N);
Ci
– символ Л, если артист выходит (уходит) через левые кулисы, или
символ П, если он выходит (уходит) через правые кулисы;
Di
– символ Д, если артист поет в данном выходе (пел перед данным
уходом), или символ Н, если он не поет (не пел).
Выходные данные
Первая строка выходного файла должна содержать два целых числа. Первое
число – количество микрофонов перед началом оперы с левой стороны, второе
число – количество микрофонов с правой стороны. В каждой из последующих
K строк необходимо вывести 1 или 0 в зависимости от того, берет ли с собой
микрофон очередной выходящий на сцену артист (1 - берет, 0 - не берет).
Пример входного файла
3
4
+ 1 Л Д
- 1 Л Д
+ 2 Л Н
+ 3 Л Н
- 3 П Н
+ 1 П Д
- 1 Л Д
- 2 П Н
Пример выходного файла
1 0
1
0
1
1
Решение
Скачать архив тестов и решенийРассмотрим для начала упрощенный вариант задачи, когда каждый артист в каждом своем выходе на сцену поет. Решением тогда будет являться следующий «жадный» алгоритм.
Предположим, что перед началом оперы ни с левой, ни с правой стороны микрофонов нет, зато есть «склад с микрофонами», с которого их можно брать в случае необходимости. В каждый момент времени все имеющиеся микрофоны можно подразделить на четыре класса (состояния): находящиеся на складе (Склад), за левой кулисой (Л), за правой кулисой (П) и на сцене (Сцена).
Рассмотрим выход артиста на сцену. Пусть, для определенности, он выходит через левую кулису. Из каких микрофонов он может выбрать тот, в который будет петь? Либо из пребывающих в состоянии Л, либо из пребывающих в состоянии Склад.
Если микрофонов в состоянии Л нет, то артисту ничего не остается, кроме как взять микрофон со склада. Если же имеется микрофон в состоянии Л, то нужно взять именно его. Действительно, перевести микрофон из состояния Склад в состояние Л можно в любой момент, поэтому состояние Склад является более выгодным, а микрофон в этом состоянии – более «дорогим».
Выбранный артистом микрофон переходит в состояние Сцена до тех пор, пока артист не уйдет со сцены, после чего микрофон попадает в состояние Л или П в зависимости от того, через левую или правую кулису он вышел.
Сказанное выше иллюстрирует рисунок. Стрелки изображают возможные
переходы между состояниями, а символы 0 и
– начальное количество микрофонов в каждом из состояний.
Ясно, что описанный алгоритм минимизирует количество микрофонов, взятых со склада. Если в процессе его работы L микрофонов было переведено со склада в состояние Л, а R микрофонов – в состояние П, то это и есть требуемое начальное размещение микрофонов по кулисам, а суммарное число микрофонов, необходимое для постановки оперы, равняется L + R.
Вернемся теперь к первоначальной постановке задачи. У нас появились артисты, которые выходят на сцену, но не поют. Те из них, которые выходят и уходят через одну и ту же кулису, должны просто игнорироваться – давать им микрофоны бессмысленно. Оставшихся же можно использовать для «переброски» микрофонов с левой стороны на правую или наоборот. При этом «непоющий» артист имеет шанс взять лишь тот микрофон, который в момент его выхода через одну из кулис находится с той же стороны. (Брать микрофон со склада для переноса бессмысленно.)
Рассмотрим, для определенности, выход «непоющего» артиста через левую кулису. Пусть имеется микрофон в состоянии Л. В зависимости от того, возьмет его артист или нет, микрофон может оказаться либо за левой кулисой, либо на сцене в процессе переноса с левой стороны на правую. По прошествии некоторого времени рассматриваемый артист уйдет со сцены через правую кулису, в результате чего микрофон может оказаться за любой из двух кулис.
Итак, для каждого микрофона рассматриваем множество мест, где он в
данный момент может находиться (в скобках указаны названия
соответствующих состояний):
1) либо он находится на складе и еще не был задействован (Склад);
2) либо он на сцене у артиста, поющего в данном выходе (Сцена);
3) либо он может быть только за левой кулисой (Л);
4) либо он может быть только за правой кулисой (П);
5) либо он может быть за любой из кулис (Л, П);
6) либо он может находиться за левой кулисой, а может – на сцене у артиста,
которому он не нужен, но который впоследствии уходит за правую кулису
(Л, Л>П);
7) либо он может находиться за правой кулисой, а может – на сцене у артиста,
которому он не нужен, но который впоследствии уходит за левую кулису
(П, П>Л).
Микрофоны, находящиеся в последних двух состояниях неравноправны –
для каждого из них нужно помнить, в какой момент времени микрофон
достигнет противоположной кулисы (перейдет в состояние Л, П). Состояния и
возможные переходы между ними иллюстрирует
следующий рисунок. (Первоначально все микрофоны находятся в состоянии Склад.)
Решение нашей задачи – естественное обобщение изложенного выше решения для упрощенного варианта и тоже, в некотором смысле, может быть названо «жадным алгоритмом». Последовательно просматриваем режиссерский план, содержащий все выходы/уходы артистов со сцены в хронологическом порядке.
Разберем сначала случай выхода артиста на сцену. Как и прежде, ограничимся лишь случаем выхода через левую кулису.
1. Если артист в данном выходе не поет, то:
если есть микрофон в состоянии Л, то артист может его взять, т.е.
микрофон следует перевести в состояние Л, Л>П (можно представить
себе, что мы даем артисту микрофон с привязанной к нему
«резиночкой», второй конец которой остается за кулисой и за которую,
в случае необходимости, можно будет потянуть, вернув микрофон
обратно);
если микрофонов в состоянии Л нет, но есть микрофоны в состоянии Л,
Л>П, то среди них нужно выбрать тот микрофон, который позже всех
переходит в состояние Л, П (т.е. сможет достичь правой кулисы), и
оценить, не может ли рассматриваемый артист перенести этот
микрофон быстрее. Если может (т.е. этот артист достигнет правой
кулисы раньше), то оставить выбранный микрофон в состоянии Л,
Л>П, изменив время его перехода в состояние Л, П (тем самым мы как
бы дергаем за «резиночку», отбирая микрофон от одного «непоющего»
артиста на сцене, и вручаем этот микрофон другому «непоющему»);
если в состоянии Л, Л>П также нет ни одного микрофона, то делать
ничего не нужно.
2. Если артист поет в данном выходе, то:
если есть микрофоны в состоянии Л, то он должен взять любой из них;
если микрофонов в состоянии Л нет, но есть микрофоны в состоянии Л,
Л>П, то среди них нужно выбрать тот микрофон, который позже всех
переходит в состояние Л, П (т.е. сможет достичь правой кулисы), и
заключить (дернуть за «резиночку»), что этот микрофон переносить на
противоположную сторону не нужно, переведя его тем самым в
состояние Л и сведя случай к предыдущему;
если в состоянии Л, Л>П также нет ни одного микрофона, но есть
микрофоны в состоянии Л, П, то следует любой из них (они все
равноправны) перевести в состояние Л (дернув, в случае
необходимости, за «резиночку»);
если и в состоянии Л, П нет ни одного микрофона, то необходимо
достать микрофон со склада, переведя его в состояние Л.
Выбранный в случае 2 микрофон переходит из состояния Л в состояние
Сцена. Корректность описанных правил легко вытекает из того, что состояние
Склад более выгодно, чем состояние Л, П, которое выгоднее состояния Л, Л>П,
которое, в свою очередь, выгоднее состояния Л.
Рассмотрим теперь уход артиста со сцены через левую кулису. Если артисту
микрофон был нужен, то этот микрофон следует перевести в состояние Л. Если
микрофон не был нужен, но рассматриваемый артист мог быть использован для
переноса микрофона с правой стороны на левую, то этот микрофон следует
перевести из состояния П, П>Л в состояние Л, П (а должен ли этот артист в
действительности переносить микрофон определится позднее – в
зависимости от того, с какой стороны он будет востребован).
Итак, алгоритм решения достаточно ясен. Храним количество микрофонов для состояний с номерами 3-5 из приведенного выше списка, а для состояний с номерами 6-7 – еще и время достижения противоположной кулисы. При использовании элементарных структур данных получаем алгоритм со сложностью O(KN). Если же реализовать структуру данных, аналогичную используемой в сортировке деревом [Вирт 89; п. 2.3.2], то можно добиться сложности O(K log N).
