Árbol de rocas (2) P64774


Statement
 

pdf   zip

thehtml

Los habitantes de cierto remoto, desarbolado lugar tienen la tradición de construir esculturas en forma de árbol sobre un río cercano. Cuenta la leyenda que un artista observó que en una zona del río había hileras de rocas paralelas a la orilla, y decidió usarlas para hacer una gran figura en forma de árbol.

El mismo proceso es todavía usado por los actuales pobladores. Los ayudantes del artista se sitúan cada uno en una roca, excepto en aquellas de la última hilera, la más alejada de la orilla. El artista se coloca en la orilla. Todo el mundo (incluyendo el artista) lleva una bolsa con cuerdas acabadas en ganchos. Cada persona elige un número cualquiera de cuerdas (o ninguna) y las lanza sobre las rocas de la hilera siguiente. El genio de la idea, el único que permanece en tierra, lanza sus cuerdas desde tierra hacia las rocas de la primera hilera.

Para que el diseño resultante sea considerado válido, es necesario que se cumpla lo siguiente:

  • Cada roca solo puede recibir un gancho (de la hilera inmediatamente inferior).
  • Dos cuerdas no pueden cruzarse, aunque vayan a rocas distintas.
  • El resultado final es un árbol (grafo conexo y sin ciclos), del que todas las rocas forman parte.

Estos son los dos únicos diseños que pueden formarse con 2 piedras en la primera hilera, 1 piedra en la segunda, y 3 en la tercera:

unit=0.6cm (9,5) [linewidth=2pt,fillcolor=lightgray,fillstyle=solid](0,0)(0,1)(9,1)(9,0)[linewidth=0.5pt](0,2)(9,2) [linewidth=0.5pt](0,3)(9,3) [linewidth=0.5pt](0,4)(9,4) (4,1)0.21a(4,1) (3,2)0.22a(3,2) (6,2)0.22b(6,2) (5,3)0.23a(5,3) (2,4)0.24a(2,4) (3,4)0.24b(3,4) (6,4)0.24c(6,4) ->1a2a ->1a2b ->2a3a ->3a4a ->3a4b ->3a4c     (9,5) [linewidth=2pt,fillcolor=lightgray,fillstyle=solid](0,0)(0,1)(9,1)(9,0)[linewidth=0.5pt](0,2)(9,2) [linewidth=0.5pt](0,3)(9,3) [linewidth=0.5pt](0,4)(9,4) (4,1)0.21a(4,1) (3,2)0.22a(3,2) (6,2)0.22b(6,2) (5,3)0.23a(5,3) (2,4)0.24a(2,4) (3,4)0.24b(3,4) (6,4)0.24c(6,4) ->1a2a ->1a2b ->2b3a ->3a4a ->3a4b ->3a4c

El punto 3 es especialmente importante: un primo lejano del artista perdió la licencia porque sus dibujos consistían en varios árboles (un “bosque”), y no en un único árbol, tal y como mandan los cánones.

Ayuda al artista calculando de cuántas formas diferentes puede quedar su obra según dichas restricciones.

Entrada

La entrada contiene un número indeterminado de casos. Cada caso se da en dos líneas. La primera línea contiene el número k de hileras de piedras del río, mientras que la segunda línea contiene los k números de rocas de cada hilera, empezando por la más cercana a tierra, siempre mayores que cero.

Salida

Para cada caso, se debe imprimir en una línea el número de formas diferentes. Como este número puede ser muy grande, imprímelo módulo 10007.

Puntuación

  • Test1:  ‍10 Puntos ‍

    Resolver entradas con no más de 50 casos, cada uno de los cuales tiene una sola hilera (k=1) y no hay más de 50 rocas por hilera.

  • Test2:  ‍20 Puntos ‍

    Resolver entradas con no más de 50 casos, cada uno de los cuales tiene una o dos hileras (k≤ 2) y no hay más de 50 rocas por hilera.

  • Test3:  ‍30 Puntos ‍

    Resolver entradas con no más de 50 casos, cada uno de los cuales tiene menos de 20 hileras (k < 20) y no hay más de 50 rocas por hilera.

  • Test4:  ‍20 Puntos ‍

    Resolver entradas con no más de 50 casos, cada uno de los cuales tiene menos de 200 hileras (k < 200) y no hay más de 200 rocas por hilera.

  • Test5:  ‍20 Puntos ‍

    Resolver entradas con no más de 1000 casos, cada uno de los cuales tiene menos de 2000 hileras (k < 2000) y no hay más de 2000 rocas por hilera.

Public test cases

  • Input

    1
1
1
2
1
7

    Output

    1
1
1

  • Input

    2
1 1
2
2 2
2
3 2
2
2 3
2
24 12
2
17 11

    Output

    1
3
6
4
8098
8781

  • Input

    2
1 1
3
1 2 1

    Output

    1
2

  • Input

    5
13 193 84 12 104
3
99 101 100
12
1 2 3 4 5 6 7 8 9 10 11 12

    Output

    3053
4320
348
    • Information
    Author
    Álex Álvarez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++