# PBinfo #1623 – SumMax1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 ai+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:


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;
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).

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream f("summax1.in");
ofstream g("summax1.out");
unsigned p,n,x,y,i,j,*a[2001],*b[2001],oo=2000000001,D,s[2001];
void afiseaza(unsigned,unsigned);
int main()
{
    f>>p>>n>>x>>y;
    for(i=0;i<=n;i++)
    {
        a[i]=new unsigned[i+3];
        b[i]=new unsigned[i+3];
        for(j=1;j<=i;j++)
            f>>a[i][j];
    }
    for(j=1;j<=n;j++)
        b[n][j]=a[n][j];
    for(i=n-1;i>=1;i--)
        for(j=1;j<=i;j++)
            b[i][j]=a[i][j]+max(b[i+1][j],b[i+1][j+1]);
    for(j=1;j<=n;j++)
        a[n][j]=1;
    for(i=n-1;i>=1;i--)
        for(j=1;j<=i;j++)
        {
            if(b[i+1][j]>b[i+1][j+1])
                a[i][j]=a[i+1][j];
            else
            if(b[i+1][j]<b[i+1][j+1])
                a[i][j]=a[i+1][j+1];
            else
                a[i][j]=min(a[i+1][j]+a[i+1][j+1],oo);
        }
    if(p==1)
    {
        g<<a[1][1];
        return 0;
    }
    afiseaza(1,1);
    return 0;
}
void afiseaza(unsigned I,unsigned J)
{
    if(D+a[I][J]<x)
    {
        D+=a[I][J];
        return;
    }
    s[I]=J;
    if(I==n)
    {
        D++;
        for(unsigned k=1;k<=n;k++)
            g<<s[k]<<' ';
        g<<'\n';
        return;
    }
    if(b[I+1][J]>=b[I+1][J+1])
    {
        afiseaza(I+1,J);
        if(D==y)return;
    }
    if(b[I+1][J+1]>=b[I+1][J])
        afiseaza(I+1,J+1);
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1623)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1623/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1623/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)