Fișierul intrare/ieșire tablou2.in, tablou2.out Sursă OJI 2017 clasa a 8-a
Autor Carmen Mincă Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Tablou2 (clasa a 8-a)

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

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.in tablou2.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii