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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Joc6:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1385 Joc6

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1385 Joc6 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1385 Joc6