Création du jeu Zuma
Vous avez décidé de créer le jeu Zuma. Vous êtes actuellement en train de travailler sur la partie qui supprime les segments de billes ayant la même couleur lorsqu’ils entrent en collision. Ainsi, vous avez une liste de billes de différentes couleurs, et le joueur tire une bille d’une certaine couleur à un emplacement précis dans cette file. Si l’on obtient un segment de plus de deux billes de la même couleur (en comptant la bille tirée par le joueur), ce segment disparaît, et les billes qui l’entourent se rapprochent pour combler l’espace vacant.
Si 3 billes ou plus se rencontrent et ont la même couleur, ce segment disparaît à son tour. Ce processus se répète jusqu’à ce que les segments qui se touchent soient de couleurs différentes ou qu’il n’y ait plus de billes.
Entrée
La première ligne de l’entrée contient une chaîne de caractères unique
b (1 ≤ |b| ≤ ) qui représente les billes dans la file. Les couleurs des billes sont représentées par des lettres minuscules de l’alphabet latin (y pour jaune, b pour bleu, r pour rouge, etc.).La ligne suivante contient l’indice
i auquel le joueur tire une bille et la couleur c de cette bille (lettre minuscule de l’alphabet latin).Sortie
Le programme doit afficher la séquence de billes résultante.
Exemples
Input | Output |
rrryyrrb
4 y | b |
rgbbrg
3 b | rgrg |
ggrrrbbb
1 g | rrrbbb |
gbyw
1 y | ygbyw |
cabbbacc
4 b | caacc |
Explication
- rrryyrrb → rrr
yyyrrb → rrrrrb → b
- rgbbrg → rg
bbrg → rgrg
- ggrrrbbb →
gggrrrbbb → rrrbbb (aucune collision entre segments après cela)
- gbyw →
ygbyw (les couleurs ne correspondent pas ⇒ on insère simplement la bille à l’indice prévu)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB