Vis-à-vis Linguistique – Épreuve régionale 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$