== include(page="template/taskheader" task_id="role") ==
Poveste si cerinta...
Gigel este mare fan al muzicii anilor '70. El are o colectie impresionanta de benzi magnetice cu melodiile compuse in acea perioada. Tehnica folosita in acea perioada poate parea rudimentara in zilele noastre, insa Gigel doreste sa reconstituie cat mai mult din atmosfera epocii.
Fiecare melodie este inregistrata pe o banda magnetica; benzile sunt numerotate de la $1$ la {$N$}. Fiecare banda este infasurata pe cate o rola din plastic, iar Gigel mai dispune de o rola goala. Rolele sunt numerotate de la $0$ la {$N$}, fiecare banda avandu-si locul pe rola cu acelasi numar, iar rola $0$ fiind rola goala.
Cand Gigel asculta o melodie, magnetofonul deruleaza banda de pe rola ei si o infasoara pe rola goala; la final banda se gaseste pe rola ce initial era goala, bobinata invers, adica cu inceputul benzii in centrul rolei, iar rola pe care se gasea initial banda devine goala. Gigel are intotdeauna grija ca, dupa ce asculta o melodie, sa rebobineze banda inapoi pe rola ei. Fratele mai mic al lui Gigel este mai dezordonat si lasa adesea banda pe rola pe care ajunge in urma ascultarii. El foloseste apoi rola proaspat eliberata pe post de rola goala pentru a asculta urmatoarea melodie. Astfel, dupa o vreme, multe dintre benzi se gasesc pe alta rola decat cea proprie, si unele benzi sunt bobinate invers, adica inceputul melodiei este in interiorul infasurarii (trebuind derulate inainte de-a putea fi ascultate).
Gigel doreste acum sa restabileasca ordinea, aducand fiecare banda pe rola ei si bobinata cu inceputul in exterior. In acest scop el poate executa o secventa de operatii. La o operatie el poate doar sa ia o rola si sa deruleze banda de pe ea pe singura rola ce este goala in acel moment, banda inversandu-si cu aceasta ocazie sensul de bobinare.
h2. Cerinta
Se cere sa se determine o secventa minima de operatii in urma carora fiecare banda ajunge pe rola cu numarul egal cu numarul benzii si infasurata cu inceputul in exterior.
h2. Date de intrare
...
Fisierul de intrare $role.in$ va contine pe prima linie un numar natural $N$ reprezentand numarul de benzi. Pe urmatoarele $N$ linii se gasesc cate doua numere naturale separate printr-un spatiu, $R$ si {$I$}. A {$k$}-a pereche descrie pozitia benzii cu numarul {$k$}: $R$ reprezinta numarul rolei pe care se afla banda {$k$}, iar $I$ are valoarea $0$ daca banda este infasurata normal (cu inceputul in exterior) si $1$ daca este infasurata invers.
h2. Date de iesire
...
Fisierul de iesire $role.out$ va contine o secventa de numere naturale, cate un numar pe o linie pe linie. Numarul de pe linia $i$ reprezenta numarul rolei de pe care se muta banda pe rola goala la cea de a {$i$}-a operatie executata.
h2. Restrictii
* $... ≤ ... ≤ ...$
* {$1 ≤ N ≤ 100 000$}
* Pe o rola poate exista cel mult o banda la un moment dat.
* Pentru toate datele de test va exista o solutie care necesita cel putin o operatie.
* Punctaj
** Pentru solutie optima se acorda $100%$ din punctaj.
** Daca solutia nu este optima, dar este corecta, se vor acorda punctaje partiale dupa cum urmeaza:
*** daca diferenta dintre numarul de operatii executate de concurent si numarul optim de operatii este mai mica sau egala decat $10%$ din numarul optim (parte intreaga), se acorda $60%$ din punctaj;
*** daca diferenta dintre numarul de operatii executate de concurent si numarul optim de operatii este mai mare decat $10%$ din numarul optim (parte intreaga), se acorda $20%$ din punctaj.
h2. Exemplu
table(example). |_. role.in |_. role.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
1 0
0 1
| 0
|
h3. Explicatie
...
| 3
2 0
0 1
3 1
| 3
2
1
3
2
0
|
== include(page="template/taskfooter" task_id="role") ==
== SmfTopic(topic_id="...") ==
