summax

Time limit: 0.5s Memory limit: 16MB Input: summax.in Output: summax.out

Avem o matrice triunghiulară cu nn linii, cu elemente numere întregi. În această matrice putem construi un traseu după următoarea regulă:

  • primul element al traseului este elementul a1,1a_{1,1}
  • dacă elementul ai,ja_{i,j} aparţine traseului, atunci următorul element al traseului poate fi doar ai+1,ja_{i+1,j} sau ai+1,j+1a_{i+1,j+1}, pentru orice 1jin1≤j≤i≤n

Traseul se va codifica cu numerele de ordine ale coloanelor, parcurgând liniile de la 11 la nn. Valoarea traseului este egală cu suma elementelor ce îl formează.

Traseul evidenţiat în exemplul din dreapta are valoarea 5+4+6+5+4=245+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 alăturat avem șase trasee de lungime maximă:

  • traseul 11. 1 1 1 1 2 (5+2+7+6+4=245+2+7+6+4=24)
  • traseul 22. 1 1 1 2 2 (5+2+7+6+4=245+2+7+6+4=24)
  • traseul 33. 1 2 2 2 2 (5+4+5+6+4=245+4+5+6+4=24)
  • traseul 44. 1 2 3 3 4 (5+4+6+5+4=245+4+6+5+4=24)
  • traseul 55. 1 2 3 4 4 (5+4+6+5+4=245+4+6+5+4=24)
  • traseul 66. 1 2 3 4 5 (5+4+6+5+4=245+4+6+5+4=24)

Cerinţă

Cunoscând dimensiunea și elementele unei matrice triunghiulare, respectiv două numere naturale st\text{st} şi dr\text{dr} (stdr\text{st}≤\text{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 0002 \ 000 \ 000 \ 000, se va tipări valoarea 2 000 000 0012 \ 000 \ 000 \ 001;
  2. Traseele cu numerele de ordine st,st+1,,dr\text{st}, \text{st}+1, \dots, \text{dr}.

Date de intrare

Fişierul summax.in conţine pe prima linie un număr natural vv. Pentru toate testele de intrare, numărul vv poate avea doar valoarea 11 sau 22.
A doua linie conține trei numere naturale nn, st\text{st} şi dr\text{dr}, separate prin spaţiu. Următoarele nn linii conțin câte o linie a matricei triunghiulare astfel: linia ii conține ii elemente, și anume valorile ai,1ai,2...ai,ia_{i,1} a_{i,2} ... a_{i,i} pentru orice 1in1≤i≤n.

Date de ieşire

Dacă valoarea lui vv este 11, se va rezolva numai punctul 11 din cerință. În acest caz, în fişierul de ieşire summax.out se va scrie un singur număr natural ce reprezintă numărul traseelor de lungime maximă.

Dacă valoarea lui vv este 22, se va rezolva numai punctul 22 din cerință. În acest caz, în fişierul de ieşire summax.out se vor tipări pe câte o linie nn numere naturale separate prin spațiu, reprezentând codificările traseelor de valoare maximă cu numerele de ordine st,st+1,,dr\text{st}, \text{st}+1, \dots, \text{dr}.

Restricții și precizări

  • 1n2 0001 ≤ n ≤ 2 \ 000;
  • 1stdr2 000 000 0001 ≤ st ≤ dr ≤ 2 \ 000 \ 000 \ 000;
  • 1drst1 0001 ≤ dr – st ≤ 1 \ 000;
  • elementele matricei triunghiulare sunt numere naturale strict pozitive.
  • valoarea maximă a traseului nu depășește 1 000 000 0001 \ 000 \ 000 \ 000

Exemplul 1

summax.in

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

summax.out

6

Explicație

Pentru primul exemplu, v=1v=1.
Numărul traseelor de valoare maximă este 66.

Exemplul 2

summax.in

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

summax.out

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

Explicație

Pentru al doilea exemplu, v=2v=2, st=2st=2, dr=4dr=4
S-au tipărit traseele cu numerele de ordine 22, 33 și 44.

Log in or sign up to be able to send submissions!