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
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
balls.in
balls.out
Explicatii
rrbrr
bbrb
2
Daca
inseram primele doua bile, consecutiv, între bila 2 si bila 3 se obtin succesiv
configuratiile:
rrbbrr => rrbbbrr => sirul vid
