Ouroboros – Qualification 2024

Level 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$

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4
5
Rostheim
Adaheim
Pascalheim
Fortrheim
AMRAC
Sample output
Adaheim
Fortrheim
Pascalheim
Rostheim
Note

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
Sample input
6
6
Nixheim
Haskelheim
Cobolheim
Prologheim
Delpheim
Modulheim
MMAACC
Sample output
Nixheim
Haskelheim
Delpheim
Modulheim
Cobolheim
Prologheim
Note

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.

Sample input
2
2
Lispheim
Erlangheim
RM
Sample output
Lispheim
Note

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

Submit your solution

You have to register or log in to be able to submit your solution.