Sugerencia de Palabras
Estás desarrollando un editor de texto con una función de sugerencia de palabras. El objetivo es ofrecer a los usuarios una lista de palabras de uso frecuente basadas en las letras que ya han escrito. Tu tarea consiste en implementar esta función de sugerencia empleando un conjunto de datos de palabras y sus frecuencias.
Se te proporciona una colección de palabras y la cantidad de veces que aparecen en un texto. Para un prefijo de palabra ingresado por el usuario, necesitas generar una lista de hasta 10 palabras que comiencen con dicho prefijo y tengan las mayores frecuencias de aparición. Las palabras se deben ordenar en orden descendente según su frecuencia. Si varias palabras tienen la misma frecuencia, se ordenan lexicográficamente. Si existen más de diez palabras distintas que comiencen con el prefijo, solo debes mostrar las primeras diez.
Entrada
La primera línea de la entrada contiene un número entero
n (1 ≤ n ≤ 10 000), que indica la cantidad de palabras encontradas en los textos.Cada una de las siguientes
n líneas contiene una palabra w_i y un número entero n_i separados por un espacio, donde w_i es una secuencia no vacía de letras minúsculas en alfabeto latino (con una longitud máxima de 15 caracteres), y n_i (1 ≤ n_i ≤ 10^6) es la cantidad de veces que dicha palabra aparece en los textos.Salida
Para cada una de las
m líneas, muestra la lista de palabras más usadas que empiecen con el prefijo u_i correspondiente. Las palabras deben listarse en orden descendente de frecuencia. Si hay palabras con la misma frecuencia, ordénalas lexicográficamente. Si hay más de diez palabras distintas que coincidan con el prefijo, muestra únicamente las primeras diez.Ejemplos
Entrada | Salida |
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