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

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


Timp maxim de execuţie/test:
0.1 secunde
Memorie totală disponibilă/stivă:
16MB/1 MB

Primarul oraşului Xcity a hotărât să cumpere pentru piaţa principală o instalaţie electrică în vederea sărbătorilor de iarnă. Aceasta are formă dreptunghiulară cu n linii şi m coloane. În dreptul fiecărei coloane se află un comutator în urma acţionării căruia becurile de pe acea coloană îşi schimbă configuraţia (cele aprinse se sting, cele stinse se aprind). La punerea sub tensiune a instalaţiei aceasta are o configuraţie predefinită a becurilor (unele sunt stinse, altele aprinse). Primarul doreşte ca pentru seara de Crăciun, în configuraţia instalaţiei să fie cât mai multe stele. O stea este o configuraţie de becuri aprinse care are exact forma din figură:

*
*
*
*
*

Cerinţă

Dându-se configuraţia instalaţiei la punerea sub tensiune, să se determine numărul maxim de stele care se pot obţine.

Date de intrare

Fisierul stele.in conţine pe prima linie două numere naturale n m separate printr-un spaţiu (numărul de linii respectiv de coloane). Pe următoarele n linii se afla câte m valori 0 sau 1, separate prin cate un spaţiu reprezentând configuraţia instalaţiei la punerea sub tensiune (1-bec aprins, 0-bec stins).

Date de ieşire

Fisierul stele.out conţine o singura linie pe care va fi scris numărul maxim de stele ce se pot obţine.

Restricţii

  • 1 <= n <= 100
  • 1 <= m <= 10
  • Două stele se pot suprapune parţial sau pot fi formate din becuri vecine.

Exemplu

stele.in stele.out Explicatie
3 4
1 0 0 0
1 0 0 0
0 0 0 1
2

Dacă se intorc coloanele 2,3,4 se obţine
1 1 1 1
1 1 1 1
0 1 1 0

Cele două stele au centrul in poziţiile (2,2) şi (2,3).

prof. Marius Nicoli
Colegiul Naţional „Fraţii Buzeşti” Craiova
mariusnicoli@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: secvente1, raze, bile5, 235, dreptunghiuri, triunghi2, albine1, puteri35, miere, left, arbgraf, reuniune, cazare, atletism, fluviu, zar1, poteci, avioane, obstacole, liste, acoperire1, minusk, efect, b2k, progresii, reconst, mijloc, romb, alune, patru, galbeni, schi1, restaurare, sort2dist
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, becuri, 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, 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
Despre baze de numeraţie: balanta, gray, np, nr01, tablou, aritma, joc8, numere6, ceas2, paritate, test1, visul, numere9, accesibil, puteri35, sumb, joct, minmax, secvb, goe, copii, b2k, becuri2, codpatrat, patrate7, cifrab, b210
Despre generare: taste, pluricex, balbe, magic3, formule, grup, zmeu, nr01, reteta2, playlist, pizza1, caramele, caini, tvshow, adevar, prime1, hexa, premii1, carti2, bile4, hof, matrx, cubinvers, arctir, guess, minmax, tablou1, adunscad, sumprod, prisme, operatii1, expeval, triburi1, optim, patru, genab, dineu, cumpanit, nkd, relatii, wb
surse trimise | ajutor