| Fişierul intrare/ieşire: | weeee.in, weeee.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 16 |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Weeee
Micutul B urmeaza sa spuna primul sau cuvant. Mama lui tot repeta "Hai B, stiu ca primul tau cuvant va fi mami". Tatal lui B crede ca primul cuvant spus de acesta va fi "Tati". Cand in sfarsit B vorbeste, el spune doar atat: WEEEEEEEEEEE. Ambii parinti sunt dezamagiti de el, asa ca decid sa nu mai vorbeasca cu el. Suparat, B se duce la locul sau de joaca.
El are cuburi pe care scrie cate o litera. Suparat, el arunca toate cuburile pe care sunt inscriptionate alte litere in afara de W si E. Apoi, aseaza cuburile in linie. Scopul jocului sau este sa formeze un cuvant cat mai lung din cuburile ramase (cele care contin literele W sau E). Din pacate, el stie numai un cuvant: un cuvant care incepe cu litera W si apoi este format numai din E-uri. El vrea sa formeze cuvantul cu lungimea maxima posibila. Astfel, scopul sau este sa formeze o subsecventa a cuburilor care incepe cu W si care contine apoi toti E-ii din cuburi.
Singura operatie admisa a jocului sau este sa aleaga 2 cuburi adiacente si sa le interschimbe. Gasiti numarul minim de interschimbari astfel incat sa existe o subsecventa a cuburilor care sa inceapa cu W si sa contina apoi toti E-ii, sau micutul B va incepe sa planga :(
Date de intrare
Fişierul de intrare weeee.in va contine pe prima linie numarul N, reprezentand lungimea sirului de cuburi. A doua linie a fisierului contine sirul de cuburi, privit de la stanga la dreapta. Pentru fiecare dintre cele N cuburi va fi scrisa litera W sau E, corespunzatoare literei inscriptionate pe cubul respectiv.
Date de ieşire
În fişierul de ieşire weeee.out se va afisa un singur numar, reprezentand numarul minim de interschimbari astfel incat sa existe o subsecventa care sa inceapa cu W si sa contina apoi toti E-ii sirului initial. Pentru ca o subsecventa sa fie un cuvant valid, ea trebuie sa contina un W si minim un E. In cazul in care nicio subsecventa nu se poate forma, se va afisa -1.
Restricţii
- 1 ≤ N ≤ 200000
- Cititi cu atentie ce scrie in "Date de iesire", pentru a nu ne da un #MLC ulterior!
- Numele problemei contine exact 4 caractere "e"
- Micutul B intre timp s-a facut mare, dar tot ii place cuvantul WEEEEEE
Exemplu
| weeee.in | weeee.out |
|---|---|
| 7 WEEEEWE | 1 |
Explicaţie
Vom interschimba penultimul si ultimul cub. Acum, subsecventa care incepe de pe pozitia 1 si are lungime 6 va incepe cu litera W si va contine toti E-ii sirului initial. Asta va duce la fericirea micutului B.
