F015B. Text predictiu T9 P65854


Statement
 

pdf   zip

thehtml

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:
||
123
 ABCDEF
456
GHIJKLMNO
789
PQRSTUVWXYZ
0 
WWWWWWWWWWWW
||

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 Diccionaridic); 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.

Public test cases
  • Input

    7
    CAPA 8
    COMA 20
    BONA 30
    ESTROBOGRAMATIC 5
    CASA 10
    CARA 10
    ZK 1
    
    2662
    2272
    2273
    378762647262842
    34672572655667338823552337
    95
    95
    2
    

    Output

    2662: BONA
    2272: CARA
    2273: ???
    378762647262842: ESTROBOGRAMATIC
    34672572655667338823552337: ???
    95: ZK
    95: ZK
    2: ???
    
  • Information
    Author
    Professorat de P1
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++