balls

Разглеждаме следната игра:
В началото играчът има един ред, съставен от черни и червени топки, случайно подредени. Редът се намира в горната част на екрана. В долната част на екрана има устройство, което изстрелва черни и червени топки, които се наместват между топките на горния ред. Известна е последователността от черни и червени топки, които устройството изстрелва. В началото горният ред е съставен от n топки и топките, изстрелвани от устройството може се вмъкват между позиции от началния ред с номера 1 и 2, 2 и 3, ..., n-1 и n, както е показано на рисунката:


Fig. 1

 

Ако началният ред се състои от една топка, изтреляната топка попада в дясно.

Ако след някое вмъкване, се окаже, че има 3 или повече последователни топки от един и същ цвят, тогава те всички изчезват.

За конфигурацията от Fig. 1 играчът е възможно да осъществи следната последователност от действия:
Стъпка 1. Вмъква първата топка (червена) между топки
3 и 4:


Fig. 2

 

Стъпка 2. Вмъква втората топка (червена) отдясно:
Стъпка 3. Вмъква третата топка (
черна) между топки 1 и 2:


Fig. 3

Задача

Напишете програма, която намира най-малкия брой топки, които трябва да бъдат изстреляни така, че началният ред да стане празен. Ако това не е възможно, програмата трябва да намери минималната дължина до която може да се сведе началният ред, ако бъдат изстреляни всичките топки, заредени в изстрелващото устройство.

Вход

Файлът balls.in съдържа в първия си ред низ от знаци, описващи топките в началния ред. Вторият ред на файла съдържа низ от знаци, описващи последователността, в която устройството изстрелва топките. И в двата низа знакът b представя черна топка, а знакът r – червена.

Изход

Файлът balls.out трябва да съдържа търсения минимален брой топки, след чието изстрелване началният ред става празен, ако това е възможно. Ако това не е възможно, файлът трябва да съдържа в последователните си редове всички редове от топки с минимална дължина, които могат да се получат след изстрелване на всичките топки от устройството. Тези редове трябва да са подредени лексикографски.

Ограничения

Сумата от броя на топките в началния ред и в устройството е цяло число между 2 и 13.

Примери

balls.in

balls.out

Пояснение

balls.in

balls.out

 

rbbrrb
rrb

rbr
rrb

Първото решение е обяснено в текста на задачата.
Второто решение се получава по следния начин:
-
вмъкваме първата топка между топки 1 и 2 => rrbbrrb
-
вмъкваме втората топка между топки 1 и 2 =>rrrbbrrb => bbrrb
-
вмъкваме третата топка между топки 1 и 2 =>bbbrrb => rrb

rrbrr
bbrb

2

Ако вмъкнем първите две топки последователни между топки 2 и 3, получаваме следното:
rrbbrr => rrbbbrr => празен ред

Time limit: 1 сек/тест
Разрешена памет  70 MB, от които 6 MB за стек

prof. Alin Burta
"B.P. Haşdeu" Buzău National High School

Contact: allbu2003@yahoo.com

Превод на български: Емил Келеведжиев