Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | electrica.in, electrica.out | Sursă | Algoritmiada 2009, Runda Finala |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 36096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Electrica
 In momentul in care trimiti o sursa, vei putea vedea scorul obtinut pe o parte din testele folosite la evaluare in monitor. |
Gabriela lucreaza la Electrica S.A. unde se ocupa de panouri publicitare. Ea acum lucreaza la un panou putin mai ciudat. Panoul consta din multe becuri dispuse sub forma unei matrice de N linii pe M coloane. Initial toate becurile sunt stinse, iar Gabriela trebuie sa aprinda unele dintre acestea. Problema este ca singura operatie permisa este alegerea unei submatrice de L pe L si schimbarea starii tuturor becurilor din acea submatrice. Gabriela vrea sa stie care este numarul minim de operatii astfel incat sa aduca becurile in starea finala ceruta.
Date de intrare
Fişierul de intrare electrica.in va contine pe prima linie numerele N, M si L. Urmatoarele N linii vor contine fiecare cate M numere 0 sau 1 (nedespartite prin spatii) reprezentand starea finala a becurilor ( O pentru stins si 1 pentru aprins).
Date de ieşire
Fişierul de ieşire electrica.out va contine o singura linie continand numarul minim de operatii pentru a aduce becurile in starea finala, sau numarul -1 in caz ca acest lucru nu este posibil.
Restricţii
- 1 ≤ L ≤ N, M ≤ 1000
- Pentru 40% din teste 1 ≤ N, M ≤ 100
- Pentru 60% din teste 1 ≤ N, M ≤ 500
- Atentie: submatricea reprezinta extinderea bidimensioanala a subsecventei si nu a subsirului
Exemplu
| electrica.in | electrica.out |
|---|---|
| 4 4 3 1110 1001 1001 0111 | 2 |
Explicaţie
Gabriela alege submatricile cu coltul stanga sus in punctele 1, 1 si 2, 2.
