Rezolvare PBinfo #1623

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 a1,1
• dacă elementul ai,j aparţine traseului, atunci următorul element al traseului poate fi doar ai+1,j sau a_i+1,j+1, pentru orice 1≤j≤i<n.
• traseul se va codifica cu numerele de ordine ale coloanelor, parcurgând liniile de la 1 la n. Valoarea traseului este egală cu suma elementelor ce îl formează.
  Traseul evidenţiat în exemplul din dreapta are valoarea 5+4+6+5+4=24, şi se codifică cu 1,2,3,3,4.

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:

1. 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 valoarea 2.000.000.001;
2. 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 ai,1 ai,2 … ai,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).