Sugestão de Palavras
Estás a desenvolver um editor de texto que inclui uma funcionalidade de sugestão de palavras. O objetivo é oferecer aos utilizadores uma lista de termos de uso frequente com base nas letras que já escreveram. A tua tarefa consiste em implementar esta funcionalidade de sugestão, utilizando para isso um conjunto de dados com palavras e as respetivas frequências de ocorrência.
Tens à tua disposição uma coleção de palavras, bem como o número de vezes que cada uma foi encontrada num texto. Para um determinado prefixo de palavra introduzido pelo utilizador, deves gerar uma lista com até 10 palavras que comecem por esse prefixo e que apresentem as maiores frequências de utilização. As palavras devem ser apresentadas por ordem decrescente de frequência. Se existirem várias com a mesma frequência, deves ordená-las lexicograficamente. Caso existam mais de dez palavras distintas que satisfaçam o mesmo prefixo, deves limitar a apresentação apenas às primeiras dez.
Entrada
A primeira linha da entrada contém um número inteiro
n (1 ≤ n ≤ 10 000), que representa o número de palavras encontradas nos textos.
Cada uma das seguintes n linhas contém uma palavra e um inteiro separados por um espaço, onde corresponde a uma sequência não vazia de letras latinas minúsculas com comprimento até 15 caracteres, e () indica o número de vezes que a palavra aparece nos textos.A linha seguinte contém um número inteiro
m (1 ≤ m ≤ 5000), que indica o número de prefixos de palavra introduzidos pelo utilizador.
Cada uma das próximas m linhas apresenta uma palavra (uma sequência não vazia de letras latinas minúsculas com comprimento até 15 caracteres), que representa o início de uma palavra fornecida pelo utilizador.Saída
Para cada um dos
m prefixos, deves apresentar uma lista das palavras mais usadas que comecem pelo prefixo correspondente . As palavras devem ser ordenadas por frequência de utilização (da maior para a menor). Em caso de frequências iguais, a ordenação é feita de forma lexicográfica. Se existirem mais de dez palavras diferentes que correspondam ao mesmo prefixo, deves apresentar apenas as primeiras 10.Exemplos
Entrada | Saída |
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