Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-04-18 19:35:55.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:pitici5.in, pitici5.outSursăInfoarena Monthly 2014, Runda 4
AutorAndrei Cristian LambruAdăugată demaritimCristian Lambru maritim
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pitici5

Intr-o padure traiesc doua tipuri de pitici: albi si negri. Ei doresc sa se aseze in sir indian. Din pacate pentru ei fiecare pitic are o pretentie si anume vrea sa vada in fata lui ori un pitic alb, ori un pitic negru. Cum ei sunt foarte incapatanati vor sa gaseasca o asezare care sa respecte aceasta conditie, dar cum ei nu stiu informatica va roaga pe voi sa ii ajutati cu mentiunea ca va vor oferi 100 de puncte daca veti reusi.

Cerinta

Fiind dat numarul N de pitici si pe rand cate un pitic, in ordinea in care se afla acum (ei au apucat sa se alinieze in sir indian si apoi si-au dat seama ca unii dintre ei au anumite pretentii), trebuie sa gasiti o asezare posibila care respecta toate restrictiile de mai sus si in plus, daca se dau tuturor piticilor numere de ordine crescatoare consecutive pornind de la 1 in care se afla initial (cu alte cuvinte primul pitic primeste numarul de ordine 1, al doilea pitic numarul de ordine 2, al treilea numarul 3 si asmd), aceasta asezare sa fie minima lexicografica dupa indicii acestia. Se mai stie ca primul pitic este de culoare G si nu se afla printre piticii initiali si mai mult decat atat nu are nicio pretentie.

Date de intrare

Fişierul de intrare pitici5.in contine pe prima linie valoarea N, reprezentand numarul de pitici si un caracter G ce reprezinta culoarea primului pitic care va ramane primul si dupa reordonare, ceilalti urmand sa se aseze in spatele lui. Aceast caracter va avea fie valoarea 'A', ce va insemna ca primul pitic are culoarea alba, fie valoarea 'B' ceea ce va inseamna ca acesta va avea culoarea neagra.

Pe urmatoarele N linii se vor afla exact doua caractere separate prin cate un spatiu. Fiecare din aceste perechi vor fi informatiile corespunzatoare fiecarui pitic. Primul caracter va pastra culoarea pe care vrea sa o aiba piticul din fata sa, iar cel de-al doilea caracter va pastra culoarea proprie a piticului respectiv. 

Date de ieşire

În fişierul de ieşire pitici5.out se va afisa pe prima si singura linie o permutare a primelor N numere naturale ce va reprezentarea reordonarea primelilor N pitici astfel incat sa se respecte restrictiile celor N pitici, iar reasezarea sa fie minima lexicografica.

Restricţii

  • 1 ≤ N ≤ 100 000

Exemplu

pitici5.inpitici5.out
6 A
N N
A A
N A
A N
N N
A N
2 4 1 3 6 5

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?