Prologin
2025
ENONCE
On s'intéresse à un programme de reconnaissance vocale.
Le but est de partir d'une suite de phonèmes enregistrés pour arriver à un mot connu.
Pour cela, l'on vous fournit un graphe orienté de transitions. Chaque état est numéroté par un nombre entre 0 et N-1 (N \<= 100), et l'on vous fournit une liste de ses voisins, via des arcs étiquetés par un phonème et par une probabilité de transition (en fait, ce sera ici un score entier, pour éviter les problèmes d'arrondis).
Pour chaque phonème (qui sera représenté par un caractère ASCII), en partant d'un état donné, on peut se rendre sur ceux des états voisins qui sont reliés à l'état courant par un arc étiqueté par le phonème en question. Le score d'un chemin est la somme des scores des arêtes qui le composent (en fait, des produits de probabilités).
L'on vous donne un sommet/état de départ et une liste de phonèmes enregistrés. Vous devez donner le sommet d'arrivée le plus probable, c'est à dire l'extrémité d'un chemin de score maximal étiqueté par le mot enregistré. (S'il y en a plusieurs possibles, retournez le sommet dont le numéro est le plus petit).
ENTREE
Le nombre N sur la première ligne.
Le numéro de l'état initial sur la deuxième.
Un nombre M sur la troisième ligne, et sur les M lignes suivantes, deux entiers i et j, un caractère ASCII c, et un score s, séparés par des espaces et représentant une transition i->j étiquetée par le phonème c avec le score (la probabilité de transition, en fait) f.
Sur la dernière ligne, le mot à lire, d'un maximum de 100 lettres, et qui peut être constitué de tous les caractères ASCII sauf '\n'.
SORTIE
Le numéro de l'état final tel que défini plus haut, suivi d'un saut de ligne.