cifras y LETRAS P45146


Statement
 

pdf   zip

thehtml

Bienvenido, concursante. ¿Que tal se te dan las letras? Porque en la prueba de hoy deberás resolver el famoso juego de las letras, del conocidísimo concurso “Cifras y Letras”. (Sí, de veras, es un concurso conocidísimo; si no has sentido hablar de él, es culpa tuya. Se emitió en los 90 por La 2, y todavía lo emiten en la actualidad en algunas televisiones autonómicas; el concurso original francés, “Des chiffres et des lettres”, se lleva emitiendo en Francia desde el 1972).

La prueba de Letras consiste en lo siguiente: dadas 9 letras, posiblemente repetidas, forma con ellas la palabra más larga posible. Por ejemplo, si las letras fuesen

A T Z A L J A I R

podríamos formar la palabra alzar o, mejor aún, la palabra aljaraz (que, como todo el mundo sabe, es la campanilla que llevan al cuello las cabras, ovejas, hurones, etc.).

Entrada

La entrada consiste en un número n<1000 en una línea, seguida de exactamente n líneas, cada una de las cuales contiene una palabra (en minúsculas) de como mucho 9 letras. Estas n palabras forman el diccionario de palabras válidas en el juego. A continuación, un natural k<100, con el número de casos a resolver, seguido de k líneas, cada una de las cuales contiene un caso (exactamente 9 letras mayúsculas).

Tu programa deberá resolver todos los casos en 1 segundo de tiempo.

Salida

Exactamente k líneas, una para cada caso, con la palabra más larga (escrita en mayúsculas) del diccionario que sea posible formar usando las letras del caso, o una línea en blanco si no fuera posible escribir ninguna de las palabras. De haber más de una palabra de máxima longitud, se escribirá la primera en aparecer en el diccionario.

Public test cases
  • Input

    3
    alzar
    aljaraz
    alondra
    1
    ATZALJAIR
    

    Output

    ALJARAZ
    
  • Input

    20
    ntage
    uuvg
    neiclimas
    mbnoe
    oeqpogw
    astbcv
    gfr
    uvtufbse
    otsiguc
    bzairmpal
    czdo
    msow
    jast
    rffflvutu
    umsogiil
    ueihez
    dje
    ooun
    ioedooox
    upyabaef
    3
    IPSJENZAT
    TNQNPPEOU
    BNGUPCOOU
    

    Output

    JAST
    
    OOUN
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++