France-IOI – Sujet 1 (A)
France-IOI » Concours » TaupIC 2011 » Sujet 1 (A)
supercaillou 2021
cameleon13 2021
11 h 26
couzin 2021
melodye52gmailcom 2021
Sujet 1 (A)
Une des manières les plus triviales de crypter un message consiste à remplacer chaque lettre d'un message par la suivante dans l'ordre alphabétique (en remplaçant le `z` par un `a`). Une méthode légèrement plus complexe consiste à associer à chaque lettre de l'alphabet une lettre image, de manière bijective, et à envoyer le message obtenu en remplaçant chaque lettre par son image, dans le message d'origine. On peut complexifier encore un peu le processus en considérant une bijection non-pas sur l'ensemble des lettres, mais sur l'ensemble des paires de lettres : on découpe le message par paires de lettres successives (appelées "bigrammes"), et on envoie à la place de chaque bigramme son bigramme image par la bijection choisie.
Quand la bijection porte directement sur les lettres de l'alphabet, une personne qui intercepte le message sans connaître la permutation peut tout de même essayer de le décrypter par une analyse fréquentielle : si le message original est en français et que sa longueur est suffisante, on peut facilement deviner, pour commencer, quelle lettre est l'image de la lettre `e`, car on sait que la fréquence d'apparition de la lettre `e` en français est autour de 16%, largement au dessus des autres. On cherche donc une lettre dans le message crypté dont la fréquence est proche de 16%, et on en déduit qu'elle correspond à la lettre `e` dans le message original.
Dans le cas où ce sont les bigrammes qui sont cryptés, la même méthode fonctionne aussi. En français, le bigramme le plus fréquent est "es" avec une fréquence de 3,15% (la moyenne étant autour de 0,15%).
On donne une chaîne de caractères message (de lettres minuscules non-accentuées). Calculer le nombre d'occurrences du bigramme (paire de lettres successives) le plus fréquent dans cette chaîne.
Par exemple, dans la chaîne "abaab", "ab" apparaît 2 fois, "ba" apparaît une fois et "aa" apparaît une fois. Le plus fréquent est "ab", et son nombre d'occurrences est 2, il faut donc répondre 2.
L'entrée contient la chaîne de caractères message, suivie d'un retour à la ligne.
La sortie est le nombre d'occurrences du bigramme le plus fréquent, suivi d'un retour à la ligne.
touteproprietenontrivialesurleslangagesrecursivementenumerablesestindecidable