Ouroboros – Qualification 2024

Niveau 3 ⋅ Validation weight: 10%

Énoncé

Jörmungandr est un serpent légendaire qui entoure tout Midgard, en passant par certaines villes, jusqu'à se mordre sa queue. Les villes rencontrées en partant de la queue de Jörmungandr jusqu'à sa tête sont données en entrée dans une liste de chaînes de caractères. Sa tête — et donc sa queue, qui se situent au même endroit car il se mord la queue — se trouvent toujours entre deux villes. Initialement, elles se situent entre la dernière ville listée et la première (souvenez-vous que la liste décrit un cycle), et Jörmungandr avance de gauche à droite dans la liste.

Dans $M$ années aura lieu le Ragnarök. Chaque année jusqu'au Ragnarök, Jörmungandr prend l'une des actions suivantes :

  • A: Avancer d'une ville de manière circulaire dans la liste ;
  • M: Manger la ville la plus proche devant sa tête ;
  • R: Se retourner, ce qui signifie qu'il avancera alors dans la direction opposée par la suite. S'il avançait de gauche à droite, il avance alors de droite à gauche, et inversement ;
  • C: Recracher la dernière ville qu'il a mangé et qu'il n'a pas encore recraché, pour la placer devant sa tête.

Notez donc que si, après s'être retourné, Jörmungandr se dirige de droite à gauche dans la liste, il mangerait alors la ville située immédiatement à gauche de sa tête.

Skuld, Norne du futur, vous indique les actions prochaines de Jörmungandr pour les $M$ prochaines années. Aidez Jøsëf Marchand à prédire l'état final des villes lors du Ragnarök, en les listant dans l'ordre en partant de sa queue jusqu'à sa tête.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de villes autour de Midgard.
  • Sur la ligne suivante, un entier : M, le nombre d'années avant le Ragnarök.
  • Sur les lignes suivantes, une liste de N éléments : villes, le nom des villes autour de Midgard, en partant de la queue de Jörmungandr.
    • Une ligne par élément de la liste : une chaine non-vide de 10 caractères ascii ou moins.
  • Sur la ligne suivante, une liste de M caractères juxtaposés : actions, la liste des actions prochaines de Jörmungandr.

Sortie

Afficher, sur une ligne par ville, la liste des villes qui seront rencontrées lors du Ragnarök, dans l'ordre, en partant de la queue de Jörmungandr jusqu'à sa tête.

Contraintes

  • $2 \le N \le 10$
  • $1 \le M \le 10$
  • $\mathtt{actions} \in \{A, C, M, R\}^M$
  • On vous garantit qu'à tout moment, il restera au moins une ville présente dans Midgard. Aussi, Jörmungandr n'essaiera jamais de recracher une ville si toutes les villes sont présentes dans Midgard.
  • On vous garantit que toutes les villes ont un nom différent.

Contraintes de performance

  • $2 \le N \le 100\,000$
  • $1 \le M \le 2\,000\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
5
Rostheim
Adaheim
Pascalheim
Fortrheim
AMRAC
Exemple de sortie
Adaheim
Fortrheim
Pascalheim
Rostheim
Commentaire

La situation décrit quatre villes autour de Midgard par lesquelles passe Jörmungandr : Rostheim, Adaheim, Pascalheim et Fortrheim :

situation initiale

Initialement, la tête et la queue de Jörmungandr se situent entre les villes de Fortrheim et de Rostheim. Le Ragnarök se déroulera dans 5 ans, alors, Jörmungandr aura le temps d'effectuer 5 actions :

Il commencera par avancer d'une ville :

action 1

Alors, sa tête se situera entre Rostheim et Adaheim.

Ensuite, il mangera la ville située juste après sa tête, c'est à dire Adaheim :

action 2

Alors, sa tête se situera entre Rostheim et Pascalheim.

Ensuite, il se retournera :

action 3

Sa tête se dirigera alors vers Rostheim.

Ensuite, il avancera d'une ville, cette fois-ci dans l'autre sens car il s'est retourné :

action 4

Sa tête se situera alors entre Rostheim et Fortrheim.

Enfin, il recrachera la dernière ville qu'il a ingéré, c'est à dire Adaheim, juste en face de sa tête, c'est à dire entre Rostheim et Fortrheim. Alors, au moment du Ragnarök, sa tête se situera entre Rostheim et Adaheim.

position finale

En partant de sa queue et en listant les villes rencontrées le long de son corps, on obtiendrait alors :

  • Adaheim
  • Fortrheim
  • Pascalheim
  • Rostheim
Exemple d'entrée
6
6
Nixheim
Haskelheim
Cobolheim
Prologheim
Delpheim
Modulheim
MMAACC
Exemple de sortie
Nixheim
Haskelheim
Delpheim
Modulheim
Cobolheim
Prologheim
Commentaire

Jörmungandr commence par manger en premier lieu la ville de Nixheim, puis la ville de Haskelheim. Après s'être déplacé jusque entre les villes de Prologheim et Delpheim, il recrachera d'abord la ville de Haskelheim (qui est la dernière ville à s'être faite manger), puis la ville de Nixheim.

Devant lui se situera alors la ville de Nixheim, qui est donc citée en premier dans le résultat.

Exemple d'entrée
2
2
Lispheim
Erlangheim
RM
Exemple de sortie
Lispheim
Commentaire

Ici, Jörmungandr se retournera et mangera Erlangheim, sans jamais la recracher. Il ne restera donc plus que Lispheim au moment du Ragnarök.