Analyse Fréquenstèle – Épreuve régionale 2023

Niveau 2

Énoncé

L'architecte ayant terminé ses occupations, il indique aux aventuriers de précieuses informations leur permettant de se repérer dans le temps. Supposant qu'il s'agissait simplement d'un problème de précision lors du placement du dernier point de contrôle, Valérian et Oscar tentent alors d'effectuer un déplacement relatif pour arriver à la bonne année. Oscar consulte de nouveau son manuel, effectue les calculs d'encodage, et indique à Valérian la combinaison à effectuer pour arriver à l'année désirée. L'indicateur temporel s'agite, puis s'arrête à nouveau, mais l'année indiquée n'est toujours pas compréhensible. Seraient-ils alors toujours en Antiquité ? Pendant que Valérian et Oscar continuent leurs investigations sur la cause de ces erreurs, les autres jeunes ressortent de la machine pour évaluer leur avancée temporelle.

Les jeunes tombent alors sur un court morceau de texte, assez mal écrit, gravé à la va-vite sur une petite stèle. Quelques lettres en haut de la stèle font apparaître le nom d'Euclide. Alors, les jeunes se mettent en quête de déchiffrer le contenu de la stèle pour y relever des indices sur la date à laquelle ils ont atteri.

Julie connaît en effet un moyen très astucieux de déchiffrer le texte: une analyse de fréquence ! Elle sait que chaque caractère de la stèle correspond à un caractère latin, juste très mal écrit. En comptant le nombre de caractères du texte gravé, elle connaît également le nombre attendu d'occurences de chacun des caractères.

À partir du contenu de la stèle, et d'une liste de 26 éléments contenant le nombre de fois que la lettre A est attendue, puis le nombre de fois que la lettre B est attendue, et ainsi de suite, aidez Julie à déchiffrer le contenu de la stèle !

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de caractères gravés sur la stèle.
  • Sur la ligne suivante, une liste de N lettres minuscules juxtaposées ([a-z]) : contenu, le texte gravé sur la stèle.
  • Sur la ligne suivante, une liste de 26 entiers séparés par des espaces : occurences, la liste contenant les nombres d'occurrences des lettres de A à Z.

Sortie

Une chaîne de caractères contenant le texte déchiffré.

Contraintes

  • Tous les éléments non-nuls de la liste occurences sont distincts
  • $1 \le N \le 50$

Contraintes de performance

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

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
28
hbbbbttttoootttzzqqqqqqmmmmm
0 0 0 0 0 0 2 0 6 0 0 3 0 5 7 1 0 4 0 0 0 0 0 0 0 0
Exemple de sortie
PRRRROOOOLLLOOOGGIIIIIINNNNN
Commentaire

Le texte gravé sur la stèle est composé de 28 caractères. L'analyse fréquentielle indique que le message déchiffré doit comprendre:

  • 0 fois la lettre A
  • 0 fois la lettre B
  • ...
  • 2 fois la lettre G
  • 6 fois la lettre I
  • 3 fois la lettre L
  • 5 fois la lettre N
  • 7 fois la lettre O
  • 1 fois la lettre P
  • 4 fois la lettre R

Dans le texte gravé, on observe que le caractère $h$ n'est présent qu'une fois. Il doit donc correspondre à la lettre $P$. Ensuite, on se rend compte que le caractère $b$ est présent 4 fois, il doit donc correspondre à la lettre $R$. En substituant les lettres ainsi de suite, on obtient PRRRROOOOLLLOOOGGIIIIIINNNNN

Exemple d'entrée
17
ybkqqybkqqybbbbbb
4 0 0 0 0 0 0 0 8 0 2 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0
Exemple de sortie
PIKAAPIKAAPIIIIII
Commentaire

Le texte gravé sur la stèle comporte 17 caractères. On remarque qu'il comporte 8 fois le caractère $b$, 4 fois le caractère $q$, 3 fois le caractère $y$ et 2 fois le caractère $k$. L'analyse fréquentielle nous indique que le contenu déchiffré doit contenir 4 fois la lettre $A$, 8 fois la lettre $I$, 2 fois la lettre $K$ et 3 fois la lettre $P$. Le contenu déchiffré doit donc être PIKAAPIKAAPIIIIII.