Предсказание слов
Вы разрабатываете текстовый редактор с функцией подсказки слов. Цель состоит в том, чтобы предоставлять пользователям список наиболее часто употребляемых слов на основе уже набранных ими букв. Ваша задача — реализовать такую функцию подсказки, используя заданные слова и частоты их появления в тексте.
У вас есть коллекция слов и количество раз, которое каждое слово встречается в тексте. Для заданного префикса, введённого пользователем, нужно сформировать список не более чем из 10 слов, начинающихся с этого префикса и обладающих наибольшим количеством вхождений. Слова следует упорядочить по убыванию частоты. Если у нескольких слов одинаковая частота, их нужно отсортировать лексикографически. Если существует более десяти разных слов, которые начинаются с данным префиксом, выводите только первые десять.
Входные данные
В первой строке входных данных содержится целое число
n (1 ≤ n ≤ 10 000), обозначающее количество слов, найденных в текстах.В каждой из следующих
n строк указаны слово и целое число , разделённые пробелом, где — непустая последовательность строчных латинских букв длиной не более 15 символов, а (1 ≤ n_i ≤ 10^6) — количество появлений этого слова в тексте.Выходные данные
Для каждой из
m строк выведите список наиболее часто встречающихся слов, начинающихся с соответствующего префикса . Слова должны быть отсортированы по убыванию частоты. Если некоторые слова имеют одинаковую частоту, их нужно упорядочить лексикографически. Если существует более десяти различных слов, начинающихся с данным префиксом, необходимо выводить только первые 10.Пример
Входные данные | Выходные данные |
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