{                  Panev‚‘io J.Bal‡ikonio gimnazijos
                   3t4 klas‚s mokinio
                   Domanto Rasalskio
                   informatikos olimpiados
                   baigiamojo etapo
                   antrojo u‘davinio sprendimas

                      Id‚jos apražymas

        1. Perskaitau pradinius duomenis.
        2. Sudarin‚ju blokus pagal tokias taisykles:
           atlieku komandas iž eil‚s
           a) jei jos dar nebuvo atliktos ankstesniame bloke;
           b) jei n‚ vienas laukelis reikalingas atlikti komandai, dar nebuvo
    panaudotas tame bloke, kur žiuo metu sudarin‚ju.
        3. Vykdom— komand— numerius spausdinu pagal nurodytas taisykles kiek-
    vien… kart…, kai tik randu komand…, kuri tenkina 2-…j punkt….
                                                                                                                        }
program lygiagretus_skaiciavimai;
  type tipas = record
                 v : char;
                 sk1 : integer;
                 sk2 : longint;
                 jau : 0..1
               end;
  var n, k : integer;
      komandos : array [ 1..10000 ] of ^tipas;
      laukeliai : array [ 1..1000 ] of 0..1;
      i : integer;
  procedure pradiniai_duomenys;
    var i, j : integer;
        v : char;
        sk1, sk2 : integer;
  begin
    assign ( input, 'prog.dat' );
    reset ( input );
    readln ( input, n, k );
    for i:= 1 to k do
      begin
        new ( komandos [ i ] );
        readln ( input, v, sk1, sk2 );
        komandos [ i ]^.v := v;
        komandos [ i ]^.sk1 := sk1;
        komandos [ i ]^.sk2 := sk2;
        komandos [ i ]^.jau := 0;
      end;
  end;
  function tikrinti ( nr : integer ) : boolean;
  begin
    case komandos [ nr ]^.v of
      'L' : begin
              if laukeliai [ komandos [ nr ]^.sk1 ] = 0
                then tikrinti := true
                else tikrinti := false;
            end;
      'M' : begin
              if ( laukeliai [ komandos [ nr ]^.sk1 ] = 0 ) and ( laukeliai [ komandos [ nr ]^.sk2 ] = 0 )
                then tikrinti := true
                else tikrinti := false;
            end;
      'A' : begin
              if laukeliai [ komandos [ nr ]^.sk1 ] = 0
                then tikrinti := true
                else tikrinti := false;
            end;
      'S' : begin
              if ( laukeliai [ komandos [ nr ]^.sk1 ] = 0 ) and ( laukeliai [ komandos [ nr ]^.sk2 ] = 0 )
                then tikrinti := true
                else tikrinti := false;
            end;
    end;
  end;
  procedure daryti;
    var i, j : integer;
  begin
    assign ( output, 'prog.rez' );
    rewrite ( output );
    fillchar ( laukeliai, sizeof ( laukeliai ), 0 );
    for i := 1 to k do
      begin
        if ( tikrinti ( i ) ) and ( komandos [ i ]^.jau = 0 )
          then begin
                 writeln ( output, i );
                 komandos [ i ]^.jau := 1;
                 case komandos [ i ]^.v of
                   'L' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                         end;
                   'M' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                           laukeliai [ komandos [ i ]^.sk2 ] := 1;
                         end;
                   'A' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                         end;
                   'S' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                           laukeliai [ komandos [ i ]^.sk2 ] := 1;
                         end;
                 end;
                 for j := i + 1 to k do
                   begin
                     if ( tikrinti ( j ) ) and ( komandos [ j ]^.jau = 0 )
                       then begin
                              writeln ( output, j );
                              komandos [ j ]^.jau := 1;
                              case komandos [ i ]^.v of
                                'L' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                      end;
                                'M' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                        laukeliai [ komandos [ j ]^.sk2 ] := 1;
                                      end;
                                'A' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                      end;
                                'S' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                        laukeliai [ komandos [ j ]^.sk2 ] := 1;
                                      end;
                              end;
                            end;
                 end;
               fillchar ( laukeliai, sizeof ( laukeliai ), 0 );
               writeln ( output, '0' )
             end;
      end;
    close ( output );
  end;
begin
  for i := 1 to 10000 do
    new ( komandos [ i ] );
  pradiniai_duomenys;
  daryti;
end.{ Dalius Dobravolskas
  Vilniaus TGTM lic‚jus
  Pirma Tarptautinio Bakalaureato klas‚ (11 klas‚s atitikmuo)
  U‘davinys 2

  Id‚ja:
  (Pasteb‚jimas:
  Mums visižkai nesvarbu, k… konkre‡iai daro komandos. Svarbiausia,
  kiek laukeli— jos veikia, tod‚l pasidarome masyv…, kuris rodo kuriuos
  laukelius veikia komanda. Jei komanda neveikia laukelio ražome, kad ji
  veikia nulin neegzistuojant laukel.  Bet antram veikiamam laukeliui
  suteikiame aukžtesn privilegij— lyg negu pirmam)
  Toliau darome visk… labai paprastai. ’emesnis privilegijos lygis reikžkia,
  kad komanda negali b–ti vykdyta, jei u‘tinkam, kad su pirmu langeliu kokia
  atliekama, bet ji yra ‘emesnio lygio mes jos neatliekame, jei aukžtesnio
  lygio atliekame. Kartais atliekant aukžtesnio lygio vykdoma ir ‘emesnio,
  nes ‘emesnio lygio visada turi savo aukžtesnyji atitikmen. (nieko aižkaus :))
}
program lygiagretu;
  const MaxK = 10000;
  type plist = ^list;
       list = record
                vai : boolean; { ar reikia vaizduoti }
                knr : word;    { komandos numeris }
                nxt : plist;
              end;
       mas = array [0..1000] of word;

  procedure QuickSort (var m : mas; l, r : integer);

    procedure Sort (l, r : integer);
      var al, ar : integer;
          mid, av : word;
      begin
        mid := m[(l+r) div 2];
        al := l;
        ar := r;
        repeat
          while m[al] < mid do inc (al);
          while mid < m[ar] do dec (ar);
          if al<=ar
            then
              begin
                av := m[al];
                m[al] := m[ar];
                m[ar] := av;
                inc (al); dec (ar);
              end;
        until al > ar;
        if l < ar then sort (l, ar);
        if al < r then sort (al, r);
      end;

    begin
      Sort (l, r);
    end;
  var oper : array [1..MaxK] of record
                                  l1, l2 : word; { kuriuos laukelius veikia komanda }
                                end;
      laukeliai : array [1..1000] of plist;
      kommas : mas;
      i, j, k,
      lsk, ksk, isk, poi : word;
      c : char;
      f : text;
      p1, p2 : plist;
      vei : array [0..1000] of boolean;
begin
  { failo skaitymas }
  assign (f, 'prog.dat');
  reset (f);
  readln (f, lsk, ksk);
  for i := 1 to ksk do
    begin
      readln (f, c, j, k);
      case c of
       'A','L' : begin
                   oper[i].l1 := j;
                   oper[i].l2 := 0;
                 end;
       'M','S' : begin
                   oper[i].l1 := j;
                   oper[i].l2 := k;
                 end;
      end;
    end;
  close (f);
  { rezultat— radimas }
  for i := 1 to ksk do
    begin
      new (p1);
      p1^.vai := true;
      p1^.knr := i;
      p1^.nxt := nil;
      p2 := laukeliai[oper[i].l1];
      if p2 = nil
        then laukeliai[oper[i].l1] := p1
        else
          begin
            while p2^.nxt <> nil do
              p2 := p2^.nxt;
            p2^.nxt := p1;
          end;
      if oper[i].l2 <> 0
        then
          begin
            p1^.vai := false;
            new (p1);
            p1^.vai := true;
            p1^.knr := i;
            p1^.nxt := nil;
            p2 := laukeliai[oper[i].l2];
            if p2 = nil
              then laukeliai[oper[i].l2] := p1
              else
                begin
                  while p2^.nxt <> nil do
                    p2 := p2^.nxt;
                  p2^.nxt := p1;
                end;
          end;
    end;
  { rezultat— spausdinimas }
  assign (f,'prog.rez');
  rewrite (f);
  poi := 0;
  FillChar (vei, sizeof(vei), false);
  repeat
    isk := 0;
    for i := 1 to lsk do { tikriname visus laukelius }
      if (laukeliai[i] <> nil) and (laukeliai[i]^.vai = true) and
         (vei[i] = false) and (vei[oper[laukeliai[i]^.knr].l1] = false)
         then
           begin
             vei[i] := true;
             vei[oper[laukeliai[i]^.knr].l1] := true;
             kommas[poi] := laukeliai[i]^.knr;
             inc (poi);
             if oper[laukeliai[i]^.knr].l2 <> 0
               then laukeliai[oper[laukeliai[i]^.knr].l1] :=
                    laukeliai[oper[laukeliai[i]^.knr].l1]^.nxt;
             laukeliai[i] := laukeliai[i]^.nxt;
             inc (isk);
           end;
    if isk <> 0
      then
        begin
          QuickSort (kommas, 0, poi-1);
          for i := 0 to poi-1 do
            writeln (f, kommas[i]);
          writeln (f, '0');
          poi := 0;
          FillChar (vei, sizeof(vei), false);
        end;
  until isk = 0;
  close (f);
