.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » becuri

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
becuri


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
16MB / 1MB

Un panou publicitar de formă dreptunghiulară conţine becuri, unul lângă altul, aliniate pe n linii şi m coloane.
Fiecare bec are asociat un comutator. Prin acţionarea comutatorului unui bec se schimbă starea tuturor becurilor de pe linia lui şi de pe coloana lui, în afară de starea sa. Prin schimbarea stării înţelegem trecerea din starea în care se află în starea opusă (stins → aprins, aprins → stins).

Cerinţă

Să se realizeze un program care determină numărul minim de acţionări de comutatoare astfel încât în final toate becurile de pe panou să fie stinse, dacă acest lucru este posibil.

Date de intrare

Fişierul de intrare becuri.in are pe prima linie două numere naturale separate prin spaţiu n şi m reprezentând numărul de linii, respectiv numărul de coloane ale panoului publicitar.
Următoarele n linii vor conţine câte m î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 ≤ n, m ≤ 500

Exemple

becuri.inbecuri.outExplicaţii
3 3 0 0 1 0 0 1 1 1 0 1 Acţionăm comutatorul din poziţia (3, 3).

autor: Cosmin Negruşeri
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot PH 2006: arbfind, team, drept1, gard, pitici1, rsp, sir5
De acelaşi autor: grazing, vitale, poze, patrate5, hawaii
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor