Sistemas-L P89549

En este problema vamos a pedirte que hagas dibujos como los siguientes,

ON CONY SON ELS EPS???

y la gracia es que es mucho más fácil de lo que te imaginas. ¡Fíjate!

Un sistema de Lindenmayer (o sistema-L) es un sistema paralelo de reescritura, donde a cada turno debes reescribir todas las letras de una palabra aplicando unas reglas. Por ejemplo, en el sistema-L

$$\begin{array}{ccl} A & \rightarrow & B \\ B & \rightarrow & AB \end{array}$$

debes cambiar cada $A$ por $B$ y cada $B$ por $AB$. Si empezáramos con $A$ en el turno $0$, encontraríamos las palabras $B$ en el turno $1$, $AB$ en el 2, $BAB$ en el 3, $ABBAB$ en el 4, etc. Al final, el texto obtenido se puede interpretar como ciertas órdenes tipo Logo (avanza para delante, rota, etc.) y ya tenemos el dibujo.

En este problema te vamos a pedir que hagas avanzar varios turnos un sistema-L, y que luego escribas las letras resultantes como órdenes Postscript, que podrás visualizar fácilmente.

Entrada

La entrada consiste en un sistema-L, descrito como una línea con la cadena de texto inicial (la cual no contiene espacios) no mayor de 30 caracteres, y otra línea con el número $k>0$ de reglas de transformación (no mayor que 10) y el número $t\geq 0$ de turnos de simulación, separados por espacios.

A continuación, viene una secuencia de $k$ reglas de transformación, cada una de las cuales ocupa una línea y está formada por un carácter (diferente de espacio) seguido de un espacio, seguido del texto resultante (que nunca será la cadena vacía), seguido de un espacio, y seguido de la orden Postscript (que puede ser vacía, o contener espacios) en la que se transformará ese carácter al final del proceso. Todo carácter tendrá exactamente 1 regla de transformación.

Salida

Escribe dos líneas con el texto “%!PS” y “newpath 297.5 421 moveto”. A continuación, escribe el texto Postscript resultante de la transformación hasta el turno $t$. Haz que cada orden Postscript ocupe una línea (incluyendo las vacías). Por último, escribe una línea con el texto “2 setlinewidth stroke showpage”.

Se te asegura que ningúna salida tendrá más de 15000 líneas. Tu programa dispondrá de 1 segundo de CPU por entrada.

Pista

Al igual que con todos los problemas, puedes bajarte los ficheros de entrada (y de salida) de la web. Te recomendamos más que nunca hacerlo así, porque en este problema debes tener especial cuidado con los espacios.

Observación

Los dibujos anteriores se han obtenido a partir de los ejemplos de entrada, usando valores $t$ distintos: $t=3$ (Ejemplo 1), $t=9$ (Ejemplo 2), $t=4$ (Ejemplo 3) y $t=5$ (Ejemplo 4). Si quieres tener una comprobación adicional de que tu programa es (aparentemente) correcto, intenta obtenerlos tú mismo com el comando gv.

Puntuación

• Test-1:

  Resolver entradas donde no se generan más de 200 líneas de texto por entrada.

• Test-2:

  Resolver entradas de todo tipo.