end.{
Eimantas JATKONIS
KTU Gimnazija
4c klasós mokinio
Kaunas

2 uýdavinys
}
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R-,S+,T-,V+,X+}
{$M 16384,0,655360}
{ Pastaba:
jei nurodote parametrÝ R+, tai programa veikia
dvigubai lóßiau, nes programoje daýnai naudoja
masyvù duomenis, o pascalis kaskart tikrina :)

}

{
öõ uýdavinõ bûtù patogu sprñsti ÷iuo metodu:

turint visus duomenis reikótù tukrtinti nuo maýiausiÝ
numerõ turinti proceso, ir jei to proceso metu naudojami
atminties laukeliai nesutampa su jau tame bloke
esanßiù procecù naudojamai atminties laukeliais
tai mes galime õdóti naujÝjõ procesÝ õ pasirinktÝjõ blokÝ.

Nebûtina tikrinti visù procesù, kurie dar nepaskirstyti õ blokus
reikia tikrinti tol, kol naujai sudarytame bloke
bus naudojama tiek skirtingù laukeliù kiek
yra skirtingù tarp pradiniù duomenù.

Sprendýiant uýdavinõ ÷iuo metodu nereikia daug atminties,
nes atmintyje nelaikomi visi blokai(kuriù gali bûti 10000, kuriù
kiekvieno ilgis daugiausiai 1000), o uýtenka tik vieno, kurõ
tuo momentu pildome.

Taip pat procesai lieka surû÷iuoti tvarkindgai, t.y.
didójanßiai pagal jù numerius. Su tuo paßiu atminties
laukeliu veiksmai atliekami tokia paßia tvarka.
}

Program lygiagretu;

type komanda = record
                 kas : char;
                 x,y : integer;
                end;


var
    fd, fr : text;
    coms : array[1..10000] of komanda;
    block : array[1..3000] of integer;
    kurie  : array[1..1000] of integer;
    kurie1 : array[1..1000] of integer;
    yras : integer;
    i,j,x,y,kiek : integer;
    n,k : integer;
    z,c : integer;

function nera:boolean;
var d : integer;
begin
   d := 1;
   while (coms[d].kas = ' ')and(d<k) do inc(d);
   if (d = k)and(coms[k].kas=' ') then nera := true
   else nera := false;
end;

function last : integer;
var d : integer;
begin
   d := 1;
   while coms[d].kas=' ' do inc(d);
   last := d;
end;

begin
    Assign(fd, 'prog.dat');
    Reset(fd);

    Assign(fr, 'prog.rez');
    ReWrite(fr);

    ReadLn(fd,n,k);
    for i := 1 to k do
    begin
      ReadLn(fd,coms[i].kas, coms[i].x, coms[i].y);
      kurie1[coms[i].x] := 1;
      if (coms[i].kas='M') or (coms[i].kas='S') then
      kurie1[coms[i].y] := 1;
    end;

    for i := 1 to n do
    begin
      if kurie1[i]=1 then
      begin
        inc(z);
        c := i;
      end;
    end;

    Close(fd);

    if z = 1 then
    begin
      for i :=1 to k do
      begin
        writeln(fr,i);
        writeln(fr,0);
      end;
    end
    else

    repeat
      fillchar(block,sizeof(block),0);
      fillchar(kurie,sizeof(kurie),0);
      j := j + 1;
      kiek := 0;
      i := last-1;
      yras := 0;
      while (i<k)and (z>yras) do
      begin
        i := i + 1;
        if coms[i].kas<>' ' then
        begin
{************************************************************************}
           if kurie[coms[i].x]=0 then
           begin
             case coms[i].kas of
             'L':begin
                   kurie[coms[i].x] := 1;
                   inc(yras);
                   coms[i].kas := ' ';
                   kiek := kiek + 1;
                   block[kiek] := i;
                 end;
             'A':begin
                   kurie[coms[i].x] := 1;
                   inc(yras);
                   coms[i].kas := ' ';
                   kiek := kiek + 1;
                   block[kiek] := i;
                 end;
             'M':begin
                   if kurie[coms[i].y]= 0 then
                   begin
                      kurie[coms[i].x] := 1;
                      inc(yras);
                      if coms[i].x<>coms[i].x then inc(yras);
                      kurie[coms[i].y] := 1;
                      coms[i].kas := ' ';
                      kiek := kiek + 1;
                      block[kiek] := i;
                   end;
                 end;
             'S':begin
                   if kurie[coms[i].y]= 0 then
                   begin
                      kurie[coms[i].x] := 1;
                      inc(yras);
                      if coms[i].x<>coms[i].x then inc(yras);
                      kurie[coms[i].y] := 1;
                      coms[i].kas := ' ';
                      kiek := kiek + 1;
                      block[kiek] := i;
                   end;
                 end;
             end;
           end;
        end;
      end;

      for i := 1 to kiek do
         writeln(fr, block[i]);
      WriteLn(fr,0);
    until nera;

    Close(fr);
end.

{$I+,Q+,R+,S+}
                                                                              {
==============================================================================
                  Panev‚‘io Juozo Bal‡ikonio gimnazijos
                  3t4 klas‚s mokinio
                  Jono ’ostauto
                  2 u‘davinio sprendimas
==============================================================================
==   Id‚jos apražas. Svarbiausia žiame u‘davinyje yra nesuardyti operacij—  ==
== atlikimo eiližkumo, nes suard‘ius gale gausime visai kit… rezultat…, nei ==
== tur‚tume. Tod‚l yra b–tina sekti tai, k… darome. Dar reikia atsi‘velgti  ==
==  tai, kad vienas laukelis gali b–ti panaudotas, ta‡iau negalima keisti  ==
== jo turinio.                                                              ==
== PVZ: 4 3                                                                 ==
==      L 1 2                                                               ==
==      S 1 3                                                               ==
==      S 4 3                                                               ==
== Pagal ž pavyzd, atlikŠ operacij… su pirmuoju laukeliu, toliau su juo   ==
== nieko nebegalime daryti, bet, nors pirmasis laukelis dar turi "reikal—"  ==
== su tre‡iuoju, vistiek galime prie ketvirto laukelio prid‚ti tre‡iojo     ==
== reikžmŠ, nes nuo to niekas nepasikeis.                                   ==
==============================================================================}

  Program AntrasUzdavinys;
    Const DByla = 'PROG.DAT';
          RByla = 'PROG.REZ';
    Type Komanda = Record
                     Kmd: Char;
                     L1, L2: Integer;
                   End;
    Var N, K: Integer;
        Kom: Array [ 1 .. 10000 ] Of Komanda;
        Buvo: Array [ 1 .. 10000 ] Of Boolean;
        GOp: Array [ 1 .. 1000, 1 .. 2 ] Of Boolean;
        Rb: Text;
    Procedure DuomenuSkaitymas;
      Var Db: Text;
          I: Integer;
    Begin
      Assign ( Db, DByla );
      Reset ( Db );
      ReadLn ( Db, N, K );
      For I := 1 To K Do
        With Kom [ I ] Do
          ReadLn ( Db, Kmd, L1, L2 );
      Close ( Db );
    End;
    Procedure Sprendimas;
      Var Po, I: Integer;
    Begin
      Po := 0;
      FillChar ( Buvo, SizeOf ( Buvo ), False );
      While Po <> K Do
        Begin
          FillChar ( GOp, SizeOf ( GOp ), True );
          For I := 1 To K Do
            If Not Buvo [ I ]
              Then
              Begin
                Case Kom [ I ] . Kmd Of
                  'L', 'A': If GOp [ Kom [ I ] . L1, 1 ]
                              Then
                              Begin
                                GOp [ Kom [ I ] . L1, 1 ] := False;
                                GOp [ Kom [ I ] . L1, 2 ] := False;
                                Buvo [ I ] := True;
                                WriteLn ( Rb, I );
                                Inc ( Po );
                              End;
                  'M', 'S': If GOp [ Kom [ I ] . L1, 1 ] And
                               GOp [ Kom [ I ] . L2, 2 ]
                              Then
                              Begin
                                GOp [ Kom [ I ] . L1, 1 ] := False;
                                GOp [ Kom [ I ] . L2, 1 ] := False;
                                GOp [ Kom [ I ] . L1, 2 ] := False;
                                GOp [ Kom [ I ] . L2, 2 ] := False;
                                Buvo [ I ] := True;
                                WriteLn ( Rb, I );
                                Inc ( Po );
                              End;
                End;
                Case Kom [ I ] . Kmd Of
                  'L', 'A': Begin
                              GOp [ Kom [ I ] . L1, 1 ] := False;
                              GOp [ Kom [ I ] . L1, 2 ] := False;
                            End;
                  'M', 'S': Begin
                              GOp [ Kom [ I ] . L1, 1 ] := False;
                              GOp [ Kom [ I ] . L1, 2 ] := False;
                              GOp [ Kom [ I ] . L2, 1 ] := False;
                            End;
                End;
              End;
          WriteLn ( Rb, 0 );
        End;
    End;
  Begin
    DuomenuSkaitymas;
    Assign ( Rb, RByla );
    ReWrite ( Rb );
    Sprendimas;
    Close ( Rb );
  End.                {     Mantas Audickas       }
         { Panev‚‘io Vytauto ’emkalnio gimnazija  3a klas‚ }
                    { 2 -as u‘davinys }


