Описание
В драматическом театре им. Пушкина к юбилею Александра Сергеевича решили поставить оперу "Евгений Онегин". Артисты театра обладают красивыми, но не очень сильными голосами. По этой причине руководство театра дало указание приобрести радиомикрофоны. В начале и в конце спектакля все артисты находятся за кулисами. Артисты выходят на сцену и покидают ее через правую или левую кулису. Для того, чтобы петь на сцене, артист берет с собой один микрофон. Артист может выходить на сцену с микрофоном (одним), даже если ему не надо петь в этом выходе. Взяв микрофон, артист не может оставить его на сцене или передать другому артисту. При уходе артиста за кулисы микрофон остается за соответствующей кулисой до тех пор, пока его снова не возьмет какой-либо артист, выходящий на сцену

Очередность выходов артистов на сцену и их уходов за кулисы указывается в режиссерском плане. Кроме того, в этом плане указывается, через какие кулисы выходит (или уходит) артист и поет ли он в данном выходе

Задание
Напишите программу, которая по заданному режиссерскому плану определяет минимальное количество требуемых для постановки оперы микрофонов, их начальное размещение по кулисам и для каждого выхода указывает, брать или не брать микрофон


Входные данные
Первая строка входного файла содержит целое число N - количество артистов, участвующих в спектакле (1
N1000). Во второй строке записано целое число K - количество выходов артистов на сцену (1K3000). Далее идут 2K строк, описывающих режиссерский план спектакля. Каждая из них содержит четверку AiBiCiDi (1i2K):

Ai – символ "+", если в данный момент артист выходит на сцену, или символ "-", если артист со сцены уходит
Bi – номер артиста (целое число от 1 до N)
Ci – символ Л, если артист выходит (уходит) через левые кулисы, или символ П, если он выходит (уходит) через правые кулисы
Di – символ Д, если артист поет в данном выходе (пел перед данным уходом), или символ Н, если он не поет (не пел)

Выходные данные
Первая строка выходного файла должна содержать два целых числа. Первое число – количество микрофонов перед началом оперы с левой стороны, второе число – количество микрофонов с правой стороны. В каждой из последующих K строк необходимо вывести число "1" или "0" в зависимости от того, берет ли с собой микрофон очередной выходящий на сцену артист ("1" - берет, "0" - не берет)


Например:

STAGE.IN
3
4
+ 1 Л Д
- 1 Л Д
+ 2 Л Н
+ 3 Л Н
- 3 П Н
+ 1 П Д
- 1 Л Д
- 2 П Н


STAGE
.OUT
1 0
1
0
1
1






Идеи
адный" алгоритм и его модификация

Комментарии

Рассмотрим для начала упрощенный вариант задачи, когда каждый артист в каждом своем выходе на сцену поет. Решением тогда будет являться следующий "жадный" алгоритм.


Предположим, что перед началом оперы ни с левой, ни с правой стороны микрофонов нет, зато есть "склад с микрофонами", с которого их можно брать в случае необходимости. В каждый момент времени все имеющиеся микрофоны можно подразделить на четыре класса (состояния): находящиеся на складе (Склад), за левой кулисой (Л), за правой кулисой (П) и на сцене (Сцена)

Рассмотрим выход артиста на сцену. Пусть, для определенности, он выходит через левую кулису. Из каких микрофонов он может выбрать тот, в который будет петь? Либо из пребывающих в состоянии Л, либо из пребывающих в состоянии Склад

Если микрофонов в состоянии Л нет, то артисту ничего не остается, кроме как взять микрофон со склада. Если же имеется микрофон в состоянии Л, то нужно взять именно его. Действительно, перевести микрофон из состояния Склад в состояние Л можно в любой момент, поэтому состояние Склад является более выгодным, а микрофон в этом состоянии - более "дорогим"


Выбранный артистом микрофон переходит в состояние Сцена до тех пор, пока артист не уйдет со сцены, после чего микрофон попадает в состояние Л или П в зависимости от того, через левую или правую кулису он вышел

Сказанное выше иллюстрирует рисунок. Стрелки изображают возможные переходы между состояниями, а символы "0" и
"" - начальное количество микрофонов в каждом из состояний:



Ясно, что описанный алгоритм минимизирует количество микрофонов, взятых со склада. Если в процессе его работы L микрофонов было переведено со склада в состояние Л, а R микрофонов - в состояние П, то это и есть требуемое начальное размещение микрофонов по кулисам, а суммарное число микрофонов, необходимое для постановки оперы, равняется L+R

Вернемся теперь к первоначальной постановке задачи. У нас появились артисты, которые выходят на сцену, но не поют. Те из них, которые выходят и уходят через одну и ту же кулису, должны просто игнорироваться - давать им микрофоны бессмысленно. Оставшихся же можно использовать для "переброски" микрофонов с левой стороны на правую или наоборот. При этом "непоющий" артист имеет шанс взять лишь тот микрофон, который в момент его выхода через одну из кулис находится с той же стороны (брать микрофон со склада для переноса бессмысленно)


Рассмотрим, для определенности, выход "непоющего" артиста через левую кулису. Пусть имеется микрофон в состоянии Л. В зависимости от того, возьмет его артист или нет, микрофон может оказаться либо за левой кулисой, либо на сцене в процессе переноса с левой стороны на правую. По прошествии некоторого времени рассматриваемый артист уйдет со сцены через правую кулису, в результате чего микрофон может оказаться за любой из двух кулис
 
Итак, для каждого микрофона рассматриваем множество мест, где он в данный момент может находиться (в скобках указаны названия соответствующих состояний):

  1. либо он находится на складе и еще не был задействован (Склад)

  2. либо он на сцене у артиста, поющего в данном выходе (Сцена)

  3. либо он может быть только за левой кулисой (Л)

  4. либо он может быть только за правой кулисой (П)

  5. либо он может быть за любой из кулис (Л,П)

  6. либо он может находиться за левой кулисой, а может - на сцене у артиста, которому он не нужен, но который впоследствии уходит за правую кулису (Л,ЛП)

  7. либо он может находиться за правой кулисой, а может - на сцене у артиста, которому он не нужен, но который впоследствии уходит за левую кулису (П,ПЛ)

Микрофоны, находящиеся в последних двух состояниях неравноправны - для каждого из них нужно помнить, в какой момент времени микрофон достигнет противоположной кулисы (перейдет в состояние Л,П). Состояния и возможные переходы между ними иллюстрирует следующий рисунок (первоначально все микрофоны находятся в состоянии Склад)



Решение нашей задачи - естественное обобщение изложенного выше решения для упрощенного варианта и тоже, в некотором смысле, может быть названо "жадным алгоритмом". Последовательно просматриваем режиссерский план, содержащий все выходы/уходы артистов со сцены в хронологическом порядке


Разберем сначала случай выхода артиста на сцену. Как и прежде, ограничимся лишь случаем выхода через левую кулису:

  1. Если артист в данном выходе не поет, то:

  1. Если артист поет в данном выходе, то:


Выбранный в случае 2 микрофон переходит из состояния Л в состояние Сцена. Корректность описанных правил легко вытекает из того, что состояние Склад более выгодно, чем состояние Л,П, которое выгоднее состояния Л,ЛП, которое, в свою очередь, выгоднее состояния Л.

Рассмотрим теперь уход артиста со сцены через левую кулису. Если артисту микрофон был нужен, то этот микрофон следует перевести в состояние Л. Если микрофон не был нужен, но рассматриваемый артист мог быть использован для переноса микрофона с правой стороны на левую, то этот микрофон следует перевести из состояния П,ПЛ в состояние Л,П (а должен ли этот артист в действительности переносить микрофон определится позднее - в зависимости от того, с какой стороны он будет востребован)

Итак, алгоритм решения достаточно ясен. Храним количество микрофонов для состояний с номерами 3-5 из приведенного выше списка, а для состояний с номерами 6-7 – еще и время достижения противоположной кулисы. При использовании элементарных структур данных получаем алгоритм со сложностью O(KN). Если же реализовать структуру данных, аналогичную используемой в сортировке деревом [Вирт 89; п.2.3.2], то можно добиться сложности O(K log N)


 



Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V-,X-}

{$M 65384,0,655360}

Program
stage;
Const InputFile='stage.in';
      OutputFile='stage.out';
      MaxSp=3000;
      MaxN=1000;
Type TPl=Record
          lf, rg, ifl: Boolean;
          WhPri: Integer;
         End;
     BMas=Array[1..3000] Of Record
           nm, WhPri: Integer;
          End;
 Var A: Array[1..MaxSp] Of TPl;
     Plov: Array[1..MaxN] Of Integer;
     sc: Array[-1..5] Of LongInt;
     Sp: Array[3..5] Of ^BMas;
     N, K: Integer;
     Res: Array[1..MaxSp] Of Integer;
 
 Procedure ReadSmb(Var ch: Char);
  Begin
    Read(ch);
    While ch In [#0..#25, #27..#32] Do Read(ch);
  End;
 
 Procedure Init;
  Var i: Integer;
      ch: Char;
      nm, sc: Integer;
      rc, rd: Char;
   Begin
    New(Sp[3]);
    New(Sp[4]);
    New(Sp[5]);
    Assign(Input, InputFile);
     Reset(Input);
      ReadLn(N, K); sc:=0;
      For i:=1 To 2*K Do Begin
       ReadSmb(ch);
       Read(nm);
       ReadSmb(rc);
       ReadSmb(rd);
        If ch='+' Then Begin
          Inc(sc);
           Plov[nm]:=sc;
           A[sc].lf:=rc='П';
           A[sc].ifl:=rd='Д';
         End
        Else Begin
         A[Plov[nm]].rg:=rc='П';
         A[Plov[nm]].WhPri:=i;
        End;
      End;
     Close(Input);
   End;
 
 Procedure AddOch(Const aa: Integer;Const k: Integer);
  Var nm: Integer;
   Begin
    Inc(sc[aa]);
     nm:=sc[aa];
    Sp[aa]^[nm].WhPri:=A[k].WhPri;
    Sp[aa]^[nm].nm:=k;
   End;
 
 Function FindMax(Const aa: Integer): Integer;
  Var i, mx, rs: Integer;
   Begin
    mx:=-1;
    For i:=1 To sc[aa] Do
    If Sp[aa]^[i].WhPri>mx Then Begin
     rs:=i;
     mx:=Sp[aa]^[i].WhPri;
    End;
    FindMax:=rs;
   End;
 
 Procedure DelOch(Const aa, bb: Integer);
  Var i: Integer;
   Begin
    Dec(sc[aa]);
    For i:=bb To sc[aa] Do Sp[aa]^[i]:=Sp[aa]^[i+1];
   End;
 
 Procedure AddSong(Const k: Integer);
  Var aa, nd: Integer;
   Begin
    aa:=Byte(A[k].lf) + 1;
     Res[k]:=1;
    If sc[aa]>0 Then Dec(sc[aa])
     Else
    If sc[aa+2]>0 Then Begin
      nd:=FindMax(aa+2);
       Res[Sp[aa+2]^[nd].nm]:=0;
      DelOch(aa+2, nd);
     End
    Else
     If sc[5]>0 Then Begin
      nd:=Sp[5]^[sc[5]].nm;
      Res[nd]:=Byte(A[nd].lf<>A[k].lf);
      DelOch(5, sc[5]);
     End
    Else Inc(sc[aa-2]);
   End;
 
 Procedure AddNoSong(Const k: Integer);
  Var aa, nd, np: Integer;
   Begin
    If Not(A[k].lf xor A[k].rg) Then Exit;
     aa:=Byte(A[k].lf) + 1;
    If sc[aa]>0 Then Begin
      Res[k]:=1;
      AddOch(aa+2, k);
      Dec(sc[aa]);
     End
    Else
     If sc[aa+2]>0 Then Begin
      Inc(aa, 2);
      nd:=FindMax(aa); np:=Sp[aa]^[nd].nm;
      If A[k].WhPriThen Begin
        Res[np]:=0;
         Res[k]:=1;
        Sp[aa]^[nd].nm:=k;
        Sp[aa]^[nd].WhPri:=A[k].WhPri;
       End;
     End;
   End;
 
 Procedure DelSong(Const k: Integer);
  Begin
   Inc(sc[Byte(A[k].rg)+1]);
  End;
 
 Function GetNum(Const aa: Integer; Const pr: Integer): Integer;
  Var i: Integer;
   Begin
    GetNum:=1;
    For i:=1 To sc[aa] Do
    If Sp[aa]^[i].WhPri=pr Then Begin
      GetNum:=i;
      Exit;
     End;
   End;
 
 Procedure DelNoSong(Const k: Integer);
  Var aa: Integer;
   Begin
    If Res[k]=0 Then Exit;
     aa:=Byte(A[k].lf)+3;
     DelOch(aa, GetNum(aa, A[k].WhPri));
    AddOch(5, k);
   End;
 
 Procedure Solve;
  Var i, sp: Integer;
      ch: Char;
      nm: Integer;
      rc, rd: Char;
 
   Begin
    FillChar(sc, SizeOf(sc), 0);
    FillChar(Res, SizeOf(Res), 0);
    Assign(Input, InputFile);
     Reset(Input); sp:=0;
      ReadLn(N, K);
      For i:=1 To 2*K Do Begin
       ReadSmb(ch);
       Read(nm);
       ReadSmb(rc);
       ReadSmb(rd);
        If ch='+' Then Begin
           Inc(sp);
           Plov[nm]:=sp;
           If A[sp].ifl Then AddSong(sp)
            Else AddNoSong(sp);
         End
        Else Begin
         If A[Plov[nm]].ifl Then DelSong(Plov[nm])
          Else DelNoSong(Plov[nm]);
        End;
      End;
 
     Close(Input);
   End;
 
 Procedure Done;
  Var i: Integer;
   Begin
    Assign(Output, OutputFile);
     Rewrite(Output);
      WriteLn(sc[-1], ' ', sc[0]);
      For i:=1 To K Do WriteLn(Res[i]);
     Close(Output);
   End;
 
BEGIN
 Init;
  Solve;
 Done;
END.

 


© Особенности национальных задач по информатике