Dernière pièce – Qualification 2022

Énoncé¶

Après avoir traversé les dimensions, Joseph Marchand se retrouve face à une porte gigantesque. Cependant, ce n'est pas une porte normale : il s'agit d'un puzzle. Pour ne pas arranger les choses, les pièces ne ressemblent en rien à des pièces de puzzle ordinaire. Ce sont des polygones de toutes sortes ! Triangles, rectangles, octogones et j'en passe... Mais bonne nouvelle : il est presque terminé, il ne manque plus qu'une pièce. Dans un coin au sol se trouve de nombreuses pièces, l'une d'entre elle pourrait bien lui permettre de terminer ce puzzle.

En plus de chercher une pièce avec le bon nombre de côtés, il faut également que la pièce soit d'une couleur différente de celles des pièces adjacentes.

Déjà fatigué par son saut inter-dimensionnel, Joseph Marchand souhaite transporter le moins de pièces possible. Il lui faut donc identifier les pièces qui pourraient potentiellement convenir pour ne déplacer que ces dernières. Aide-le à ouvrir la porte rapidement !

Entrée¶

L'entrée contiendra :

• Sur la première ligne, un entier : nCouleurs, le nombre de couleurs.
• Sur les lignes suivantes, une liste de nCouleurs éléments : couleurs, les différentes couleurs possibles.
  • Une ligne par élément de la liste : une chaine de caractères.
• Sur la ligne suivante, un entier : nCotes, le nombre de côtés de la pièce manquante.
• Sur les lignes suivantes, une liste de nCotes éléments : couleurscotes, les couleurs des pièces adjacentes à la pièce manquante.
  • Une ligne par élément de la liste : une chaine d'au maximum 10 caractères.
• Sur la ligne suivante, un entier : nPieces, le nombre de pièces à trier.
• Sur les lignes suivantes, une liste de nPieces éléments : pieces, les pièces à trier.
  • Chaque élément de la liste est sur plusieurs lignes : une struct structpiece.
    • Sur la première ligne, un entier : nCotesPiece, le nombre de cotes de la pièce.
    • Sur la ligne suivante, une chaine d'au maximum 10 caractères : couleurPiece, la couleur de la pièce.

Sortie¶

Affiche sur la première ligne pour chaque pièce un caractère :

• 'O' si la pièce peut correspondre à celle recherchée
• 'X' sinon.

Sur la ligne suivante, le nombre de pièces qui peuvent correspondre.

Contraintes¶

• $0 \le nCouleurs$
• $0 \le nCotes$
• $0 \le nPieces$
• $couleur[ ] \in {b, j, o, r, v}$