Fişierul intrare/ieşire:omizi.in, omizi.outSursă.campion 2005
AutorEmilian MironAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Omizi

Intr-un arbore cu N noduri (numerotate de la 1 la N) s-au urcat M omizi (numerotate de la 1 la M). Ca orice fiinta, si omizile noastre faceau politica, si ca orice politician voiau sa ajunga cat mai sus in ierarhia arborelui, spre cat mai multe frunze verzi si gustoase.
Desi are o gandire simpla, totusi fiecare omida tine foarte mult la orientarea sa politica. Astfel omizile de stanga aleg mereu sa mearga in sus si cat mai la stanga, iar cele de dreapta tot mai sus si cat mai spre dreapta. Spre mirarea biologilor, omizile sunt foarte politicoase. Fiecare omida ocupa o singura functie (nod) in arbore si isi asteapta randul spre promovare. Astfel in fiecare zi se efectueaza cate o promovare, si anume a celei mai inalte in functie omizi care poate urca in ierarhie (are un nod fiu vecin neocupat, prin nod fiu vecin omizile intelegand un nod imediat urmator situat mai sus in arbore). Daca sunt mai multe omizi cu acelasi rang, atunci se trage la sorti. Omida zilei alege unde anume vrea sa urce daca are mai multe posibilitati conform orientarii sale politice.

Cerinta

Pentru a putea evalua pagubele si pentru a mai salva ceva din calea omizilor politice, gradinarul a hotarat sa apeleze la voi pentru a afla care vor fi pozitile omizilor dupa toate promovarile.

Date de Intrare

Pe prima linie a fisierului de intrare omizi.in se gasesc numerele naturale N si M, cu semnificatia din enunt. Pe urmatoarele N linii se afla descrierea arborelui. Mai exact, pe linia i+1 este scrisa lista fiilor nodului i de la stanga la dreapta ca orientare politica, terminata cu numarul 0. Fii sunt separati prin cate un spatiu. Pe urmatoarele M linii se gasesc informatii despre omizi. Mai exact, pe linia N+1+i se afla un numar x si o litera majuscula L separate prin spatiu (x reprezinta numarul nodului in care se afla initial omida i, iar L este orientarea politica a omizii i - S pentru stanga si D pentru dreapta).

Date de Iesire

Fisierul de iesire omizi.out va avea M linii, fiecare continand un numar de la 1 la N. Pe linia i este scrisa pozitia finala a omizii i (dupa toate promovarile).

Restrictii si precizari

  • 3 ≤ N ≤ 16 000
  • 2 ≤ M ≤ N
  • Radacina arborelui este intotdeauna nodul 1
  • Rangul unei omizi este distanta in numar de muchii de la radacina pana la nodul unde este pozitionata.
  • Omizile vor alege intotdeauna nodurile accesibile conform orientarii politice. De exemplu, ordinea preferata pentru o omida ce urmeaza sa fie promovata si care este intr-un nod cu 3 fii, 4, 5 si 6 (de la stanga la dreapta) este 4, 5, 6 pentru o omida de stanga si 6, 5, 4 pentru una de dreapta, aceasta alegand primul fiu care nu este deja ocupat

Exemplu

omizi.inomizi.out
4 2
2 3 0
4 0
0
0
1 S
2 S
2
4
10 5
2 5 9 0
0
8 4 0
0
3 6 7 0
0
10 0
0
0
0
1 D
6 S
7 D
5 S
9 S
7
6
10
8
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content