Diferente pentru problema/pitici5 intre reviziile #5 si #25

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="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.
Intr-o padure traiesc doua tipuri de pitici: de culoare $alba$ si de culoare $neagra$. Ei doresc sa se aseze in sir indian, dar din pacate fiecare pitic are o pretentie si anume vrea sa vada in fata lui un pitic de o anume culoare, ori alba, ori neagra. Cum ei sunt foarte incapatanati, vor sa gaseasca o asezare care sa respecte pretentiile fiecaruia dintre ei. Cum niciunul nu stie algoritmica va roaga pe voi sa le scrieti un program prin care sa generati pentru ei o astfel de asezare. Ei au mentionat ca daca veti reusi sa ii ajutati va vor oferi 100 de puncte.
h1. 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.
Se stie ca piticii sunt numerotati cu valori distincte de la $1$ la $N$, unde $N$ reprezinta si numarul lor. Se da pe rand fiecare pitic de la numarul $1$ la numarul $N$ in ordine si se cere sa gasiti o asezare posibila care respecta toate restrictiile de mai sus si in acelasi timp sirul valorilor, obtinut dupa reasezarea piticilor, sa fie minim lexicografic.
 
Se mai stie ca primul pitic este de culoare $C$, are numarul de ordine $0$ si nu se afla printre piticii initiali, iar mai mult decat atat nu are nicio pretentie.
h2. 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.
Fişierul de intrare $pitici5.in$ contine pe prima linie valoarea $N$, reprezentand numarul de pitici si un caracter $C$ ce reprezinta culoarea primului pitic care va ramane primul si dupa reasezare, ceilalti urmand sa se aseze in spatele lui. Acest caracter va avea fie valoarea $'A'$, ce va insemna ca primul pitic are culoarea $alba$, fie valoarea $'N'$ 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.
Pe urmatoarele $N$ linii se vor afla exact doua caractere separate prin cate un spatiu. Fiecare din aceste perechi de caractere vor fi informatiile corespunzatoare fiecarui pitic. Primul caracter va pastra culoarea pe care vrea sa o aiba piticul in fata sa, iar cel de-al doilea caracter va pastra culoarea proprie a piticului respectiv.
h2. 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.
În fişierul de ieşire $pitici5.out$ se va afisa pe prima si singura linie o permutare a primelor $N$ numere naturale. Aceasta permutare va reprezenta reordonarea celor $N$ pitici astfel incat sa se respecte toate restrictiile descrise mai sus.
h2. Restricţii
* $1 ≤ N ≤ 100 000$
* Se garanteaza ca intotdeauna exista o asezare posibila astfel incat sa se respecte restrictiile celor $N$ pitici.
* Spunem că un sir A=(a ~1~,a ~2~,..,a ~N~) este mai mic lexicografic decât un sir B=(b ~1~, b ~2~,..,b ~N~) dacă există o poziţie p astfel încât x ~p~ < y ~p~ şi x ~1~ = y ~1~, x ~2~ = y ~2~,..., x ~p-1~ = y ~p-1~.
h2. Exemplu
h3. Explicaţie
Sunt posibile si alte reordonari care respecta restrictiile, dar nu sunt minime lexicografic. O alta posibila reordonare era $2 4 1 5 3 6$ .
Primul pitic din sir este deja fixat si are culoarea $alba$. Urmatorii $N$ pitici se vor reaseza in felul urmator: cel de-al $doilea$ pitic va fi $primul$, cel de-al $patrulea$ pitic va deveni al $doilea$, $primul$ pitic va fi al $treilea$ si asa mai departe... Sirul pozitiilor initiale, rezultat dupa asezarea minima lexicografica, care respecta toate restrictiile celor $N$ pitici este $2 4 1 3 6 5$. Mai sunt posibile si alte reasezari ale piticilor (de exemplu $2 4 1 5 3 6$), dar sirurile asociate acestor reasezari nu sunt minime lexicografic.
== include(page="template/taskfooter" task_id="pitici5") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
9810