Создание игры Zuma
Вы решили создать игру Zuma. Сейчас вы работаете над этапом, который удаляет последовательные сегменты шариков одного цвета, когда они сталкиваются друг с другом. У нас есть список шариков разных цветов, и игрок выстреливает шариком определённого цвета в заданную позицию этой линии. Если в результате получается более двух шариков одного цвета подряд (включая тот, которым выстрелили), весь этот сегмент исчезает, а шары по бокам заполняют освободившееся пространство.
Если после этого три и более шариков одинакового цвета снова оказываются подряд, этот сегмент тоже исчезает. Процесс повторяется до тех пор, пока соседние сегменты не окажутся разных цветов или пока шары не закончатся совсем.
Входные данные
Первая строка входных данных содержит единственную строку
b (1 ≤ |b| ≤ ), описывающую шары в линии. Цвета шариков задаются строчными латинскими буквами (y для жёлтого, b для синего, r для красного и т.д.).Следующая строка содержит индекс
i (1 ≤ i ≤ |b|), в который пользователь совершает выстрел, и цвет шарика c (строчная латинская буква).Выходные данные
Программа должна вывести итоговую последовательность шариков.
Примеры
Входные данные | Выходные данные |
rrryyrrb
4 y | b |
rgbbrg
3 b | rgrg |
ggrrrbbb
1 g | rrrbbb |
gbyw
1 y | ygbyw |
cabbbacc
4 b | caacc |
Пояснение
- rrryyrrb → rrr
yyyrrb → rrrrrb → b
- rgbbrg → rg
bbrg → rgrg
- ggrrrbbb →
gggrrrbbb → rrrbbb (дополнительных столкновений после этого не возникло)
- gbyw →
ygbyw (цвета не совпадают ⇒ шарик вставляется в позицию, куда был сделан выстрел)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB