Fişierul intrare/ieşire:tablou2.in, tablou2.outSursăOJI 2017 clasa a 8-a
AutorCarmen MincaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 ≤ ZN*N; 1 ≤ nrN
  • 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

tablou2.intablou2.outExplicaţii
1
4 4
L 1
L 3
C 1
L 1
10
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.
2
3 5
3
Sunt necesare minimum 3 operaţii, de exemplu:
L 3
L 1
C 1
2
4 7
0
Nu există nicio succesiune de operaţii pentru care să se obţină Z=7 valori negative.
Trebuie sa te autentifici pentru a trimite solutii. Click aici