Quart de Singe – Regional event 2022

Level 4

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

Runtime constraints

Maximum memory usage
500000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
3
TERMINUS
TRANTOR
PSYCOHISTOIRE
Sample output
P
Sample input
3
TERMINUS
TRANTOR
PSYCOHISTOIRES
Sample output
T
Sample input
7
ABE
ACD
ACEF
BCB
BDB
BEB
BF
Sample output
A
Sample input
4
AAAA
AAA
AA
A
Sample output
0
Sample input
2
B
A
Sample output
A

Submit your solution

You have to register or log in to be able to submit your solution.