Prévision Rotationnelle 3 – Épreuve régionale 2023

Niveau 6

Énoncé

Estimant être dans une année Préhistorique, les six jeunes font chacun une estimation du nombre d’années à remonter pour retourner dans le présent. Ils calculent ensuite la moyenne des estimations, encodent l’année grâce à l’outil du mathématicien, effectuent la combinaison de leviers adéquate, et mettent en route la machine. L’estimation n’étant pas assez précise, ils arrivent à une époque qui commence à leur être familière, mais pas tout à fait à notre présent. Possiblement au début du ⅹⅹe siècle ? Les jeunes sortent alors de la machine pour essayer de trouver la date exacte du jour, afin de pouvoir effectuer leur dernier voyage temporel et rentrer chez eux.

En sortant de la machine, Julie demande la date et sa position au premier passant qu'ils rencontrent. "Bletchley Park, 1943", en plein milieu de la Seconde Guerre Mondiale ! Voyant toute l'ingénieurie derrière l'étonnante machine depuis laquelle vous venez de sortir, le passant vous demande votre aide pour travailler sur sa propre machine : une certaine machine qui servirait à déchiffrer les messages Allemands.

Il est connu que les messages sont chiffrés en utilisant une combinaison secrète de rotations. L'objectif est alors de tenter d'effectuer plusieurs séries de rotations sur le message initial. Le message initial est une suite de N nombres : $1, 2, 3, 4, ..., N-1, N$

Une rotation se caractérise par l'échange des deux nombres situés à deux positions différentes. Par exemple, la rotation 6 2 échange les nombres situés en 2e et 6e position. Effectuée sur le message original, pour $N = 8$, cela donnerait $1, 6, 3, 4, 5, 2, 7, 8$.

L'ingénieur vous indique alors une séquence précise de rotations, rotations, à effectuer sur le message initial. Ensuite, Q fois, il 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'une nouvelle rotation. C'est simplement une modification de la liste rotations.

Pour chaque mutation dans la liste mutations, il est nécessaire d'appliquer la modification en question dans la liste des rotations, puis d'afficher le résultat de l'application de toutes les rotations en partant du message initial.

La liste rotations n'est pas réinitialisée avant chaque mutation. En revanche, le message initial est toujours $1, 2, 3, 4, ..., N-1, N$ après chaque mutation.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre d'éléments contenus dans le message.
  • Sur la ligne suivante, un entier : M, le nombre de rotations.
  • Sur les lignes suivantes, une liste de M éléments : rotations, la liste des rotations initiales.
    • Une ligne par élément de la liste : séparés par des espaces, un entier depart (la position de départ du nombre qui tourne), et un entier arrivee (la position d'arrivée du nombre qui tourne).
  • 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.
    • Chaque élément de la liste est sur plusieurs lignes : une struct mutation.
      • Sur la première ligne, un entier : position, la position de la rotation qui mute.
      • Sur la ligne suivante, séparés par des espaces, un entier depart (la position de départ du nombre qui tourne), et un entier arrivee (la position d'arrivée du nombre qui tourne) : nouvelle rotation, la nouvelle rotation à effectuer.

Sortie

Après chaque mutation, afficher le résultat de toutes les rotations sur la liste initiale.

Contraintes

  • $1 \le N \le 10$
  • $1 \le M \le 100$
  • $1 \le Q \le 100$
  • $1 \le \text{depart}, \text{arrivee} \le N$
  • $1 \le \text{position} \le M$
  • $1 \le \text{nouveau depart}, \text{nouvelle arrivee} \le N$

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
4
3
1 3
2 4
3 4
3
1
1 3
1
2 3
2
3 4
Exemple de sortie
3 4 2 1
1 4 3 2
1 3 2 4
Commentaire

La première mutation remplace la première rotation par 1 ↔ 3. La première rotation étant déjà 1 ↔ 3, cela ne change pas la liste des rotations. Si nous appliquons ces rotations sur le message initial, nous obtenons :

    Rotation     Message
$1, 2, 3, 4$
1 ↔ 3 $3, 2, 1, 4$
2 ↔ 4 $3, 4, 1, 2$
3 ↔ 4 $3, 4, 2, 1$

Nous devons donc afficher 3 4 2 1 sur la première ligne.

La deuxième mutation remplace la première rotation par 2 ↔ 3. Les trois rotations à appliquer sont donc 2 ↔ 3, puis 2 ↔ 4, puis 3 ↔ 4.

Si nous appliquons ces rotations sur le message initial, nous obtenons :

    Rotation     Message
$1, 2, 3, 4$
2 ↔ 3 $1, 3, 2, 4$
2 ↔ 4 $1, 4, 2, 3$
3 ↔ 4 $1, 4, 3, 2$

Nous devons donc afficher 1 4 3 2 sur la deuxième ligne.

Enfin, la troisième mutation remplace la deuxième rotation par 3 ↔ 4. Les trois rotations à appliquer sont donc 2 ↔ 3, puis 3 ↔ 4, puis 3 ↔ 4.

Si nous appliquons ces rotations sur le message initial, nous obtenons :

    Rotation     Message
$1, 2, 3, 4$
2 ↔ 3 $1, 3, 2, 4$
3 ↔ 4 $1, 3, 4, 2$
3 ↔ 4 $1, 3, 2, 4$

Nous devons donc afficher 1 3 2 4 sur la troisième ligne.

Exemple d'entrée
7
3
2 2
2 3
5 4
2
2
2 4
1
1 2
Exemple de sortie
1 4 3 5 2 6 7
2 4 3 5 1 6 7
Commentaire

La première mutation remplace la deuxième rotation par 2 ↔ 4. Les trois rotations à appliquer sont donc 2 ↔ 2, puis 2 ↔ 4, puis 5 ↔ 4. Si nous appliquons ces rotations sur le message initial, nous obtenons :

    Rotation     Message
$1, 2, 3, 4, 5, 6, 7$
2 ↔ 2 $1, 2, 3, 4, 5, 6, 7$
2 ↔ 4 $1, 4, 3, 2, 5, 6, 7$
5 ↔ 4 $1, 4, 3, 5, 2, 6, 7$

Nous devons donc afficher 1 4 3 5 2 6 7 sur la première ligne.

La seconde mutation remplace la première rotation par 1 ↔ 2. Les trois rotations à appliquer sont donc 1 ↔ 2, puis 2 ↔ 4, puis 5 ↔ 4.

Si nous appliquons ces rotations sur le message initial, nous obtenons :

    Rotation     Message
$1, 2, 3, 4, 5, 6, 7$
1 ↔ 2 $2, 1, 3, 4, 5, 6, 7$
2 ↔ 4 $2, 4, 3, 1, 5, 6, 7$
5 ↔ 4 $2, 4, 3, 5, 1, 6, 7$

Nous devons donc afficher 2 4 3 5 1 6 7 sur la deuxième ligne.