Suggestion de mots
Vous êtes en train de développer un éditeur de texte doté d’une fonctionnalité de suggestion de mots. L’objectif est de proposer aux utilisateurs une liste de mots couramment utilisés, en se basant sur les lettres qu’ils ont déjà saisies. Votre mission consiste à implémenter cette fonctionnalité de suggestion à l’aide d’un ensemble de mots et de leurs fréquences.
On vous fournit une collection de mots ainsi que le nombre de fois où ils apparaissent dans un texte. Pour un préfixe saisi par l’utilisateur, vous devez générer une liste pouvant contenir jusqu’à 10 mots qui commencent par ce préfixe et qui présentent les fréquences d’apparition les plus élevées. Les mots doivent être triés par ordre décroissant de fréquence. S’il y a des mots avec la même fréquence, on les classe par ordre lexicographique. S’il existe plus de dix mots commençant par le préfixe indiqué, vous ne devez afficher que les dix premiers.
Entrée
La première ligne des données contient un entier
n (1 ≤ n ≤ 10 000), qui représente le nombre de mots trouvés dans les textes.
Chacune des n lignes suivantes contient un mot et un entier séparés par un espace, où est une séquence non vide de lettres minuscules (alphabet latin) d’une longueur maximale de 15 caractères, et () est le nombre de fois où ce mot apparaît dans les textes.La ligne suivante contient un entier
m (1 ≤ m ≤ 5000), qui indique le nombre de préfixes saisis par les utilisateurs.
Chacune des m lignes suivantes contient un mot (une séquence non vide de lettres minuscules, avec une longueur maximale de 15 caractères), qui correspond au début d’un mot saisi par un utilisateur.Sortie
Pour chacune des
m lignes, affichez la liste des mots les plus fréquemment utilisés qui commencent par le préfixe correspondant . Les mots doivent être présentés dans l’ordre décroissant des fréquences. Si des mots ont la même fréquence, triez-les par ordre lexicographique. S’il y a plus de dix mots différents commençant par le préfixe, affichez uniquement les dix premiers.Exemples
Entrée | Sortie |
6
fire 2
walk 2
with 2
me 2
fierce 1
win 3
3
fi
w
wi | fire
fierce
win
walk
with
win
with |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB