Wortvorschlag
Sie entwickeln gerade einen Texteditor mit einer Funktion zur automatischen Wortvorschlag. Ziel ist es, den Nutzerinnen und Nutzern eine Liste häufig verwendeter Wörter anzuzeigen, die auf den bereits eingegebenen Buchstaben basieren. Ihre Aufgabe ist es, diese Wortvorschlags-Funktion mithilfe eines Datensatzes zu implementieren, der aus Wörtern und deren Häufigkeiten besteht.
Ihnen liegt eine Sammlung von Wörtern sowie die jeweilige Häufigkeit ihrer Verwendung vor. Für ein vom Benutzer eingegebenes Wortpräfix sollen Sie eine Liste von bis zu 10 Wörtern erzeugen, die mit diesem Präfix beginnen und die höchsten Verwendungsfrequenzen aufweisen. Die Wörter müssen absteigend nach ihrer Häufigkeit sortiert sein. Bei gleichen Häufigkeiten erfolgt die Sortierung lexikografisch. Falls mehr als zehn verschiedene Wörter mit dem angegebenen Präfix beginnen, geben Sie nur die ersten zehn aus.
Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl
n (1 ≤ n ≤ 10 000), die Zahl der in den Texten gefundenen Wörter.Jede der folgenden
n Zeilen enthält ein Wort und eine ganze Zahl , getrennt durch ein Leerzeichen. Dabei ist eine Folge von Kleinbuchstaben (maximal 15 Zeichen), die nicht leer ist, und () gibt an, wie oft dieses Wort in den Texten vorkam.Ausgabe
Für jede der
m Zeilen sollen Sie eine Liste der am häufigsten verwendeten Wörter ausgeben, die mit dem jeweiligen Präfix beginnen. Die Ausgabe erfolgt absteigend nach Häufigkeit. Bei gleichen Häufigkeiten wird lexikografisch sortiert. Gibt es mehr als zehn verschiedene Wörter, die mit diesem Präfix anfangen, so sind nur die ersten 10 anzugeben.Beispiele
Eingabe | Ausgabe |
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