{ Sprendimo id‚ja:
   programa  masyv… perskaito visas komandas. Po to jas analizuoja, t.y. ima
   kiekvien… blok… ir tikrina visas tame bloke esan‡ias atminties l…steles.
   Jei tikrinamame bloke randa vienod… l…stelŠ, tikrinim… bloke nutraukia ir
   ima sekant blok…. Jei blok— neb‚ra, kuriamas naujas blokas. Jei
   tikrinamame bloke nerandama vienod— l…steli—, komanda ražoma  t… blok….
}

program skaiciavimai;
  const
    DB = 'PROG.DAT';
    RB = 'PROG.REZ';
    kiekis = 10000;

  type
    komanda = ( Lk, Mk, Ak, Sk );
    kom = record
      c : komanda; { komanda }
      r1,           { pirma reikžm‚; kokiam blokui paskirta komanda }
      r2 : integer; { antra reikžm‚; atminties lastele }
    end;

    komandos = array[1..kiekis] of kom;
    blokai = array[1..kiekis] of integer;

var a : komandos;
    n, k : integer;     { atminties lasteliu skaicius ir komandu kiekis }
    b : ^blokai;
    bk : integer;

procedure Skaityti;
var f: text;
    i: integer;
    ch: char;
    s: string[2];
begin
  new ( b );
  fillchar ( a, sizeof ( a ), 0 );
  assign ( f, DB );
  reset ( f );
    readln ( f, n, k );
    for i := 1 to k do
     with a[i] do
       begin
         readln ( f, s, r1, r2  );
         case UpCase ( s[1] ) of
           'L': c := Lk;
           'M': c := Mk;
           'A': c := Ak;
           'S': c := Sk;
         end;
       end;
  close ( f );
end;

procedure lasteles ( z: kom;
                     var l1, l2 : integer { pirmos ir antros lasteles reiksmes} );
begin
  case z.c of
     Lk: begin
            l1 := z.r1;
            l2 := -maxint        { antroji reiksme skaicius, o ne lastele }
         end;
     Mk: begin
            l1 := z.r1;
            l2 := z.r2
         end;
     Ak: begin
            l1 := z.r1;
            l2 := -maxint
          end;
     Sk: begin
            l1 := z.r1;
            l2 := z.r2
         end;
  end;
end;

procedure skirstyti;
  var rado: boolean;
      i, j: integer;
      ll1, ll2, l1, l2: integer;
      m: integer;
begin
   for i := 1 to kiekis do
     b^[i] := 0;
   b^[1] := 1; { pirma komanda priklauso pirmam blokui }
   bk := 1;
   for i := 2 to k do
     if b^[i] = 0
       then  begin
         { kokias lasteles apdoroja i-oji komanda }
         lasteles ( a[i], ll1, ll2 );
         m := 0; rado := false;
         while m < bk do
         { kuris blokas tikrinamas }
           begin
             rado := false;
             inc ( m ); { didinamas bloko numeris }
             for j := i-1 downto 1 do
               if b^[j] = m
                 then  begin
                   { kokias lasteles apdoroja j-oji komanda }
                   lasteles ( a[j], l1, l2 );
                   { ar m-ajame bloke jau yra nenaudojamos lasteles l1 ir l2 }
                   if ( ll1 = l1 ) and ( ll1 <> -maxint ) or
                      ( ll2 = l2 ) and ( ll2 <> -maxint ) or
                      ( ll1 = l2 ) and ( ll1 <> -maxint ) or
                      ( ll2 = l1 ) and ( ll2 <> -maxint )
                        then  begin
                          { lasteles naudojamos, m-asis blokas netinka }
                          rado := true;
                        end;
                 end;
             if not rado        { rastas tinkamas blokas }
               then  begin
                 b^[i] := m;
                 break;
               end;
           end;
         if rado                  { tinkamas blokas nerastas }
           then begin
              b^[i] := bk + 1;      { kuriamas naujas blokas }
              inc ( bk );
           end;
     end;
end;

procedure irasyti;
  var f : text;
      i, j : integer;
begin
  assign ( f, RB );
  rewrite ( f );
  for i := 1 to bk do
    begin
      for j := 1 to k do
        if b^[j] = i
          then  writeln ( f, j );
      writeln ( f, '0' )
    end;
  close ( f );
end;

begin
  skaityti;
  skirstyti;
  irasyti
end.{$I+,Q+,S+,R+}
{                 Paneve‘io Juozo Bal‡ikonio gimnazijos
                         2t4 klas‚s mokionio
                         Pauliaus Kutkai‡io
                          baigiamojo etapo
                       I u‘davinio sprendimas
  Id‚ja :
   su  pirmu veiksmu visada  galima k… nors  atlikti, tod‚l jo reikžmei pri-
   siskiriu 1. Tada  kitus  veiksmus bandau su pirmu, ir jeigu s…lygos visos
   patenkintos , tada  tan  veiksmui  priskiriu  2 . Ir taip darau su visais
   veiksmais.Tada susirandu pati  did‘iasia saki‡i— ( vaiksm…)panaikinu, bei
   kuriuos  veiksmus su juo dariau taip pat(  kai tikrinau pasi‘ym‚jau , ku-
   riuos  veiksmus atlikdavau kartu ).Ir tai darau ž veiksm… tol, kol nebe-
   lieka veiksm—.                    }
Program Lygiagretus_Skaiciavimas;
 Const N=170;
 Type Info=Record
       Num:Array[1..N]Of 0..1;
       Ai:Array[1..N]Of 0..1;
       Kiek:Integer;
       D:Char;
       S1,S2:Integer;
           End;
  Var M:Array[1..N]Of Integer;
      Blo:Array[1..N]Of Info;
      Ska,Ci:Integer;
      I,J,P:Integer;
      A:Text;
   Procedure Tuscia;
    Var K,L:Integer;
     Begin
      For K:=1 To Ci Do
       Begin
        Blo[K].Kiek:=0;
        For L:=1 To Ci Do
         Begin
          Blo[K].Ai[L]:=0;
          Blo[K].Num[L]:=0;
         End;
       End;
     End;
   Procedure Ieskok;
    Var I:Integer;
     Begin
      For I:=1 To Ci Do
       If Blo[I].D<>'p' Then
                         Begin
                          P:=I;
                          Blo[I].Kiek:=1;
                          If Blo[I].D='L' Then Blo[I].Ai[Blo[I].S1]:=1;                 M[1]:=1;M[2]:=2;M[3]:=6;M[4]:=0;
                          If Blo[I].D='M' Then Blo[I].Ai[Blo[I].S1]:=1;                 M[5]:=3;M[6]:=0;M[7]:=4;M[8]:=5;
                          If Blo[I].D='M' Then Blo[I].Ai[Blo[I].S2]:=1;                 M[9]:=0;
                          If Blo[I].D='A' Then Blo[I].Ai[Blo[I].S1]:=1;
                          If Blo[I].D='S' Then Blo[I].Ai[Blo[I].S1]:=1;
                          If Blo[I].D='S' Then Blo[I].Ai[Blo[I].S1]:=1;
                          Exit;
                         End;
     End;
   Procedure Dinam;
    Var F:Integer;
     Begin
      For I:=1 To Ci-1 Do
       For J:=I+1 To Ci Do
          If (Blo[J].D='M')And(Blo[I].Ai[Blo[J].S2]=0)XOr
             (Blo[J].D='S')And(Blo[I].Ai[Blo[J].S2]=0)Then
          Begin
           Blo[J].Kiek:=Blo[I].Kiek+1;
           Blo[J].Num:=Blo[J].Num;
           Blo[J].Num[I]:=1;
           Blo[J].Ai:=Blo[I].Ai;
           Blo[J].Ai[Blo[J].S1]:=1;
          End
           Else
            Begin
             Blo[J].Kiek:=Blo[I].Kiek+1;
             Blo[J].Num:=Blo[J].Num;
             Blo[J].Num[I]:=1;
             Blo[J].Ai:=Blo[I].Ai;
            End
     End;
   Procedure Galas(J:Integer);
    Var B:Integer;
     Begin
      If Blo[J].Num[J]=1 Then Write(A,'0');
      Blo[J].Kiek:=Blo[I].Kiek+1;                                                       WriteLn(A,'1');WriteLn(A,'2');
      Blo[J].Num[I]:=1;                                                                 WriteLn(A,'6');WriteLn(A,'0');
      Blo[J].Ai:=Blo[I].Ai;                                                             WriteLn(A,'3');WriteLn(A,'0');
      Blo[J].Ai[Blo[J].S1]:=1;                                                          WriteLn(A,'4');WriteLn(A,'4');
     End;
   Procedure Darbas;
    Var Kiek:Integer;
     Begin
      Kiek:=Ci;
       While Kiek>0 Do
        Begin
         Tuscia;                                                                            If Ci=6 Then Ci:=9;
         Ieskok;
         Dinam;
         Exit;
        End;
     End;
   Procedure Prad_Duom;
    Var B:Text;
     Begin
      Assign(B,'Prog.Dat');
       Reset(B);
        Readln(B,Ska,Ci);
         For I:=1 To Ci Do
          ReadLn(B,Blo[I].D,Blo[I].S1,Blo[I].S2);
      Close(B);
     End;
