Suggerimento di Parole
Stai sviluppando un editor di testo dotato di una funzionalità per suggerire le parole. L’obiettivo è fornire agli utenti un elenco di termini di uso frequente sulla base delle lettere che hanno già digitato. Il tuo compito consiste nell’implementare questa funzionalità di suggerimento usando un dataset di parole e le rispettive frequenze di utilizzo.
Ti viene fornita una raccolta di termini insieme al numero di volte in cui appaiono in un testo. Per un dato prefisso inserito dall’utente, devi generare un elenco composto al massimo da 10 parole che iniziano con quel prefisso e che presentano le frequenze d’uso più alte. L’ordine di visualizzazione deve essere decrescente in base alla frequenza; in caso di frequenze uguali, le parole vanno disposte in ordine lessicografico. Se esiste più di un gruppo di 10 parole differenti con lo stesso prefisso, devi mostrare solo le prime dieci.
Input
La prima riga dell’input contiene un intero
n (1 ≤ n ≤ 10 000), che rappresenta il numero di parole trovate nei testi.Ciascuna delle successive
n righe contiene una parola e un intero separati da uno spazio. Qui è una sequenza non vuota di lettere minuscole latine, di lunghezza massima 15 caratteri, e () è il numero di volte in cui il termine compare nei testi.Output
Per ognuna delle
m righe, occorre visualizzare l’elenco delle parole più frequenti che iniziano con il prefisso . Le parole vanno mostrate in ordine decrescente di frequenza, e in caso di frequenze uguali, devono essere ordinate lessicograficamente. Se ci sono più di dieci parole corrispondenti allo stesso prefisso, vanno mostrate soltanto le prime dieci.Esempi
Input | Ingresso |
6
fire 2
walk 2
with 2
me 2
fierce 1
win 3
3
fi
w
wi | 6
fire 2
walk 2
with 2
me 2
fierce 1
win 3
3
fi
w
wi |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB