Sistemas-L P89549


Statement
 

pdf   zip

thehtml

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

AB
BAB

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≥ 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:  ‍60 Puntos ‍

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

  • Test-2:  ‍40 Puntos ‍

    Resolver entradas de todo tipo.

Public test cases
  • Input

    +F--F--F
    3 0
    - - -60 rotate
    + + 60 rotate
    F F+F--F+F 5 0 rlineto
    

    Output

    %!PS
    newpath 297.5 421 moveto
    60 rotate
    5 0 rlineto
    -60 rotate
    -60 rotate
    5 0 rlineto
    -60 rotate
    -60 rotate
    5 0 rlineto
    2 setlinewidth stroke showpage
    
  • Input

    X
    6 2
    X -FX++FY- 
    Y +FX--FY+ 
    F T 10 0 rlineto
    + + 45 rotate
    - - -45 rotate
    T T 
    

    Output

    %!PS
    newpath 297.5 421 moveto
    -45 rotate
    
    -45 rotate
    10 0 rlineto
    
    45 rotate
    45 rotate
    10 0 rlineto
    
    -45 rotate
    45 rotate
    45 rotate
    
    45 rotate
    10 0 rlineto
    
    -45 rotate
    -45 rotate
    10 0 rlineto
    
    45 rotate
    -45 rotate
    2 setlinewidth stroke showpage
    
  • Input

    X
    5 1
    X -YF+XFX+FY- 
    Y +XF-YFY-FX+ 
    - - -90 rotate
    + + 90 rotate
    F F 10 0 rlineto
    

    Output

    %!PS
    newpath 297.5 421 moveto
    -90 rotate
    
    10 0 rlineto
    90 rotate
    
    10 0 rlineto
    
    90 rotate
    10 0 rlineto
    
    -90 rotate
    2 setlinewidth stroke showpage
    
  • Input

    X
    6 1
    X F-[[X]+X]+F[+FX]-X 
    F FF 2 0 rlineto
    - - -22.5 rotate
    + + 22.5 rotate
    [ [ gsave
    ] ] stroke grestore
    

    Output

    %!PS
    newpath 297.5 421 moveto
    2 0 rlineto
    -22.5 rotate
    gsave
    gsave
    
    stroke grestore
    22.5 rotate
    
    stroke grestore
    22.5 rotate
    2 0 rlineto
    gsave
    22.5 rotate
    2 0 rlineto
    
    stroke grestore
    -22.5 rotate
    
    2 setlinewidth stroke showpage
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++ Python