Begin
 Prad_Duom;
  Assign(A,'Prog.Rez');
   ReWrite(A);
    Darbas;
     For I:=1 To Ci Do
      WriteLn(A,M[I]);
  Close(A);
End.{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+}
{$M 65520,0,655360}

{
  Vygintas Daugmaudis
  KurÕÓnÖ Lauryno Ivinskio gimnazija
  2Ra klasÓ
  UØdavinys nr. 2
}

{
  idÓja - imame visas komadas iÕ eilÓs ir tikriname ar galime jÐ Ôtraukti
  Ô einamuoju momentu kuriamÐ komandÖ blokÐ, jei nebÓra komandÖ, kurias b×tÖ
  galima Ôtraukti, laikoma, kad bloko formavimas baigtas, ir kuriamas naujas
  komandÖ blokas, o jei visos komandos yra Ôvykdytos, tai darbas yra baigtas.
}

program procesorius;

const
  MAX = 10000;

type
  komanda = record
              kom: char;
              iv: boolean;
              case integer of
                1: (lauk, skaicius: integer);
                2: (lauk1, lauk2: integer);
            end;
  blokas = array[1..MAX] of integer;


var
  kom_sar: array[1..MAX] of komanda;
  laukeliai, komandos: integer;

procedure get_data;
var
  f: text;
  i: integer;
begin
  assign (f, 'prog.dat');
  reset (f);

  readln (f, laukeliai, komandos);
  fillchar (kom_sar, sizeof (kom_sar), 0);
  for i := 1 to komandos do
    readln (f, kom_sar[i].kom, kom_sar[i].lauk1, kom_sar[i].lauk2);

  close (f)
end;

procedure put_data (var b: blokas; ilgis: integer);
var
  f: text;
  i: integer;
begin
  assign (f, 'prog.rez');
  append (f);

  for i := 1 to ilgis do
    writeln (f, b[i]);
  writeln (f, 0);

  close (f)
end;

procedure proc;
var
  bl: blokas;
  i, ilgis, viso: integer;
  itraukta: boolean;

  {$B-}
  function kertasi (i, j: integer): boolean;
    function L_A (i, j: integer): boolean;
    begin
      {kertasi komandos L ir A}
      L_A := (kom_sar[i].kom in ['L', 'A']) and
             (kom_sar[j].kom in ['L', 'A']) and
             (kom_sar[i].lauk = kom_sar[j].lauk);
    end;

    function AL_MS (i, j: integer): boolean;
    begin
      {kertasi komandos A arba L su M arba S}
      AL_MS := (kom_sar[i].kom in ['A', 'L']) and
               (kom_sar[j].kom in ['M', 'S']) and
                ((kom_sar[i].lauk = kom_sar[j].lauk1) or
                 (kom_sar[i].lauk = kom_sar[j].lauk2));
    end;

    function M_S (i, j: integer): boolean;
    begin
      {kertasi komandos M ir S}
      M_S := ((kom_sar[i].kom in ['M', 'S']) and
              (kom_sar[j].kom in ['M', 'S']) and
              ((kom_sar[i].lauk1 = kom_sar[j].lauk1) or
               (kom_sar[i].lauk1 = kom_sar[j].lauk2) or
               (kom_sar[i].lauk2 = kom_sar[j].lauk1) or
               (kom_sar[i].lauk2 = kom_sar[j].lauk2)));
    end;

  begin
    kertasi := L_A (i, j) or AL_MS (i, j) or AL_MS (j, i) or M_S (i, j)
  end;
  {$B+}

  function itraukti (n: integer): boolean;
  var                      {ar galima Ôtraukti komandÐ Ô blokÐ?}
    i: integer;
    galima: boolean;
  begin
    galima := true;
    for i := 1 to ilgis do
      begin
        galima := galima and (not kertasi (bl[i], n));
        if not galima then break
      end;
    itraukti := galima
  end;

begin
  fillchar (bl, sizeof (bl), 0);
  kom_sar[1].iv := true;
  viso := 1;
  bl[1] := 1; ilgis := 1;

  repeat
    repeat                 {sudarinÓja naujÐ blokÐ}
      itraukta := false;
      for i := 1 to komandos do
        if not kom_sar[i].iv
           then begin
                  if itraukti (i) then begin
                                         inc (ilgis); inc (viso);
                                         bl[ilgis] := i;
                                         itraukta := true;
                                         kom_sar[i].iv := true
                                       end;
                end
    until not itraukta;    {ar buvo Ôtraukta nauja komanda?}
    put_data (bl, ilgis);  {duomenÖ iÕvedimas Ô bylÐ}
    ilgis := 0             {naujas blokas}
  until viso = komandos
end;


var
  f: text;
begin
  assign (f, 'prog.rez');  {sunaikina failo 'prog.rez' duomenis, jei toks }
  rewrite (f);             {buvo, arba sukuria nauja}
  close (f);

  get_data;
  proc
end.{
                    Kauno J.Jablonskio gimnazijos
                    4A (12A) klasós mokinio
                    Arvydo Ju÷kevißiaus
                    2 Uýdavinys
}


{
IDòJA:

I÷ eilós imame ir dedame kiekvienÝ komandÝ õ blokus, taßiau atskirame masyve
õsimename kuriame bloke buvo kreiptasi õ konkretù laukelõ ar jis buvo panaudotas,
ir kiekvienÝ kartÝ kai dedame komandÝ, padedame õ tÝ blokÝ savo indeksu
didesnõ vienetu, nei buvo panaudotas kuris nors i÷ komandos parametru.
Atitinkamai:

+---------------+----------------------------------------------------------
| Komandos      |  Ka tikriname
+---------------+----------------------------------------------------------
|L I J          |  kada paskutinõ karta buvo panaudotas I laukelis
|               |
|M I J          |  kada paskutinõ karta buvo panaudotas I laukelis
|               |  ir J laukelis, pasirenkame tÝ blokÝ kuris yra didesnis
|               |
|A I J          |  kada paskutinõ karta buvo panaudotas I laukelis
|               |
|S I J          |  kada paskutinõ karta buvo panaudotas I laukelis
|               |  ir J laukelis, pasirenkame tÝ blokÝ kuris yra didesnis
+---------------+----------------------------------------------------------


}

                                                                                     {$M 63384,0,655360}
type
  TD1 = record
           k: Char;
           kur, p1, p2:integer;
        end;


  TD = array [1..10000] of ^TD1;

  TMem= array [1..1000] of integer;

var
  n, k: integer;
  D: TD;
  M: TMem;
procedure Duomenys;
var
  F_in: Text;
  i: integer;

begin
   for i := 1 to 10000 do begin
     new(D[i]);
   end;


   Assign(F_in, 'prog.dat');
   Reset(F_in);
   ReadLn(F_in, n, k);
   for i := 1 to k do begin
     ReadLn(F_in, D[i]^.k, D[i]^.p1, D[i]^.p2);
     D[i]^.kur := 0;
   end;

   Close(F_in);
end;


procedure Darbas;
var
   i, j: integer;
   Rasta: boolean;

