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

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