F015B. Text predictiu T9 P65854

Com la majoria de joves, la Steffy es passa moltes hores al dia enviant missatges SMS als seus amics. Avui està ensenyant el seu nou mòbil rosa al Roy i al Johnny.

Steffy:

Heu vist que guai que és? A més, utilitza la nova tecnologia T9!

Johnny:

Què carai és això de la T9?

Steffy:

Vol dir “Text on 9 keys”, i és un sistema predictiu de text. Permet entrar paraules amb una sola pulsació per lletra, en lloc de prémer diverses vegades per a cada lletra.

Roy:

Què vols dir?

Steffy:

Mira, el teclat dels telèfons és el següent:

1	2	3
	ABC	DEF
4	5	6
GHI	JKL	MNO
7	8	9
PQRS	TUV	WXYZ
	0

Roy, amb el teu telèfon sense T9, com escriuries “@BONA@”?

Roy:

Doncs hauria de picar “@22 666 66 2@”.

Steffy:

Això mateix, és a dir, 8 tecles. En canvi, utilitzant la tecnologia T9, jo només he de picar “@2662@”, és a dir, tantes tecles com lletres té la paraula.

Johnny:

Ja... però havent picat “@2662@”, per què el telèfon endevina que vols escriure “@BONA@” i no “@COMA@”, que també es picaria “@2662@”?

Steffy:

Aquí està la gràcia! El telèfon emmagatzema un diccionari de paraules, juntament amb la freqüència d’aparició de cadascuna, i tria la més freqüent.

Johnny:

I si no volies la paraula més freqüent?

Steffy:

Et fots.

Feu un programa que, a partir d’un diccionari de paraules amb les seves freqüències, utilitzi la tecnologia T9 per “endevinar” la paraula corresponent a cada seqüència de tecles donada.

Entrada

L’entrada comença amb la descripció d’un diccionari: un natural $n$, seguit de $n$ parells amb una paraula en majúscules i un natural que representa la seva freqüència (com més alt, més freqüent és la paraula). Totes les paraules del diccionari són diferents. Després venen les seqüències de tecles, les quals són cadenes (potser llargues) de dígits entre ‘@2@’ i ’@9@’.

Sortida

Per a cada seqüència de tecles de l’entrada, cal escriure en una línia la paraula del diccionari corresponent amb freqüència més alta. En cas d’empat a freqüències, cal escriure la paraula més petita en ordre alfabètic. En cas de no correspondre’s a cap paraula del diccionari, cal escriure “@???@”. Utilitzeu el format de l’exemple.

Observacions

Encara que hi ha solucions millors, per senzillesa useu les declaracions de tipus

    struct Parella {
        string par;
        int freq;
    };

    typedef vector<Parella> Diccionari;

per implementar i usar una funció @string endevina(string s, const Diccionari& dic);@ que, donada una seqüència de tecles @s@ i un diccionari ordenat decreixentment per freqüència, i en cas d’empat creixentment per paraula, busqui seqüencialment i retorni la paraula del diccionari que es correspon a @s@, o bé “@???@”.

Lògicament, abans haureu d’ordenar el diccionari. Aquesta ordenació ha de ser eficient.

Qualsevol solució que no segueixi aquests requeriments serà qualificada amb un zero.