Quart de Singe – Épreuve régionale 2022

Énoncé¶

Le clown du Mulet offre à Bayta de révéler l'identité de son maître. L'information n'est cependant pas gratuite. Il adore jouer avec les lettres, et lui propose donc une partie de quart de singe télépathique. Il est sûr de sa victoire, et laisse donc Bayta commencer. Vous devez aider Bayta à gagner.

Les règles du jeu sont les suivantes :

• Les joueurs ajoutent une lettre chacun leur tour afin de former un mot

• Le premier qui ne peut plus ajouter de lettre a perdu

• La liste de tous les mots possibles est instantanément partagée par la pensée

Voici une liste possible de mots :

1
2
3

TERMINUS
TRANTOR
PSYCOHISTOIRE

Si Bayta choisit T, le clown peut choisir E, et ainsi assurer sa victoire: c'est lui qui dira la dernière lettre de TERMINUS. Cependant, si Bayta choisit P, elle dira la dernière lettre de PSYCOHISTOIRE et gagnera.

Dans certains cas, aucune lettre ne permet de gagner à coup sûr, mais le clown joue au feeling, et n'établit pas de stratégie. Il choisit parmi les lettres possibles de manière équiprobable, tandis vous tentez de maximiser les chances de gagner pour Bayta.

Bayta ne veut pas avoir à vérifier plusieurs sorties, donc si deux lettres ont la même probabilité (à $10^{-3}$ près), il faut donner la première lettre dans l'ordre alphabétique.

Enfin, dans certaines situations, il est impossible de gagner. Il faut alors afficher 0.

On notera que les mots donnés n'existent pas forcément, et qu'ils sont uniquement composés de lettres latines (non-accentuées) en majuscule.

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : N, Le nombre de mots autorisés.
• Sur les lignes suivantes, une liste de N éléments : mots, La liste des mots autorisés.
  • Une ligne par élément de la liste : une chaine de 256 caractères maximum.

Sortie¶

La première lettre à donner pour avoir le plus de chance de gagner.

Contraintes¶

• $1 \le N \le 10$

Contraintes de performance¶

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