Rezolvare completă PbInfo #2070 Tablou

Se consideră un tablou cu N linii şi N coloane (numerotate de la 1 la N) care conţine valoarea 1 în fiecare dintre cele NxN celule. Valorile din tablou pot fi modificate prin aplicarea a două operații codificate astfel:

  • L nr, prin care se schimbă simultan toate semnele numerelor din linia cu numărul nr.
  • C nr, prin care se schimbă simultan toate semnele numerelor din coloana cu numărul nr.

Cerințe

1) Dându-se o succesiune de K operații (L nr sau C nr) asupra liniilor/coloanelor tabloului inițial (în care toate celulele conțin valoarea 1) să se determine numărul valorilor pozitive din tablou la finalul executării celor K operații.
2) Să se determine numărul minim de operații L nr sau C nr, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact Z valori negative.

Date de intrare

Fișierul de intrare tablou.in conține pe prima linie numărul p=1 sau p=2, reprezentând numărul cerinței ce trebuie rezolvată.

  • Dacă p=1 atunci linia a doua a fișierului de intrare conține numerele N și K, separate printr-un spațiu, iar următoarele K linii conțin fiecare câte o literă mare (L sau C) și un număr nr, separate printr-un spațiu, reprezentând codificarea uneia dintre cele două operații (L nr sau C nr).
  • Dacă p=2 atunci linia a doua a fișierului de intrare conține numerele N și Z, separate printr-un spațiu.

Date de ieșire

  • Dacă p=1, atunci fișierul de ieșire tablou.out conține pe prima linie un număr natural, reprezentând numărul valorilor pozitive din tabloul obținut la finalul executării celor K operații asupra tabloului inițial (răspunsul la cerința 1).
  • Dacă p=2, atunci fișierul de ieșire tablou.out conține pe prima linie un număr natural reprezentând numărul minim de operații L nr sau C nr, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact Z valori negative (răspunsul la cerința 2). Dacă prin aplicarea de operații L nr sau C nr tabloului inițial nu se poate obține un tablou cu Z valori negative, atunci, fișierul va conține pe prima linie valoarea 0 (zero).

Restricții și precizări

  • N, K, Z și nr sunt numere naturale
  • 3 ≤ N ≤ 20000; 1 ≤ K ≤ 43000; 1 ≤ Z ≤ N*N; 1 ≤ nr ≤ N
  • Prin schimbare de semn, valoarea -1 se transformă în 1 și valoarea 1 se transformă în -1
  • În concurs s-au acordat 10 puncte din oficiu și câte 45 puncte pentru rezolvarea corectă a fiecărei cerințe. Pe site se acordă 10 puncte pentru rezolvarea corectă a exemplelor.

Exemplul 1

tablou.in

1
4 4
L 1
L 3
C 1
L 1

tablou.out

10

Explicație

N=4. La finalul aplicării succesiunii de K=4 operații, tablou modificat are conținutul:

-1  1  1  1
-1  1  1  1
 1 -1 -1 -1
-1  1  1  1

Astfel, tabloul conține 10 valori pozitive.

Exemplul 2

tablou.in

2
3 5

tablou.out

3

Explicație

Sunt necesare minimum 3 operații, de exemplu: L 3, L 1, C 1

Exemplul 3

tablou.in

2
4 7

tablou.out

0

Explicație

Nu există nicio succesiune de operații pentru care să se obțină Z=7 valori negative.

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 Tablou:

//sursa oficiala-prof. Carmen Minca
#include <fstream>
using namespace std;

#define Nmax 20005

ifstream fin("tablou.in");
ofstream fout("tablou.out");

int N,Z,K,M,P;
char linie[Nmax];
char coloana[Nmax];

void cerinta1()
{
    fin>>N>>K;
    char LC;
    int nr_val_pozitive,nr_val_negative,nr;
    int i, linimpar=0, colimpar=0;
    for(i=1; i<=K; i++)
    {
        fin>>LC>>nr;
        if(LC=='L')
            linie[nr]=(linie[nr]+1)%2;
        else
            coloana[nr]=(coloana[nr]+1)%2;
    }
    for(i=1; i<=N; i++)
    {
        linimpar+=linie[i];
        colimpar+=coloana[i];
    }

    nr_val_negative=linimpar*(N-colimpar)+(N-linimpar)*colimpar;
    nr_val_pozitive=N*N - nr_val_negative;
    fout<<nr_val_pozitive<<endl;
}

void cerinta2()
{
    fin>>N>>Z;
    int M,linimpar, colimpar,ok=0, i;

    if(Z>N*N)ok=0;
    else if(Z==N*N)
    {
        linimpar=N;
        colimpar=0;
        ok=1;
    }
    else if(2*Z==N*N)
    {
        ok=1;
        linimpar=N/2;
        colimpar=0;
    }
    else
        for(linimpar=0; (linimpar<=N) && (ok==0); linimpar++)
        {
            if(N-2*linimpar!=0 && (Z-N*linimpar)%(N-2*linimpar)==0)
            {
                colimpar=(Z-N*linimpar)/(N-2*linimpar);
                if(colimpar>=0 && colimpar<=N)
                {
                    ok=1;
                    break;
                }
            }
        }
    if(ok==0)fout<<0<<endl;
    else fout<<linimpar+colimpar<<endl;
}

int main()
{
    fin>>P;
    if(P==1) cerinta1();
    else cerinta2();
    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 #2070 Tablou

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2070 Tablou 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!