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.1 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate |
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 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
- 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.
- 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 șicâte4550 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. |