Avem o matrice triunghiulară cu n
linii, cu elemente numere întregi. În această matrice putem construi un traseu după următoarea regulă:
- primul element al traseului este elementul
a
1,1
- dacă elementul
a
i,j
aparţine traseului, atunci următorul element al traseului poate fi doara
i+1,j
saua
i+1,j+1
, pentru orice1≤j≤i<n
. - traseul se va codifica cu numerele de ordine ale coloanelor, parcurgând liniile de la
1
lan
. Valoarea traseului este egală cu suma elementelor ce îl formează.
Traseul evidenţiat în exemplul din dreapta are valoarea5+4+6+5+4=24
, şi se codifică cu1,2,3,3,4
.
![](/resurse/9dc152/p-1200/1623-summax1.png)
Fie mulţimea tuturor traseelor de valoare maximă generate în ordine lexicografică și numerotate. Pentru exemplul de mai sus avem șase trasee de lungime maximă:
- traseul 1.
1 1 1 1 2 (5+2+7+6+4=24)
- traseul 2.
1 1 1 2 2 (5+2+7+6+4=24)
- traseul 3.
1 2 2 2 2 (5+4+5+6+4=24)
- traseul 4.
1 2 3 3 4 (5+4+6+5+4=24)
- traseul 5.
1 2 3 4 4 (5+4+6+5+4=24)
- traseul 6.
1 2 3 4 5 (5+4+6+5+4=24)
Cerința
Cunoscând dimensiunea și elementele unei matrice triunghiulare, respectiv două numere naturale st
şi dr
(st≤dr
), se cere să se determine:
- Numărul total al traseelor de valoare maximă. În cazul în care această valoare depășește
2.000.000.000
, se va tipări valoarea2.000.000.001
; - Traseele cu numerele de ordine
st
,st+1
, … ,dr
.
Date de intrare
Fișierul de intrare summax1.in
conține pe prima linie un număr v
. Pentru toate testele de intrare, numărul v
poate avea doar valoarea 1
sau 2
.
A doua linie conține trei numere naturale n
, st
şi dr
, separate prin spaţiu. Următoarele n
linii conțin câte o linie a matricei triunghiulare astfel: linia i
conține i
elemente, și anume valorile a
i,1
a
i,2
… a
i,i
pentru orice 1≤i≤n
.
Date de ieșire
Dacă valoarea lui v
este 1
, se va rezolva numai punctul 1 din cerință.
În acest caz, în fişierul de ieşire summax1.out
se va scrie un singur număr natural ce reprezintă numărul traseelor de lungime maximă.
Dacă valoarea lui v
este 2
, se va rezolva numai punctul 2
din cerință.
În acest caz, în fişierul de ieşire summax1.out
se vor tipări pe câte o linie n
numere naturale separate prin spațiu, reprezentând codificările traseelor de valoare maximă cu numerele de ordine st
, st+1
, … , dr
.
Restricții și precizări
1 ≤ n ≤ 2000
1 ≤ st ≤ dr ≤ 2.000.000.000
1 ≤ dr – st ≤ 1000
- elementele matricei triunghiulare sunt numere naturale strict pozitive
- valoarea maximă a traseului nu depășește
1.000.000.000
Exemplul 1
summax1.in
1 5 2 4 5 2 4 7 5 6 6 6 5 5 3 4 3 4 4
summax1.out
6
Explicație
v=1
Numărul traseelor de valoare maximă este 6
. (vezi exemplul de mai sus).
Exemplul 2
summax1.in
2 5 2 4 5 2 4 7 5 6 6 6 5 5 3 4 3 4 4
summax1.out
1 1 1 2 2 1 2 2 2 2 1 2 3 3 4
Explicație
v=2
st=2 dr=4
S-au tipărit traseele cu numerele de ordine 2
, 3
și 4
. (vezi exemplul de mai sus).