Fişierul intrare/ieşire:weeee.in, weeee.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorFlorin ChiricaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inweeee.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?