Prevision Rotationnelle 1 – Épreuve régionale 2023

Niveau 3

Énoncé

Avec les informations tout juste récupérées, Valérian commence à se poser des questions sur l'encodage des nombres qu'Oscar lui indiquait, avant de se rendre compte qu'Oscar lisait le manuel d'instructions de sa machine à laver ! (qui bien sûr ne suit pas le même système d'encodage pour la température que notre machine pour l'année…) Personne ne se souvenant du système d'encodage exact, les jeunes vont désespérément tenter de retourner au présent pour récupérer le manuel d'instructions… Même sans connaître l'encodage, ils savent que grâce au mode relatif, ils ne peuvent qu'avancer dans le temps. Alors Valérian décide de faire une combinaison aléatoire pour voir où ça les mène.

Les jeunes sortent alors de leur machine à voyager dans le temps et tombent nez à nez avec ce qui semble être un mathématicien Perse des années 1400. Il affirme être en train de rechercher une nouvelle méthode ingénieuse pour calculer les décimales de pi. Il commence par tracer un cercle, puis il place une quantité paire N de nombres allant de 1 à N, dans cet ordre et équitablement espacés sur le contour du cercle, en partant de 1 en haut de celui-ci. Ensuite, il sait qu'il doit effectuer une suite de rotation précise qu'il cherche encore à découvrir.

Rotations

Il existe trois types de rotations :

  • La rotation gauche, G : chaque nombre présent sur le cercle prend la place du nombre situé immédiatement à sa gauche. Sur la situation initiale pour $N = 8$ par exemple, effectuer cette rotation et citer les nombres présents sur le cercle depuis le haut donnerait 2, 3, 4, 5, 6, 7, 8, 1.
  • La rotation droite, D : chaque nombre présent sur le cercle prend la place du nombre situé immédiatement à sa droite. Sur la situation initiale pour $N = 8$ par exemple, effectuer cette rotation et citer les nombres présents sur le cercle depuis le haut donnerait 8, 1, 2, 3, 4, 5, 6, 7.
  • La division, S : chaque nombre présent sur le cercle prend la place du du nombre situé à l'opposé de celui-ci. Sur la situation initiale pour $N = 8$ par exemple, effectuer cette rotation et citer les nombres présents sur le cercle depuis le haut donnerait 5, 6, 7, 8, 1, 2, 3, 4.

Le mathématicien affirme vouloir offrir aux jeunes aventuriers une de ses dernières inventions s'ils parviennent à l'aider correctement.

Il indique à nos aventuriers une séquence précise de rotations, rotations, à effectuer sur le cercle initial. Ensuite, Q fois, il leur indique un changement précis à effectuer sur la séquence de rotations, une mutation. Les Q mutations sont indiquées dans la liste mutations. Une mutation prend la forme d'une position et d'un type de rotation. C'est simplement une modification de la liste rotations.

Pour chaque mutation dans la liste mutations, il demande à ce que nos amis appliquent la modification en question sur la liste des rotations, puis qu'ils lui indiquent en retour le résultat de l'application de toutes les rotations ainsi modifiées, dans l'ordre, en partant du cercle initial.

La liste rotations n'est pas réinitialisée avant chaque mutation. En revanche, les nombres présents sur le cercle initial sont toujours 1, 2, 3, 4, ..., N-1, N en partant du haut après chaque mutation.

Aidez nos aventuriers à effectuer ces calculs !

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, la quantité de nombres à positionner sur le cercle.
  • Sur la ligne suivante, un entier : M, le nombre de rotations.
  • Sur la ligne suivante, une liste de M caractères juxtaposés : rotations, la liste des rotations initiales.
  • Sur la ligne suivante, un entier : Q, le nombre de mutations.
  • Sur les lignes suivantes, une liste de Q éléments : mutations, la liste des mutations à effectuer et évaluer.
    • Une ligne par élément de la liste : séparés par des espaces, un entier position (la position de la rotation qui mute), et un caractère type (la nouvelle rotation à effectuer).

Sortie

Après chaque mutation, afficher sur une ligne le résultat de l'application de toutes les rotations sur le cercle initial, cela sous la forme de $N$ nombres séparés par un espace : les $N$ nombres que l'on croise dans l'ordre en partant du haut du cercle.

Contraintes

  • $2 \le N \le 10$
  • $N$ est garanti pair
  • $1 \le M \le 100$
  • $\text{rotations}_i = D, G, \text{ou } S$
  • $1 \le Q \le 100$

Pour chaque mutation :

  • $1 \le \text{position} \le M$
  • $\text{type} = D, G, \text{ou } S$

Contraintes de performance

  • $1 \le M \le 100\,000$
  • $1 \le Q \le 100\,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
8
3
DSD
2
1 G
3 G
Exemple de sortie
5 6 7 8 1 2 3 4
7 8 1 2 3 4 5 6
Commentaire

À l'issue de la première mutation, qui remplace la première rotation par une rotation gauche, la liste rotations est [G, S, D]. En appliquant ces trois rotations et en énumérant après chaque rotation les nombres trouvés sur le cercle en partant du haut, on obtient :

1
2
3
4
  | 1, 2, 3, 4, 5, 6, 7, 8
G | 2, 3, 4, 5, 6, 7, 8, 1
S | 6, 7, 8, 1, 2, 3, 4, 5
D | 5, 6, 7, 8, 1, 2, 3, 4

Le résultat attendu après la première mutation est donc 5 6 7 8 1 2 3 4.

À l'issue de la seconde mutation, qui remplace la troisième rotation par une rotation gauche, la liste rotations est [G, S, G]. En appliquant ces trois rotations, on obtient :

1
2
3
4
  | 1, 2, 3, 4, 5, 6, 7, 8
G | 2, 3, 4, 5, 6, 7, 8, 1
S | 6, 7, 8, 1, 2, 3, 4, 5
G | 7, 8, 1, 2, 3, 4, 5, 6

Le résultat attendu après la seconde mutation est donc 7 8 1 2 3 4 5 6.

Exemple d'entrée
2
4
GGSD
3
1 G
3 D
3 S
Exemple de sortie
1 2
1 2
1 2
Commentaire

À l'issue de la première mutation, qui remplace la première rotation par une rotation gauche, la liste rotations est [G, G, S, D]. Cela n'impacte en effet pas la liste des rotations, qui comportait déjà une rotation gauche comme première rotation. En appliquant ces quatre rotations, on obtient :

1
2
3
4
5
  | 1, 2
G | 2, 1
G | 1, 2
S | 2, 1
D | 1, 2

Le résultat attendu après la première mutation est donc 1 2.

À l'issue de la deuxième mutation, qui remplace la troisième rotation par une rotation droite, la liste rotations devient [G, G, D, D]. En appliquant ces quatre rotations, on obtient :

1
2
3
4
5
  | 1, 2
G | 2, 1
G | 1, 2
D | 2, 1
D | 1, 2

Le résultat attendu après la deuxième mutation est donc également 1 2.

À l'issue de la dernière mutation, qui remplace la troisième rotation par une division, la liste rotations redevient [G, G, S, D]. Le résultat attendu après la troisième mutation est le même qu'après la première mutation, soit 1 2.