Fişierul intrare/ieşire:	role.in, role.out	Sursă	Baraj ONI 2007
Autor	Radu Lupsa	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Role

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.

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.

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.

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.

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.

Exemplu

Cum se trimit solutii?