Prologin
2025
É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$