Fișierul intrare/ieșire	tablou2.in, tablou2.out	Sursă	OJI 2017 clasa a 8-a
Autor	Carmen Mincă	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.05 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	2.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Tablou2 (clasa a 8-a)

Notă: problema este punctată ușor diferit față de original din cauza restricțiilor impuse de evaluatorul infoarena.

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 tablou2.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 tablou2.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 tablou2.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

• 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
• Se acordă 10 puncte din oficiu și câte 45 50 puncte pentru rezolvarea corectă a fiecărei cerințe.

Exemple