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.

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.

#include <bits/stdc++.h>


using namespace std;
ifstream cin("tablou.in");
ofstream cout("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)
    {
        cin >> x >> y;
        if(x=='L') L[y]=L[y]^1;
        else  C[y]=C[y]^1;
    }
    l = L.count();
    c = C.count();
    cout << n * n - l * (n - c) - c * (n - l);
}
void solve2()
{
    if(n * n < k) {cout << 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){cout << s;return;}
    }
    cout << 0;
}
int main()
{
    cin >> v >> n >> k;
    if(v==1) solve1();
    else solve2();
    return 0;
}