Fişierul intrare/ieşire:electrica.in, electrica.outSursăAlgoritmiada 2009, Runda Finala
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.15 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Electrica

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content