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.

Autor prof.  Carmen Mincă

Colegiul Național de Informatică Tudor Vianu – București

Presupunem că s-a aplicat de x_i ori operația L i și dey_k ori operația C k.

Valoarea memorată în celula situată în liniai și coloanak își va schimba semnul dex_i+y_k ori.

Astfel, ea va fi negativă dacă suma x_i+y_k este impară.

Deducem că numărul de valori negative din tabloul modificat va depinde de paritățile numerelor x_i și y_k.  Dacă șirul valorilorx₁,x₂,x₃,..,x_N conține x valori impare iar șirul valorilor y₁,y₂,y₃,..,y_N conține y valori impare atunci tabloul modificat va conține x*(N-y)+y*(N-x) valori negative.

Astfel răspunsul la cerința 1) este valoarea expresiei N² – x*(N-y) + y*(N-x)

Pentru cerința 2), vom folosi relația  x*(N-y)+y*(N-x)=Z.

Căutăm prima valoare a lui x din mulțimea {0,1,2,…,N} pentru care există un y din {0,1,2,..,N}  și cu proprietatea că y= . și N≠2*x Dacă există aceste valori x și y, atunci numărul minim de operații este M=x+y

#include <fstream>
#include <cmath>
#include <bitset>
using namespace std;
ifstream fin("tablou.in");
ofstream fout("tablou.out");

bitset <20005> L,C;
char x;
int i,y,n,v,k,l,c,s,p;

void solve1()
{ for(i=1;i<=k;++i)
   { fin>>x>>y;
      if(x=='L') L[y]=L[y]^1;
            else C[y]=C[y]^1;
   }
   l=L.count();
   c=C.count();
   fout<<n*n-l*(n-c)-c*(n-l);
}

void solve2()
{ if(k>n*n) {fout<<0; return;}
  for(s=k/n;s<=n;++s)
    if((n*s-k)%2==0) {p=(n*s-k)/2;
                      y=sqrt(s*s-4*p);
                      if(y*y==s*s-4*p){fout<<s;return;}
                      }
 fout<<0;
}
int main()
{ fin>>v>>n>>k;
 if(v==1) solve1();
  else solve2();
  fin.close();fout.close();
  return 0;
}

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