# PBinfo #1385 – Joc6 – Rezolvare C++

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

## Enunț

Cerința
Dom’ Profesor Unu și Dom’ Profesor Doi au găsit o matrice cu n linii numerotate de la 1 la n și n coloane numerotate de la 1 la n și elemente numere naturale. Semnificativ marcați de algoritmul de determinare a celui mai lung subșir crescător, au inventat pe loc un joc:


liniile cu indice impar aparțin lui Dom’ Profesor Unu, cele cu indice par aparțin lui Dom’ Profesor Doi;
pentru fiecare linie a sa, Dom’ Profesor Unu determină lungimea maximă a unui subșir crescător;
pentru fiecare linie a sa, Dom’ Profesor Doi determină lungimea maximă a unui subșir descrescător;
scorul fiecărei linii este lungimea determinată;
scorul total al fiecărui Dom’ Profesor este egal cu suma scorurilor liniilor corespunzătoare;
jocul este câștigat de Dom’ Profesor cu scorul total mai mare.

Determinați scorului fiecărui Dom’ Profesor și stabiliți câștigătorul.

Date de intrare
Fișierul de intrare joc6.in conține pe prima linie numărul n; fiecare dintre următoarele n linii conține n numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire joc6.out va conține pe prima linie două numere S1 S2, separate prin exact un spațiu, unde S1 este scorul lui Dom’ Profesor Unu, iar S2 este scorul lui Dom’ Profesor Doi. Linia a doua va conține unul dintre cuvintele:


UNU – dacă câștigă Dom’ Profesor Unu;
DOI – dacă câștigă Dom’ Profesor Doi;
REMIZA – dacă scorurile sunt egale.

Restricții și precizări

1 ≤ n ≤ 150
elementele matricei vor fi mai mici decât 1.000.000.000

Exemplu:
joc6.in

4
1 4 2 3
2 9 8 7
3 6 3 8
1 2 3 3
joc6.out

6 5
UNU
Explicație

linia 1 este a lui Dom’ Profesor Unu. Scorul este 3 – subșirul 1 2 3;
linia 2 este a lui Dom’ Profesor Dou. Scorul este 3 – subșirul 9 8 7;
linia 3 este a lui Dom’ Profesor Unu. Scorul este 3 – subșirul 3 3 8;
linia 4 este a lui Dom’ Profesor Doi. Scorul este 2 – subșirul 3 3.

Așadar, scorul total a lui Dom’ Profesor Unu este 3+3=6, iar scorul total al lui Dom’ Profesor Doi este 2+3=5. Câștigă Unu.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
using namespace std;
#define NN 155
ifstream fin("joc6.in");
ofstream fout("joc6.out");
int n , a[NN], L[NN];
int main()
{
    fin >> n;
    int s1 = 0 , s2 = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= n ; j ++)
            fin >> a[j];
        int semn;
        if(i % 2 == 1)
            semn = 1;
        else
            semn = -1;
        for(int j = n ; j > 0 ; j --)
        {
            L[j] = 1;
            for(int k = j + 1; k <= n ; k ++)
                if(semn * a[j] <= semn * a[k])
                    if(L[j] < 1 + L[k])
                        L[j] = 1 + L[k];
        }
        int Max = L[1];
        for(int j = 2 ; j <= n ; j ++)
            if(L[j] > Max)
                Max = L[j];
        if(semn == 1)
            s1 += Max;
        else
            s2 += Max;
    }
    fout << s1 << " " << s2 << endl;
    if(s1 > s2)
        fout << "UNU";
    else
        if(s1 < s2)
            fout << "DOI";
        else
            fout << "REMIZA";
    return 0;
}
```

## Resurse

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