| Fișierul intrare/ieșire | becuri.in, becuri.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Adăugată de |
Radu Muntean
•
heracle
|
|
| Timp de execuție pe test | 0.3 sec | Limită de memorie | 512 KB |
| Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Becuri
La un muzeu din orasul nostru, gardianul, imediat dupa inchiderea muzeului, trebuie sa stinga toate luminile din camera principala. Patronul, observand consumul de curent mult prea mare al muzeului, s-a hotarat sa nu mai aprinda toate luminile in fiecare camera, ci doar cateva pentru a nu ramane pe intuneric.
Camera principala are forma dreptunghiulara(de matrice) si contine becurile unul langa altul, aliniate pe l linii si c coloane. Stiind ca exista l+c comutatoare(dispuse la capatul fiecarei coloane sau linii) care schimba starea tuturor becurilor de pe linia sau coloana la care este distribuit, gardianul vrea sa determine numărul minim de actionări de comutatoare astfel incat în final toate becurile de pe panou sa fie stinse, dacă acest lucru este posibil.
Prin schimbarea starii întelegem trecerea din starea in care se afla în starea opusa (stins → aprins, aprins → stins).
Date de intrare
Fișierul de intrare becuri.in are pe prima linie două numere naturale separate prin spațiu l și c reprezentând numărul de linii, respectiv numărul de coloane ale panoului publicitar.
Următoarele l linii vor conține câte c întregi separați prin câte un spațiu, fiecare întreg reprezentând starea inițială a unui bec, 1 dacă becul este aprins și 0 dacă acesta este stins.
Date de ieșire
Fișierul de ieșire becuri.out va conține o singură linie pe care se va scrie un întreg ce reprezintă numărul minim de acționări de comutatoare pentru a stinge toate becurile, sau -1 dacă pentru configurația inițială dată nu există soluție.
Restricții
1<l,c<20;
Exemplu
| becuri.in | becuri.out |
|---|---|
| 4 4 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 |
3 |
| becuri.in | becuri.out |
|---|---|
| 4 4 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 |
-1 |
Explicație
apasand intrerupatorul liniei 1 si 4 vom obtine
0 0 1 0
0 0 1 0
0 0 1 0
0 0 1 0
apasand intrerupatorul coloanei 3 se vor stinge toate becurile
