Matriz triangular


Submit solution

Points: 100 (partial)
Time limit: 3.0s
Memory limit: 128M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Tenemos una matriz triangular con n líneas, con números enteros. En esta matriz podemos construir una ruta usando la siguiente regla:

  • el primer elemento de la ruta es el elemento a_{1,1}.
  • si el elemento a_{i, j} pertenece a la ruta, entonces el siguiente elemento de la ruta puede ser solo a_{i + 1, j} o a_{i + 1, j + 1}, para cualquier 1 \le j \le i < n.

La ruta se codificará con números en el orden de la columna, pasando desde las líneas 1 a N. El valor de la ruta es igual a la suma de los elementos que la conforman.

La ruta resaltada en el gráfico de ejemplo tiene el valor de 5 + 4 + 6 + 5 + 4 = 24, y está codificada por 1,2,3,3,4.

descripción aqui

Ya sea el conjunto de todas las rutas máximas generadas en orden lexicográfico y numerado. Para el siguiente ejemplo, tenemos seis trayectorias de longitud máxima:

Ruta 1. 1 1 1 1 2 (5 + 2 + 7 + 6 + 4 = 24)

Ruta 2. 1 1 1 2 2 (5 + 2 + 7 + 6 + 4 = 24)

Ruta 3. 1 2 2 2 2 (5 + 4 + 5 + 6 + 4 = 24)

Ruta 4. 1 2 3 3 4 (5 + 4 + 6 + 5 + 4 = 24)

Ruta 5. 1 2 3 4 4 (5 + 4 + 6 + 5 + 4 = 24)

Ruta 6. 1 2 3 4 5 (5 + 4 + 6 + 5 + 4 = 24)

Tarea

Al conocer el tamaño y los elementos de una matriz triangular y respectivamente dos números naturales st y dr (st \le dr), se requiere determinar:

  1. Número total de rutas máximas. Si este valor excede 2000000000, se imprimirá el valor de 2000000001.

  2. Rutas con los números de serie st, st + 1, ..., dr.

Entrada

La entrada contiene un número natural v en la primera línea. Para todas las pruebas de entrada, v solo puede tener un valor de 1 o 2.

La segunda línea contiene tres números naturales n, st y dr, separados por espacios. Las siguientes n líneas contienen una línea de la matriz triangular de la siguiente manera: la línea contiene i elementos, de la forma, a_{i, 1}, a_{i, 2} ... a_{i, i}, para cualquier 1 \le i \le n.

Salida

Si el valor de v es 1, solo se resolverá el punto 1 de la tarea. En este caso, en la salida se escribirá un solo número natural que representa el número de rutas de longitud máxima.

Si el valor de v es 2, solo se resolverá el punto 2 de la tarea. En este caso, en la salida se imprimirá en una línea, n números naturales separados por espacios, que representan la codificación de las rutas de valor máximo con st, st + 1, ..., dr.

Restricciones y aclaraciones.

1 \le n \le 2000

1 \le st \le dr \le 2 000 000 000

• 1 ≤ dr - st ≤ 1000

• Los elementos de la matriz triangular son números naturales estrictamente positivos.

• El valor máximo de la ruta no excede 1,000,000,000

Ejemplo de Entrada #1

1
5 2 4
5
2 4
7 5 6
6 6 5 5
3 4 3 4 4

Ejemplo de Salida #1

6

Explicación: v = 1 El número máximo de rutas es 6. (ver ejemplo arriba).

Ejemplo de Entrada #2

2
5 2 4
5
2 4
7 5 6
6 6 5 5
3 4 3 4 4

Ejemplo de Salida #2

1 1 1 2 2
1 2 2 2 2
1 2 3 3 4

Explicación: v = 2

st = 2

dr = 4

Se imprimieron los números de la serie 2, 3 y 4. (ver ejemplo arriba).

Otra información útil

• una variable int (C++) o integer en (Pascal) ocupa 4 bytes (32 bits)

• ocupa una matriz con 1000 líneas y 1000 columnas con elementos integrales (1000 * 1000 * 4) / (1024 * 1024) = 3.81 MB

• Las pruebas de entrada tienen la siguiente configuración:

  #     v   n   st  dr
  0     1   20  4   10
  1     1   900 50  100
  2     1   1300    2000    3000
  3     1   1700    20000   21000
  4     2   20  6   9
  5     2   30  20 000 000  20 001 000
  6     2   60  40 030 000  40 031 000
  7     2   100 139 876 543 139 876 999
  8     2   500 137 987 000 137 988 000
  9     2   700 123 456 789 123 457 777
  10    2   900 100 000 000 100 001 000
  11    2   1000    1 999 999 999   2 000 000 000
  12    2   1010    1 000 000   1 000 001
  13    2   1020    10 123  11 111
  14    2   1100    1 999 999 999   2 000 000 000
  15    2   1200    1 000 000   1 000 001
  16    2   1300    10 123  11 111
  17    2   1500    1 999 999 999   2 000 000 000
  18    2   1600    1 000 000   1 000 999
  19    2   1700    10 123  11 123

Comments

There are no comments at the moment.