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 |
rbr |
Първото
решение е
обяснено в
текста на
задачата. |
rrbrr |
2 |
Ако
вмъкнем
първите две
топки
последователни
между топки 2
и 3,
получаваме
следното: |
Time
limit: 1
сек/тест
Разрешена
памет 70
MB,
от които
6
MB
за стек
prof.
Alin Burta
"B.P. Haşdeu"
Contact: allbu2003@yahoo.com
Превод
на български:
Емил
Келеведжиев