balls

Se considera urmatorul joc:
Initial, jucatorul are la dispozitie un sir de bile negre si rosii, asezate īntr-o ordine oarecare īn partea de sus a ecranului. Un dispozitiv de tragere mobil este plasat īn partea de jos a ecranului. Dispozitivul lanseaza bile (negre si rosii) care sunt inserate īn sirul initial, succesiunea bilelor fiind cunoscuta. Presupunand ca, la un moment dat, sirul bilelor este compus din n bile, o bila lansata de dispozitivul de tragere poate fi inserata īn sir īntre bila 1 si bila 2, īntre bila 2 si bila 3,…, sau īntre bila n-1 si n, asa cum se observa īn figura de mai jos.


Figura 1
Daca sirul contine o singura bila, inserarea unei alte bile se poate face īn dreapta acesteia.
Daca īn sirul de bile, īn urma unei inserari, apar grupuri de cel putin trei bile consecutive de aceeasi culoare atunci acestea dispar, iar bilelor ramase li se aplica din nou aceasta regula.
Pentru configuratia din figura 1, o posibilitate de inserare a bilelor este urmatoarea:
Pasul 1. Inserez prima bila (rosie) īntre bila 3 si bila 4:

Figura 2
Pasul 2. Inserez a doua bila (rosie) īn dreapta singurei bile ramase īn sir:
Pasul 3. Inserez a treia bila (neagra) īntre bila 1 si bila 2:

Figura 3

Cerinta

Scrieti un program care sa determine numarul minim de bile ce trebuie sa fie lansate astfel īncāt sirul initial de bile sa devina vid sau, īn cazul īn care acest lucru nu este posibil, se vor determina toate sirurile de bile de lungime minima ce se pot obtine prin lansarea tuturor bilelor disponibile īn dispozitivul de lansare.

Date de intrare

Fisierul balls.in contine pe prima linie un sir de caractere ce descrie sirul initial de bile, caracterul b reprezentānd o bila de culoare neagra, iar caracterul r reprezentānd o bila de culoare rosie. Pe cea de a doua linie se afla un sir de caractere ce descrie succesiunea īn care sunt lansate bilele din dispozitivul de tragere, caracterul b reprezentānd o bila de culoare neagra, iar caracterul r reprezentānd o bila de culoare rosie.

Date de iesire

Īn fisierul balls.out se va scrie pe prima linie numarul minim de bile ce trebuie lansate pentru a transforma sirul initial īn sirul vid, daca acest lucru este posibil. In caz contrar, in fisierul de iesire se vor scrie toate sirurile de bile de lungime minima ce se pot obtine prin lansarea tuturor bilelor disponibile din dispozitivul de lansare, cate un sir pe o linie, īn ordine lexicografica.


Restrictii

Suma dintre numarul bilelor din sirul initial si numarul bilelor din dispozitivul de lansare este un numar natural īntre 2 si 13.

Exemple

balls.in balls.out Explicatii balls.in balls.out Explicatii
rbbrrb
rrb 		rbr
rrb 		Prima solutie se obtine conform explicatiilor din enunt.
A doua solutie se obtine astfel:
-inseram prima bila īntre bila 1 si bila 2 => rrbbrrb
-inseram a doua bila īntre bila 1 si bila 2 =>rrrbbrrb => bbrrb
-inseram a treia bila īntre bila 1 si bila 2=>bbbrrb => rrb
 		rrbrr
bbrb 		2
 Daca inseram primele doua bile, consecutiv, īntre bila 2 si bila 3 se obtin succesiv configuratiile:
rrbbrr => rrbbbrr => sirul vid

Timp maxim de executie/test: 1 secunda
Memorie totala disponibila: 70 MB, din care 6 MB pentru stiva.

prof. Alin Burta
Colegiul National "B.P. Hasdeu" Buzau
Contact: allbu2003@yahoo.com