Palabras crecientes P20520


Statement
 

pdf   zip

thehtml

Se os da una palabra origen y una palabra objetivo. Adicionalmente, tenéis unas cuantas reglas que os permiten transformar trozos de la palabra original. Por ejemplo, a partir de las reglas

||
abbba
bba
||

y de la palabra original aab, se pueden hacer (entre otras) las transformaciones sucesivas

||
aababba
abbabbaba
bbababababa
||

Se os pide hacer un programa que, dadas las palabras original y final, y las reglas de transformación, calcule el mínimo número de pasos necesarios para transformar la palabra original en la palabra objetivo. Si no es posible conseguirlo, debe indicarse. Todas las reglas dadas provocarán un incremento en el tamaño de la palabra.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con la palabra origen y la palabra objetivo (ambas de longitud menor que 20), seguidas de un natural positivo n≤ 12, seguido de n reglas de transformación, cada una definida con sus dos palabras (ambas de longitud menor que 10), formadas exclusivamente por las letras a y b. La segunda palabra de cada regla será más larga que la primera.

Salida

Para cada caso de la entrada, tenéis que escribir el número de caso, seguido del mínimo número de pasos necesarios para pasar de la palabra original a la palabra objetivo. Si no es posible, debe indicarse. Seguid el formato de los ejemplos.

Puntuación

  • Test-1:  ‍40 puntos Puntos ‍

    Resolver casos de prueba como los del ejemplo 1, donde todos los casos tienen solución, y siempre en 3 pasos o menos.

  • Test-2:  ‍60 puntos Puntos ‍

    Resolver casos de prueba con solución de hasta 9 pasos, y también sin solución, como los del ejemplo 2.

Public test cases
  • Input

    aab bababa
    2
    ab bba
    b ba
    
    a abba
    3
    a bb
    bb abba
    a abba
    
    abcd abcd
    0
    
    abab bbbaaa
    2
    ab aaa
    ab bbb
    

    Output

    Caso #1: solucion en 3 pasos
    Caso #2: solucion en 1 paso
    Caso #3: solucion en 0 pasos
    Caso #4: solucion en 2 pasos
    
  • Input

    aaa abbabbab
    3
    a ab
    b bb
    ab abb
    
    a b
    0
    
    a aaabababba
    8
    a aa
    a ab
    a ba
    a bb
    b aa
    b ab
    b ba
    b bb
    
    aa bbabb
    3
    a bab
    a bbb
    ba abba
    

    Output

    Caso #1: solucion en 5 pasos
    Caso #2: sin solucion
    Caso #3: solucion en 9 pasos
    Caso #4: sin solucion
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++