Matriz triangular
Tenemos una matriz triangular con 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 .
- si el elemento pertenece a la ruta, entonces el siguiente elemento de la ruta puede ser solo o , para cualquier .
La ruta se codificará con números en el orden de la columna, pasando desde las líneas a . 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 , y está codificada por .
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:
.
.
.
.
.
.
Tarea
Al conocer el tamaño y los elementos de una matriz triangular y respectivamente dos números naturales y , se requiere determinar:
Número total de rutas máximas. Si este valor excede , se imprimirá el valor de .
Rutas con los números de serie .
Entrada
La entrada contiene un número natural en la primera línea. Para todas las pruebas de entrada, solo puede tener un valor de o .
La segunda línea contiene tres números naturales , y , separados por espacios. Las siguientes líneas contienen una línea de la matriz triangular de la siguiente manera: la línea contiene elementos, de la forma, , ... , para cualquier .
Salida
Si el valor de es , solo se resolverá el punto 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 es , solo se resolverá el punto de la tarea. En este caso, en la salida se imprimirá en una línea, números naturales separados por espacios, que representan la codificación de las rutas de valor máximo con .
Restricciones y aclaraciones.
•
•
• 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
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: El número máximo de rutas es . (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:
Se imprimieron los números de la serie , y . (ver ejemplo arriba).
Otra información útil
• una variable o en ocupa bytes
• ocupa una matriz con 1000 líneas y 1000 columnas con elementos integrales
• 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