Potaje de letras P65859


Statement
 

pdf   zip

thehtml

Un potaje de letras es como una sopa de letras, pero donde las palabras no tienen porqué aparecer únicamente en orden horizontal o vertical: las palabras son como spaghettis que pueden cambiar de orientación (vertical o horizontal) tantas veces como haga falta mientras aparecen en el potaje. Por ejemplo, el siguiente potaje contiene las palabras oie (2 veces) y mississipi, que marcamos en mayúsculas:

E  ‍ w  ‍ a  ‍ P  ‍ z  ‍ a
I  ‍ a  ‍ x  ‍ I  ‍ S  ‍ S
O  ‍ a  ‍ x  ‍ M  ‍ S  ‍ I
z  ‍ O  ‍ z  ‍ I  ‍ S  ‍ x
a  ‍ I  ‍ E  ‍ a  ‍ a  ‍ z

Fíjate que la palabra OIE aparece dos veces, y que la palabra MISSISSIPI reutiliza la misma letra I del potaje para representar sus dos últimas Is.

Te pedimos que hagas un programa que sea capaz de, dado un potaje de letras y una lista de palabras, descubrir si las palabras aparecen o no aparecen en el potaje. También te pedimos que tu programa marque las palabras que encuentra.

Entrada

La primera línea de la entrada contiene la palabra BUSCA (decidir, para cada palabra, si aparece o no) o MARCA (además de decidirlo, marcar encima del potaje todas las apariciones de las palabras que encuentres).

La segunda línea de la entrada contiene los números N, M≤ 50 y de filas y columnas del potaje de letras, y viene seguida de la descripción del potaje, con N líneas de M letras minúsculas. Por último, una línea con el número K≤ 50 de palabras que se te pregunta, ninguna de las cuales contendrá más de 50 letras minúsculas, y las K palaras, una por línea.

Salida

Escribe K líneas diciendo, para cada palabra, si aparece o no aparece en el potaje de letras, siguiendo el formato de los ejemplos.

Además, si la entrada empezaba con la palabra MARCA, escribe el potaje de letras, marcando todas las letras que forman parte de alguna palabra en mayúsculas.

Puntuación

  • Test1:  ‍25 Puntos ‍

    Resolver entradas BUSCA donde ninguna palabra tiene más de 3 letras.

  • Test2:  ‍20 Puntos ‍

    Resolver entradas BUSCA y MARCA donde ninguna palabra tiene más de 5 letras.

  • Test3:  ‍40 Puntos ‍

    Resolver entradas BUSCA de cualquier tipo.

  • Test4:  ‍15 Puntos ‍

    Resolver entradas BUSCA y MARCA de cualquier tipo.

Public test cases
  • Input

    BUSCA
    5 6
    ewapza
    iaxiss
    oaxmsi
    zozisx
    aieaaz
    4
    oie
    aa
    zzz
    sis
    

    Output

    oie: SI
    aa: SI
    zzz: NO
    sis: SI
    
  • Input

    MARCA
    5 6
    ewapza
    iaxiss
    oaxmsi
    zozisx
    aieaaz
    4
    oie
    aa
    zzz
    missis
    

    Output

    oie: SI
    aa: SI
    zzz: NO
    missis: SI
    Ewapza
    IAxISS
    OAxMSI
    zOzISx
    aIEAAz
    
  • Input

    BUSCA
    5 6
    exapza
    iaxiss
    oxamsi
    zoxisx
    aieaax
    4
    oie
    mississipi
    axaxaxaxaxaxaxaxaxaxaxaxa
    axaxaxaxaxaaxaxaxaxaxaxa
    

    Output

    oie: SI
    mississipi: SI
    axaxaxaxaxaxaxaxaxaxaxaxa: SI
    axaxaxaxaxaaxaxaxaxaxaxa: NO
    
  • Input

    MARCA
    5 6
    exapza
    iaxiss
    oxamsi
    zoxisx
    aieaax
    3
    oie
    mississipi
    axaxaxaxaxaxaxaxaxaxaxaxa
    

    Output

    oie: SI
    mississipi: SI
    axaxaxaxaxaxaxaxaxaxaxaxa: SI
    EXAPza
    IAXISS
    OXAMSI
    zOXISx
    aIEaAX
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++