Les Mots Justes – Qualification 2025

Énoncé¶

Dans les documents d'archives que Joseph Nageant avait étudié se trouve toute une section sur la langue parlée dans cette ville engloutie. Bien que Joseph connaisse déjà bien les règles de la langue, il lui arrive encore de commettre quelques erreurs de style.

Pour pouvoir mieux se fondre dans la masse, Joseph tente de perfectionner sa maîtrise de la langue...

Dans cette ville sous-marine, on parle des phrases uniquement composées de mots de 4 lettres, eux-mêmes composés de deux syllabes de deux lettres minuscules.

Pour former une phrase, on choisit deux listes de $N$ bigrammes (les syllabes de deux lettres), la première liste $A$ contenant les possibilités pour commencer un mot, et la seconde liste $B$ contenant les possibilités pour terminer un mot. Les deux listes peuvent contenir des syllabes dupliquées.

On construit alors la phrase comme une liste des $N \times N$ mots, représentant toutes les concaténations possibles d'une syllabe dans la liste $A$, et d'une syllabe dans la liste $B$. En clair, cette liste contient toutes les valeurs possibles de $A_i$ concaténé à $B_j$, pour $1 \leq i, j \leq N$ (la syllabe dans $A$ est toujours concaténée à gauche de la syllabe extraite de $B$).

Par exemple, si on prend comme syllabes de départ les bigrammes ab et ac, et qu'on considère comme syllabes d'arrivée les bigrammes cd et ce, cela forme la phrase (abcd, abce, accd, acce).

Une phrase est dite juste si tous les mots présents dans la phrase ont le même nombre d'occurrences :

• Par exemple, la phrase (cdef, abcd, abcd, cdef) est une phrase juste, car tous les mots sont présents deux fois dans la phrase.
• Au contraire, la phrase (abcd, abcd, bcde) n'est pas juste, car le mot abcd est présent deux fois, alors que le mot bcde n'est présent qu'une fois.

En une correction, Joseph peut soit :

• Ajouter une occurrence du mot de son choix à la phrase, ou
• Supprimer une occurrence du mot de son choix de la phrase.

Étant donnés les listes de syllabes $A$ et $B$, aidez Joseph à trouver le nombre minimal de corrections nécessaires pour rendre sa phrase juste.

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : N, le nombre de syllabes dans chaque liste.
• Sur les lignes suivantes, une liste de N éléments : A, les syllabes de début de mot.
  • Une ligne par élément de la liste : une chaine de 2 caractères.
• Sur les lignes suivantes, une liste de N éléments : B, les syllabes de fin de mot.
  • Une ligne par élément de la liste : une chaine de 2 caractères.

Sortie¶

Afficher, sur une ligne, le nombre de corrections minimal pour rendre la phrase juste.

Contraintes¶

• $1 \le N \le 20$
• Les syllabes sont toujours composées de deux lettres minuscules. ([a-z]{2})

Contraintes de performance¶

• $1 \le N \le 200\,000$