Prologin
2024
Énoncé¶
Jøsëf Marchand se retrouve à Asgard. Cependant, il a beaucoup de mal à comprendre les dieux. En effet, ces derniers n'utilisent pas d'espace pour séparer leurs mots…
Le langage des dieux n'utilise que les deux caractères ( et ).
Un mot est dit opposable si :
- Sa taille est paire ;
- La première moitié du mot est le reflet de la seconde moitié du mot. C'est à dire que la première moitié du mot ne partage aucun caractère en commun avec la seconde moitié du mot, inversée.
Par exemple, le mot ())()()(() est opposable, car la première moitié
est le reflet de la seconde : ())() ()(().
Autrement dit, la première moité, ())(), ne partage aucun caractère avec la
seconde moitié lue de droite à gauche, )(()(.
Les mots du langage des dieux sont toujours opposables.
Étant donné une phrase divine, aidez Jøsëf Marchand à la décomposer en mots,
en lui indiquant la taille de chacun des mots.
S'il est impossible de décomposer la phrase en une séquence de mots opposables,
alors indiquez IMPOSSIBLE.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, la taille de la phrase.
- Sur la ligne suivante, une liste de N caractères juxtaposés : phrase, la phrase divine à analyser.
Sortie¶
S'il est possible de décomposer la phrase en une séquence de mots opposables,
proposer une décomposition en affichant la taille des mots, séparés par un
espace. Sinon, afficher IMPOSSIBLE.
Si plusieurs solutions existent, afficher n'importe laquelle d'entre elles.
Contraintes¶
- $1 \le N \le 40$
- $sequence[i] \in \{(, )\}$
Contraintes de performance¶
- $1 \le N \le 100\,100$