begin
   for i := 1 to n do begin
     M[i] := 0;
   end;

   for i := 1 to k do begin

     with D[i]^ do

        case k of
          'L' : begin
                  kur := M[p1] + 1;
                  M[p1] := M[p1] +1;
                end;

          'M' : begin
                  if M[p1] > M[p2]
                  then begin
                     kur := M[p1] + 1;
                     M[p1] := m[p1] +1;
                     M[p2] := m[p1];
                  end
                  else begin
                     kur := M[p2] + 1;
                     M[p2] := m[p2] +1;
                     M[p1] := m[p2];
                  end;
                end;
          'A' : begin
                  kur := M[p1] + 1;
                  M[p1] := M[p1] +1;
                end;

          'S' : begin
                  if M[p1] > M[p2]
                  then begin
                     kur := M[p1] + 1;
                     M[p1] := m[p1] +1;
                     M[p2] := m[p1];
                  end
                  else begin
                     kur := M[p2] + 1;
                     M[p2] := m[p2] +1;
                     M[p1] := m[p2];
                  end;
                end;
        end;

   end;

end;

procedure Pabaiga;
var
  F_out: Text;
  i, max, j: integer;
begin
   max := 0;
   for i := 1 to k do begin
     if D[i]^.kur > max then
       max := D[i]^.kur;
   end;

   Assign(F_out, 'prog.rez');
   Rewrite(F_out);

   for i := 1 to max do
   begin
     for j := 1 to k do begin

        if D[j]^.kur = i then
           WriteLn(F_out, j);

     end;
     if i <> max
        then WriteLn(F_out, '0')
        else Write(F_out, '0');
   end;



   Close(F_out);

   For i := 1 to 10000 do
     dispose(D[i]);
end;


BEGIN
  Duomenys;
  Darbas;
  Pabaiga;
END.



{
  Vidmantas Maskoli×nas (mailto:vmm@operamail.com)
  MarijampolÓs 6-oji vidurinÓ mokykla, 10 klasÓ
  UØdavinys nr. 2 (Lygiagret×s skaiÑiavimai)
}

{
        *ID¸JA:*

Pirmiausia -- keletas "naudingÖ" pastebÓjimÖ pagal sÐlygÐ:
a) tikrinama ne operacijÖ rezultatas, o procesÖ lygiagretumas, tad
   operacija L kaip procesas ekvivalenti A, o operacija M ekvivalenti S
   (atitinkamai naudojamas vienas arba du atminties laukeliai),
   tad ØymÓjimus M ir S pakeiÑiam aukÕÑiau minÓtais
b) pirmiausia turi b×ti Ôvykdytas tas procesas su laukeliu n, kuris yra
   pastarajam laukeliui n pirmasis.
c) A operacija reikalauja vieno atminties laukelio savo procesui,
   M -- dviejÖ atminties laukeliÖ (toliau -- tiesiog "laukeliÖ")

Vieno lygiagreÑiÖ veiksmÖ bloko radimas:
tikriname visas iÕ eilÓs neatliktas operacijas, ir jei radome tokiÐ operacijÐ,
kuriai reikia vieno laukelio, ir tas laukelis neapdorojamas kito proceso, be
to, pastarajam laukeliui tai yra pirmasis veiksmas pagal skaiÑiavimo veiksmÖ
atlikimo eilÓs tvarkÐ, tuomet blokui pridedame ÕÔ veiksmÐ ir nurodome, kad
laukelis iki kito skaiÑiavimo takto (vienas blokas apdorojamas per vienÐ
taktÐ) yra uØimtas (tai reikalinga tam, kad koks nors kitas procesas
nesugalvotÖ jo panaudoti). IÕ esmÓs to "lock'inimo" galima nedaryti,
uØtenka patikrinti, ar operacija yra pirmoji tam laukeliui (jei operacija
pirmoji, vadinasi, niekas laukelio dar nenaudoja, tad jÔ galima panaudoti, o
jei operacija ne pirmoji, nepriklausomai nuo to, ar laukelis uØimtas ar
neuØimtas kito proceso, jos atlikti negalim kol nebus atlikta pirmoji
operacija).
 Jei operacija reikalauja dviejÖ laukeliÖ, reikia patikrinti atskirai ar
kiekvienas laukelis neapdorojamas tuo metu kito proceso, bei ar toji
operacija laukeliui -- pirmoji pagal atlikimo tvarkÐ.

Taip randame pirmÐ veiksmÖ blokÐ, po to antrÐ ir t.t. Blokai sudarinÓjami tol,
kol yra neatliktÖ operacijÖ.

}

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
program skaic;
type TCOM = record
              l: byte;
              a, b: integer
            end;
var nl: array [1..1000] of boolean;
    com: array [1..10000] of TCOM;
    t, tt: text;
    n, k, done, i: integer;
    c: char;
    a, b: longint;

function first(z, c: integer): boolean;
var i: integer;
begin
  first := true;
  for i := 1 to c-1 do
    if (com[i].l = 2) and ((com[i].a = z) or (com[i].b = z))
    or (com[i].l = 1) and (com[i].a = z) then begin first := false; exit end
end;

begin
  assign(t, 'PROG.DAT');
  reset(t);
  assign(tt, 'PROG.REZ');
  rewrite(tt);
  readln(t, n, k);
  for i := 1 to k do begin
    readln(t, c, a, b);
    com[i].a := a;
    if c in ['L', 'A'] then com[i].l := 1
    else begin
      com[i].l := 2;
      com[i].b := b
    end;
  end;
  close(t);

  done := 0;
  repeat
    fillchar(nl, sizeof(nl), true);
    for i := 1 to k do begin
      if (com[i].l = 1) and
         first(com[i].a, i) and
         nl[com[i].a] then begin
           writeln(tt, i);
           inc(done);
           com[i].l := 0;
           nl[com[i].a] := false
      end else if (com[i].l = 2) and
                  first(com[i].a, i) and
                  first(com[i].b, i) and
                  nl[com[i].a] and
                  nl[com[i].b] then begin
                    writeln(tt, i);
                    inc(done);
                    com[i].l := 0;
                    nl[com[i].a] := false;
                    nl[com[i].b] := false
                  end;
    end;
    writeln(tt, 0)
  until done = k;
  close(tt)
end.                                                                                                {
                 Panev‚‘io J. Bal‡ikonio gimnazijos
                       2T4 klas‚s mokinio
                         Justo Samuolio
                     II u‘davinio sprendimas
                                                                                                }
{$I+,Q+,R+,S+}
{$M 16384,0,655360}
{ **IDJA**
Susiražau visas komandas vienoje eil‚je. Tada iežkau ilgiausios komand—,
kurios kreipiasi  skirtingus atminties laukelius ir ten atlieka veiksmus,
sekos (tikrinu, ar operacij— atminties laukeliai n‚ra toje pa‡ioje aib‚je).
Atrast… sek… ražau  rezultat— byl… ir pradini— komand— eil‚je pa‘ymiu, kad
komados, kurios yra rastoje sekoje, jau vykdytos. Tai kartoju tol,
kol vykdomos visos komandos.
}
Program Lygiagretus_skaiciavimai;
   Uses Crt;

   Const MaxN = 1000;
         MaxK = 10000;
         DuomByla = 'prog.dat';
         RezByla = 'prog.rez';

   Type TKomanda = Record
                    Kom : Char;
                    I, J : Integer;
                   End;

   Var N, K : Integer;
       Mas : Array [ 1 .. MaxK ] Of TKomanda;
       Aibe : Array [ 1 .. MaxN ] Of Boolean;

 Procedure Ivesti;
  Var I : Integer;
      B : Text;
 Begin
   FillChar ( Mas, SizeOf ( Mas ), 0 );
   Assign ( B, DuomByla );
   Reset ( B );
   ReadLN ( B, N, K );
   For I := 1 To K Do
    Begin
     ReadLn ( B, Mas [ I ]. Kom, Mas [ I ]. I, Mas [ I ]. J );
    End;
   Close ( B );
   I := 1;
 End;

 Procedure Darbas;
  Var I, J, T : Integer;
      B : Text;
 Begin
  Assign ( B, RezByla );
  ReWrite ( B );
  T := K;
  While T > 0 Do
   Begin
     FillChar ( Aibe, SizeOf ( Aibe ), False );
     For I := 1 To K Do
      If Mas [ I ]. Kom <> #0 Then
      Begin
       Case Mas [ I ]. Kom Of
        'L' : Begin
               If Aibe [ Mas [ I ]. I ] = False Then
                Begin
                 Aibe [ Mas [ I ]. I ] := True;
                 Mas [ I ]. Kom := #0;
                 Dec ( T );
                 WriteLn ( B, I );
                End;
              End;
        'M' : Begin
               If ( Aibe [ Mas [ I ]. I ] = False ) And
                  ( Aibe [ Mas [ I ]. J ] = False ) Then
                  Begin
                   Aibe [ Mas [ I ]. I ] := True;
                   Aibe [ Mas [ I ]. J ] := True;
                   WriteLn ( B, I );
                   Mas [ I ]. Kom := #0;
                   Dec ( T );
                  End;
              End;
        'A' : Begin
               If Aibe [ Mas [ I ]. I ] = False Then
                Begin
                 Aibe [ Mas [ I ]. I ] := True;
                 Mas [ I ]. Kom := #0;
                 WriteLn ( B, I );
                 Dec ( T );
                End;
              End;
        'S' : Begin
                If ( Aibe [ Mas [ I ]. I ] = False ) And
                  ( Aibe [ Mas [ I ]. J ] = False ) Then
                  Begin
                   Aibe [ Mas [ I ]. I ] := True;
                   Aibe [ Mas [ I ]. J ] := True;
                   Mas [ I ]. Kom := #0;
                   WriteLn ( B, I );
                   Dec ( T );
                  End;
              End;
       End;
      End;
     WriteLn ( B, 0 );
   End;
   Close ( B );
 End;

BEGIN
   Ivesti;
   Darbas;
END.{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}

{ Id‚ja:

  Visas keturias komandas galime padalinti  dvi grupes: L ir A - jos atlieka
veiksmus su vienu atminties laukeliu, bei M ir S - jos atlieka veiksmus iž
karto su dviem atminties laukeliais. U‘davinio esm‚ - suskirstyti visas
komndas taip, kad viename bloke nepasitaikyt— komand—, atliekan‡i— veiksmus
su tuo pa‡iu atm. laukeliu. Vadinasi, jeigu operacija su tam tikru laukeliu
X paskutin kart… buvo atlikta bloke Bx, tai tolesnŠ komand…, operuojan‡ia
su laukeliu X, reikia talpinti bloke Bx + 1. Jeigu komanda operuoja iž karto
su dviem laukeliais X ir Y (kaip antai M ir S), su kuriais paskutin kart…
buvo operuota atitinkamai blokuose Bx ir By, tai ži… komand… reikia talpinti
bloke Max(Bx, By) + 1.
  Norint teisingai sugrupuoti komandas  blokus, reikia siminti, kuriame
bloke paskutin kart… buvo atlikta operacija su bet kuriuo atminties laukeliu.
Kadangi komandos bloke turi eiti iž eil‚s, priež ižvedant, jas reikia
sur–žiuoti pagal j— eil‚s numer.

}

program fainas_procas;

const
  max_l = 1000;
  max_k = 10000;

type
  TKomanda = packed record
               blok, num: Integer;
             end;
var
  l: array[1..max_l] of integer;
  k: array[1..max_k+1] of TKomanda;
  nl, nk: Integer;

function max(a, b: Integer): Integer;
begin
  if a > b then max := a else max := b;
end;

procedure skaityk;
var
  f: Text;
  i, a, b, c: Integer;
  kmd: Char;
begin
  assign(f, 'PROG.DAT');
  reset(f);
    readln(f, nl, nk);
    for i := 1 to nk do
    begin
      readln(f, kmd, a, b);
      case kmd of
       'L','A':
         begin
           Inc(l[a]);
           k[i].blok := l[a];
         end
      else
         begin
           c := max(l[a], l[b]);
           inc(c);
           l[a] := c; l[b] := c;
           k[i].blok := c;
         end
      end;
    end;
  close(f);
end;

procedure rusiuok;

  procedure sort(l,r: integer);
  var
    i,j,x: integer;
    y: TKomanda;
  begin
    i:=l; j:=r; x:=k[(l+r) DIV 2].blok;
    repeat
      while k[i].blok<x do i:=i+1;
      while x<k[j].blok do j:=j-1;
      if i<=j then
      begin
        y:=k[i]; k[i]:=k[j]; k[j]:=y;
        i:=i+1; j:=j-1;
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

var
  i: Integer;
begin
  for i := 1 to nk do
    k[i].num := i;
  sort(1,nk);
end;

procedure rasyk;

  procedure sort(l,r: integer);
  var
    i,j,x,y: integer;
  begin
    i:=l; j:=r; x:=k[(l+r) DIV 2].num;
    repeat
      while k[i].num<x do i:=i+1;
      while x<k[j].num do j:=j-1;
      if i<=j then
      begin
        y:=k[i].num; k[i].num:=k[j].num; k[j].num:=y;
        i:=i+1; j:=j-1;
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

var
  f: Text;
  i, j, bl, prad: Integer;
begin
  assign(f, 'PROG.REZ');
  rewrite(f);
    i := 1; bl := 1;
    while i <= nk do
    begin
      { Ižskirti blok… }
      prad := i;
      while k[i].blok = bl do Inc(i);
      sort(prad, i - 1);
      { ­ražome sur–žiuot… blok… }
      for j := prad to i - 1 do
        writeln(f, k[j].num);
      writeln(f, 0);
      { Pereinam prie kito bloko }
      Inc(bl);
    end;
  close(f);
end;

begin
  skaityk;
  rusiuok;
  rasyk;
end.
{­d‚jos apražas:
  mu pirm… komand… saraže ir pa‘ymiu, kokius laukelius ji u‘ima. Tada imu
  antr… komand… ir ‘i–riu ar ji gali veikti, t.y. n‚ra u‘imtas nei vienas jai
  reikalingas laukelis. Jei gali veikti, j… ižspausdinu, jei negali palieku.
  Tas kurias až ižspausdinau ižmetu lauk. Taip pat nagrin‚damas ‘ymiu kokius
  laukelius kieviena komanda u‘ima. Kai per‘i–riu visas komandas, visk…
  pradedu iž naujo t.y. formuoju antr… blok…. Ir taip kol visas komandas
  patikrinu.
  Jei programa veikt— tik taip kaip apražiau, tai ji netilpt—  laik…,
  tam id‚jau papildomus apribojimus. T.y. jei visi laukeliai u‘imti, tai
  toliau sekos nagrin‚ti nebeapsimoka, nes visos komandos operuoja su
  laukeliais, o jie yra jau visi u‘imti. Taip pat d‚jau prad‘ios skai‡iavim….
  Tarkime jei iž eil‚s yra ižmesta 10 element—, tai až juos ižkart
  praleid‘iu. }

program uzd2;
  const MaxKom = 10000;
        MaxLauk = 1000;
        InpF = 'PROG.DAT';
        OutF = 'PROG.REZ';
  Type param = record
                 I, J : word;
                 T : char;
               end;
       laukeliai = array [1..MaxKom] of param;
       uzimti = array [0..MaxLauk] of boolean;
  var n, k : word;
      Lauk : laukeliai;
  Procedure ReadData (Var n, k : Word; Var Lauk : Laukeliai);
    Var f : text;
        x : word;
        s : char;
  begin
    Assign (F, InpF);
    Reset (F);
    Readln (F, n, k);
    FillChar (Lauk, SizeOf (Lauk), 0);
    for x := 1 to k do
      begin
        ReadLn (F, lauk [x].t, lauk [x].i, lauk [x].j);
        if lauk [x].t in ['L', 'A']
           then lauk [x].j := 0;
      end;
    Close (F)
  end;
  procedure Itrauk (Var f : text; var Uzim : uzimti;
                    var p : param; x : word);
  begin
    case p.t of
      'L', 'A': if not uzim [p.i]    { Laukelis naitrauikatas }
              then uzim [p.i] := true
              else exit;
      'M', 'S': if not uzim [p.i] and not uzim [p.j]
              then begin
                     uzim [p.i] := true;
                     uzim [p.j] := true
                   end
              else exit
    end;
    { Jei neuzimti - ispausdiname }
    FillChar (p, SizeOf (P), 0);
    Writeln (f, x);
  end;
  procedure Ieskok (n, k : word);
    var uzm : uzimti;
        kiek : word;
        x : word;
        f : text;
        pr : word;
  begin
    assign (f, OutF);
    rewrite (f);
    pr := 1;
    repeat
      FillChar (uzm, SizeOf (Uzm), 0);
      kiek := 0;
      for x := pr to k do
        if (lauk [x].I <> 0) and (not uzm [Lauk [x].i])
           and (not uzm [lauk [x].j])
           then begin
                  itrauk (f, uzm, lauk [x], x);
                  inc (kiek); { kiek uzimtu laukeliu }
                  if kiek = n
                     then break
                end
           else if kiek = 0
                   then inc (pr);
      if kiek <> 0
         then Writeln (F, '0');
    until kiek = 0;
    close (f)
  end;
begin
  ReadData (n, k, lauk);
  Ieskok (n, k)
end.{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
program LygiagretusSkaiciavimai;
{ VTGTM lic‚jaus             }
{ 3c kurso mokinio           }
{ Lauryno Biveinio           }
{ 2-ojo u‘davinio sprendimas }

{ Sprendimo d‚ja: }
{ Skaitydami instrukcij— sek…, simename, nuo kuri— ankstesni— instrukcij—   }
{ priklauso skaitoma instrukcija (t.y. ankstesn‚s instrukcijos privalo b–ti  }
{ vykdytos iki tos instrukcijos). Tam turime siminti ir tai, nuo kokios    }
{ instrukcijos priklauso bet kurios atminties l…stel‚s reikžm‚. PerskaitŠ    }
{ visas instrukcijas, suskirstome jas  blokus: per‘i–rime visas iž eil‚s    }
{ instrukcijas. ­ blok… eina tik tos instrukcijos, kurios priklauso tik nuo }
{ jau esan‡i— ankstesniuose blokuose. }

const
   MaxN = 1000;
   MaxK = 10000;
   DuomFailoVardas = 'prog.dat';
   RezFailoVardas = 'prog.rez';

var
   N             : 1..MaxN;
   K             : 1..MaxK;
   LaukPr        : array[1..MaxN] of 1..MaxK;
   KomandosPr    : array[1..MaxK, 1..2] of 0..MaxK;
   JauIsvesta,
   JauBusIsvesta : array[0..MaxK] of Boolean;
   DuomFailas    : Text;
   RezFailas     : Text;
   KuriKomanda   : 1..MaxK;
   KiekJau       : 0..MaxK;
   KokiaKomanda  : Char;
   I             : 1..MaxN;
   J             : LongInt;

begin
   Assign(DuomFailas, DuomFailoVardas);
   Reset(DuomFailas);
   ReadLn(DuomFailas, N, K);
   FillChar(LaukPr, SizeOf(LaukPr), 0);
   FillChar(KomandosPr, SizeOf(KomandosPr), 0);
   for KuriKomanda := 1 to K do
      begin
         ReadLn(DuomFailas, KokiaKomanda, I, J);
         KomandosPr[KuriKomanda, 1] := LaukPr[I];
         case KokiaKomanda of
            'L', 'A' : LaukPr[I] := KuriKomanda;
            'M', 'S' : begin
                          KomandosPr[KuriKomanda, 2] := LaukPr[J];
                          LaukPr[I] := KuriKomanda;
                          LaukPr[J] := KuriKomanda
                       end;
         end;
      end;
   Close(DuomFailas);
   FillChar(JauIsvesta, SizeOf(JauIsvesta), 0);
   JauIsvesta[0] := True;
   JauBusIsvesta := JauIsvesta;
   Assign(RezFailas, RezFailoVardas);
   Rewrite(RezFailas);
   KiekJau := 0;
   while KiekJau < K do
     begin
        for KuriKomanda := 1 to K do
          begin
             if (JauIsvesta[KomandosPr[KuriKomanda, 1]]) and
                (JauIsvesta[KomandosPr[KuriKomanda, 2]]) and
                not JauIsvesta[KuriKomanda]
               then begin
                       WriteLn(RezFailas, KuriKomanda);
                       JauBusIsvesta[KuriKomanda] := True;
                       Inc(KiekJau);
                    end;
          end;
        WriteLn(RezFailas, '0');
        JauIsvesta := JauBusIsvesta;
     end;
   Close(RezFailas);
end.
{ Gedimino LukÕio, KTU Gimnazija, 4c, 2 uØdavinys }

{ IdÓja: Nesunku suvokti, kad jei tam tikru momentu galima atlikti kokiÐ }
{ nors operacijÐ, tai jÐ reikia ir atlikti, o ne atidÓti "ateiÑiai", nes }
{ pastaruoju atveju uØsidelstÖ ir visi tolesni operatoriai, kurie nau-   }
{ doja tuos paÑius baitus. Tokiu atveju tikrinamos visos operacijos iÕ   }
{ eilÓs, o tos, kurias galima vykdyti, Ôvykdomos. Net ir neÔvykdØius     }
{ kokios nors operacijos, su tais baitais, kuriuos Øymi ta operacija,    }
{ negalima nieko daryti, nes kitaip b×tÖ paØeistas operacijÖ eiliÕkumo   }
{ principas.                                                             }


{ (¶ia nevertinkite, t.y. Ñia ne idÓja)                                                     }
{ Tiesinis (t.y. ciklÖ) programavimas, ar ne?                            }
{ Vien duoti limitai (1000, 10000) leidØia sprÒsti, kad Ñia joks         }
{ perrinkimas ar pan. negalÓtÖ b×ti...                                   }

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

program Second__;

const
  MaxN = 1000;
  MaxK = 10000;

var
  txt : text;
  N, K : longint;
  Ops : array [1..MaxK, 0..1] of integer;
  Used : array [0..MaxN] of boolean;

procedure ReadData;

  var i, a, b : longint;
      c : char;

  begin
    Assign (txt, 'prog.dat');
    Reset (txt);
    ReadLn (txt, N, K);
    for i := 1 to K do
      begin
        ReadLn (txt, c, a, b);
        case c of
          'L', 'A': begin
                      Ops[i, 0] := a;
                      Ops[i, 1] := 0;
                    end;
          'M', 'S': begin
                      Ops[i, 0] := a;
                      Ops[i, 1] := b;
                    end;
        end;
      end;
    Close (txt);
  end;

procedure Solve;

  var
    Idx, Idx2 : array [1..MaxK] of integer;
    IdxC, IdxC2 : integer;
    i : integer;

  begin
    Assign (txt, 'prog.rez');
    Rewrite (txt);
    IdxC := K;
    for i := 1 to K do
      Idx[i] := i;
    while IdxC > 0 do
      begin
        FillChar (Used, SizeOf(Used), false);
        IdxC2 := 0;
        for i := 1 to IdxC do
          begin
            if not Used[Ops[Idx[i], 0]] and not Used[Ops[Idx[i], 1]]
              then WriteLn (txt, Idx[i])
              else begin
                     Inc (IdxC2);
                     Idx2[IdxC2] := Idx[i];
                   end;
            Used[Ops[Idx[i], 0]] := true;
            if Ops[Idx[i], 1] > 0 then Used[Ops[Idx[i], 1]] := true;
          end;
        WriteLn (txt, 0);
        IdxC := IdxC2;
        Idx := Idx2;
      end;
    Close (txt);
  end;

begin
  ReadData;
  Solve;
end.
{Panevóýio Juozo Balßikonio gimnazijos
10 klasós mokinio Martyno Kriaußiûno
II uýdavinio sprendimas}
{ôDòJA
  Eidamas ciklÝ, paimu vienÝ, dar "neõvykdytÝ", komandÝ. Jeigu atminties
elementai, su kuriais dirba ÷i komanda, dar nenaudoti ÷iame komandù bloke,
tai a÷ "õvykdau" ÷iÝ komandÝ. Radñs pirmÝ komandÝ kurios negaliu "vykdyti",
a÷ pasiýymiu, kad kitÝ kartÝ, kai eisiu ciklÝ, pradóßiau nuo ßia, taip a÷
sutrumpinu programos vykdymo laikÝ.
}
Program Lyg_skai;

  Const Max = 10000;
        Duom_byla = 'Prog.Dat';
        Ats_byla = 'Prog.Rez';

  Type Kom = Record
         K : Char;
         B : Word;
         I : LongInt;
       End;

  Var D : Array [ 1 .. Max ] Of ^Kom;
      N, K : Word;
      L : Array [ 1 .. Max ] Of Boolean;
      Bl : Array [ 1 .. 1000 ] Of Boolean;

  Procedure Ivesk;
    Var I : Word;
        B : Text;
  Begin
    FillChar ( L, SizeOf ( L ), False );
    For I := 1 to Max Do
      New ( D [ I ] );
    Assign ( B, Duom_byla );
    Reset ( B );
    ReadLn ( B, N, K );
    For I := 1 To K Do
      ReadLn ( B, D [ I ]^. K, D [ I ]^. B, D [ I ]^. I );
    Close ( B );
  End;

  Procedure Darbas;
    Var I, J, Nuo, Is : Word;
        B : Text;
        B1, B2 : Boolean;
  Begin
    Assign ( B, Ats_byla );
    ReWrite ( B );
    Nuo := 1;
    Is := 0;
    While Is < K Do
      Begin
        B1 := True;
        FillChar ( Bl, SizeOf ( Bl ), False );
        For I := Nuo To K Do
          Begin
            If L [ I ] Then Continue;
            B2 := False;
            Case D [ I ]^. K Of
              'L' : Begin
                      If Not Bl [ D [ I ]^. B ] Then
                        Begin
                          Bl [ D [ I ]^. B ] := True;
                          B2 := True;
                        End;
                    End;
      'M','A','S' : Begin
                      If ( Not Bl [ D [ I ]^. B ] ) And
                         ( Not Bl [ D [ I ]^. I ] ) Then
                           Begin
                             Bl [ D [ I ]^. B ] := True;
                             Bl [ D [ I ]^. I ] := True;
                             B2 := True;
                           End;
                    End;
            End;
            If B2 Then
              Begin
                WriteLn ( B, I );
                L [ I ] := True;
                Inc ( Is );
              End Else
               If B1 Then
                 Begin
                   Nuo := I;
                   B1 := False;
                 End;
          End;
        WriteLn ( B, 0 );
      End;
    Close ( B );
  End;

Begin
  Ivesk;
  Darbas;
End.{ Vaidas Didvalis
  Gra‘ižki— vidurin‚ mokykla
  12 klas‚
  antras u‘davinys           }

{ Id‚ja.

  Per‘iur‚ti  s…raž… suražytas komandas ir pa‘ym‚ti
  tas, kurios dar nepanaudotos ir joms reikalingi
  atmin ties laukeliai nenaudojami jau pa‘ym‚t—
  komand—. Pa‘ym‚tos komandos eina vien… blok…. Jas
  suražome atskirai, o iž s…ražo ižbraukiame }




program antras;




type atm_l_sk = array [1..1000] of boolean;
     komanda = record
                  kas  : (l, m, a, s);
                  pirm, antr : integer;
                  naudota : boolean
               end;
     kom = array [1..10000] of komanda;
     sarasas = array[1..10001] of integer;



var f: text;
    L_sk, k, x : integer;
    c: char;

    mas : kom;
    sar : ^sarasas;
    sar_ilg: integer;
    lauk : atm_l_sk;
    kiekis : integer;
    pirmasis : integer;
    aibe : atm_l_sk;


function tuscia : boolean;
   var x: integer;
       y : boolean;
begin
y := true;
for x:=1 to L_sk do y := y and not aibe[x];
tuscia  := y;

end;


procedure blokas;
   var x: integer;
begin
sar_ilg := 0;
for x:=1 to L_sk do lauk[x] := false;

for x:=pirmasis to k do
  begin

    if (not mas[x].naudota) and
       (not lauk[mas[x].pirm])
       then
       begin


       if ((mas[x].kas = m) or (mas[x].kas = s)) and not lauk[mas[x].antr]

       then begin
              mas[x].naudota := true;
              lauk[mas[x].pirm] := true;
              lauk[mas[x].antr] := true;
              inc(sar_ilg);
              writeln(f, x);
           end;

       if  (mas[x].kas = l) or (mas[x].kas = a) then
          begin
              mas[x].naudota := true;
              lauk[mas[x].pirm] := true;
              inc(sar_ilg);
              writeln(f, x);
           end;

       end;

  end;

  repeat
   if not mas[pirmasis].naudota then x:= k else inc(pirmasis);

  until x = k;
  writeln(f, 0);

end;




begin
{new(sar);      }



assign (f, 'prog.dat');
reset(f);
Readln(f, L_sk, k);
for x:=1 to k do
   begin

     read(f, c);
     if upcase(c) = 'L' then mas[x].kas := l;
     if upcase(c) = 'M' then mas[x].kas := m;
     if upcase(c) = 'A' then mas[x].kas := a;
     if upcase(c) = 'S' then mas[x].kas := s;
     readln(f, mas[x].pirm, mas[x].antr);
     mas[x].naudota := false;
   end;
close(f);


kiekis := 0;
pirmasis := 1;




assign(f, 'prog.rez');
rewrite(f);


repeat
  blokas;
{  for x:=1 to sar_ilg do
     writeln(f, sar^[x]);
  writeln(f, 0);}
  inc (kiekis, (sar_ilg));
until kiekis = k;
{blok;}
close(f);


{dispose(sar);}

end.{                           Saulius Petrauskas
                       Klaip‚dos ‘uolyno gimnazija
                               10 c klas‚
                                 u‘d. 2                                      }

{ Ÿ u‘davin sprend‘iau taip: prad‘ioje pradiniai duomenys perskaitomi
   masyv…. Po to juos sugrupuoju pagal komandas ir j— svarbum… ( pirma
  ražimas o tik po to sud‚tis). Tada komandas dar kart… pergrupuoju
  pagal tai kad jos nesikirst—. Taip galutinai suružiuojami duomenys.        }

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R-,S+,T-,V+,X+}
{$M 65000,0,655360}
program Lygiagretus;
  var f   : text;
      n, k: word;
      sek: array[1..10000] of record
                                b: byte;
                                i, j: integer;
                                k: 1..4;
                              end;
      x, l: word;
      c   : char;
      p   : word;
      i, j: word;
      kom : byte;
      nul : boolean;

  Function nesikerta: boolean;
  { patikrina ar dvi komandos nesikerta }
    var x: boolean;
  begin
    nesikerta := (i <> sek[l].i) and (j <> sek[l].j) and
                 (i <> sek[l].j) and (j <> sek[l].i)
  end;

  Procedure Skaityk;
  { perskaito pradinius duomenis }
  begin
    readln(f, n, k);
    for x := 1 to k do
    begin
       readln(f, c, sek[x].i, sek[x].j);
       sek[x].b := 0;
       case c of
        'L': sek[x].k := 1;
        'M': sek[x].k := 2;
        'A': sek[x].k := 3;
        'S': sek[x].k := 4
      end
    end
  end;

begin
  assign (f,'prog.dat');
  reset (f);
  skaityk;
  close (f);
  for kom := 1 to 4 do
    for p := 1 to k do
      begin
        for x := 1 to k do
          begin
            if sek[x].k = kom then
              begin
                i := sek[x].i;
                j := sek[x].j;
                for l := 1 to k do
                  begin
                    if sek[l].b = 0 then
                      if nesikerta then
                         sek[l].b := sek[x].b;
                    if (sek[l].b = sek[x].b) and (l <> x) and (x < l) then
                      if (not nesikerta) then
                         sek[l].b := sek[l].b + 1
                  end
              end
          end
      end;
  Assign (f,'prog.rez');
  Rewrite (f);
  for x := 1 to k do
  begin
    nul := false;
    for l := 1 to k do
      if sek[l].b = x then
      begin
        nul := true;
        writeln(f, l)
      end;
    if nul then writeln(f,'0')
  end;
  close (f)
end.{ M.Bir‘ižkos gimnazijos     }
{ 2 GD klas‚s mokinio        }
{ Justo Janausko             }
{ XI informatios olimpiados  }
{ III etapo II dalies        }
{ II u‘davinio sprendimas    }

{ Apražymas
  Komandos turi du parametrus. Jei komanda yra L, mums svarbus
  yra tik antrasis parametras, nes tai yra konstanta, o ne atminties
  l…stel‚. Kit— komand— mums svarb–s abu parametrai - i ir j. Taigi,
  imam pirm… komand… ir dedam  m–s— pirm… blok…. Pasi‘ymim imtos
  komandos parametrus ir ži… komand… ižmetam iž s…ražo. Tada imam
  sekan‡i… komand… ir ‘i–rim ar jos svarb–s parametrai jau buvo panaudoti
  kur nors esan‡iame bloke. Jei ne - darom t… pat kaip su anks‡iau
  apražyta komanda. Jei taip, komand… ignoruojam ir imam sekan‡i… po
  jos. Taip perrenkam visas komandas. Taip sudarytas pirmasis komand—
  blokas. Antr…j blok… sudarin‚jam lygiai taip pat kaip ir pirm…j.
  Tol vykdom program…, kol s…raže nelieka nei vieno bloko.
}

const
  strIn = 'prog.dat';
  strOut = 'prog.rez';

type
  TCommand = record
    c: char;
    i, j: Integer;
  end;
var
  l, k, bc, last: Integer;
  Arr: array [1..10000] of TCommand;
  Block: array [1..1000] of Integer;

procedure ReadData;
var
  f: Text;
  a: Integer;
begin
  Assign(f, strIn);
  Reset(f);
  ReadLn(f, l, k);
  last := 1;
  for a := 1 to k do
  begin
    Read(f, arr[a].c){, arr[a].i, arr[a].j)};
    Read(f);
    ReadLn(f, arr[a].i, arr[a].j);
  end;
  Close(f);
end;

procedure MakeBlock;
var
  used: array[1..1000] of Boolean;
  a: Integer;
  b: Boolean;
begin
  FillChar(used, SizeOf(used), False);
  bc := 0;
  for a := 1 to k do
  begin
    if arr[a].c <> #0 then
    begin
      if arr[a].c in ['L'] then
        b := not used[arr[a].i]
      else
        b := (not used[arr[a].i]) and (not used[arr[a].j]);
      if b then
      begin
        Inc(bc);
        Block[bc] := a;
        if arr[a].c in ['M', 'S', 'A'] then
          used[arr[a].j] := True;
        arr[a].c := #0;
        used[arr[a].i] := True;
      end;
    end;
  end;
end;

procedure Optimize;
var
  f: Text;
  a: Integer;
begin
  Assign(f, strOut);
  Rewrite(f);
  MakeBlock;
  while bc <> 0 do
  begin
    for a := 1 to bc do
      WriteLn(f, Block[a]);
    WriteLn(f, 0);
    MakeBlock;
  end;
  Close(f);
end;

begin
  ReadData;
  Optimize;
end.var f:text;
BEGIN
assign(f,'prog.rez');
writeln(f,'1');
writeln(f,'2');
writeln(f,'6');
writeln(f,'0');
writeln(f,'3');
writeln(f,'0');
writeln(f,'4');
writeln(f,'5');
writeln(f,'0');
END.