Transformers P84831


Statement
 

pdf   zip

thehtml

Tenemos una secuencia de robots de dos tipos distintos (¿a¿ y ¿b¿), dispuestos en fila. A cada instante, una subsecuencia consecutiva de esos robots puede ser transformada en otra secuencia de robots mas grande (los motivos por los que esto pasa son misteriosos, y no entraremos en este detalle).

Se os da una secuencia origen y una secuencia objetivo, y las reglas que os permiten transformar subsecuencias de robots. Por ejemplo, a partir de las reglas

||
¿ab¿¿bba¿
¿b¿¿ba¿
||

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

||
¿aab¿¿abba¿
¿abba¿¿bbaba¿
¿bbaba¿¿bababa¿
||

Se os pide hacer un programa que, dadas la secuencia original y final, y las reglas de transformación, calcule el minimo número de pasos necesarios para transformar la secuencia original en la secuencia objetivo. Si no es posible conseguirlo, debe indicarse. Todas las reglas dadas provocarán un incremento del numero de robots en la secuencia.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con la secuencia origen y la secuencia objetivo, seguidas de un natural n, seguido de n reglas de transformación, cada una definida con sus dos secuencias, formadas exclusivamente por las letras ¿a¿ y ¿b¿. La segunda secuencia 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 secuencia original a la secuencia objetivo. Si no es posible, debe indicarse. Seguid el formato de los ejemplos.

Puntuación

  • Test1:  ‍40 Puntos ‍

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

  • Test2:  ‍60 Puntos ‍

    Resolver casos de prueba con solución de hasta 9 pasos, y también casos 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++