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

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


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

Fie o matrice lidoriană de x linii şi y coloane. Liniile matricei se numerotează de jos în sus, cu numere de la 0 la x-1. Coloanele matricei se numerotează de la dreapta la stânga, cu numere de la 0 la y-1. Matricea lidoriană este formată doar din valori „1” şi „0”.



Pentru fiecare linie i, se calculează sli ca suma tuturor produselor dintre a(i,j) şi 2j. Pentru fiecare coloană k, se calculează sck ca suma tuturor produselor dintre a(i,k) şi 2i .



Fie S1 suma tuturor sumelor calculate pe linii şi fie S2 suma tuturor sumelor calculate pe coloane.
S1= Sl0+ Sl1+ Sl2 S2= Sc0+ Sc1+ Sc2 + Sc3
Considerăm t=S1+ S2. Se înţelege prin „mutare” o interschimbare între oricare două valori „1” şi „0” din matrice.
Jocul lidorian presupune executarea unui număr minim de mutări, astfel încât valoarea lui t să fie minimă.

Cerinţă

Să se scrie un program care să permită calcularea valorii minime a lui t. Pentru această valoare a lui t, se cere să se determine numărul minim de mutări necesare.

Date de intrare

Fişierul de intrare joc8.in conţine în ordine, pe linii:
x y număr de linii,număr de coloane despărţite printr-un spaţiu
ax-1,y-1 ax-1,y-2 … ax-1,0 elementele liniei x-1, fără spaţii între ele
ax-2,y-1 ax-2,y-2 … ax-2,0 elementele liniei x-2, fără spaţii între ele

a0,y-1 a0,y-2 … a0,0 elementele liniei 0, fără spaţii între ele

Date de ieşire

Fişierul de ieşire joc8.out conţine, în ordine, pe prima linie, valoarea t, apoi numărul minim de mutări, cu un singur spaţiu între ele.

Restricţii

2 <= x, y <= 12
matricea conţine cel puţin o cifră de 1

Exemple

joc8.injoc8.outExplicaţii
5 6 100010 010000 000001 000010 011000 28 5


autor: Prof. Rodica Pintea
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, bifo, joc9, pal, romeo, seceta, antena, avere, joc11, paianjen, suma2, vizibil, masina3, csir, lsort, patrat, ziduri, anticip, bsir, evantai, galax, spion, texan
De acelaşi autor: fisc, cartonase2, cartoane, tramvai1, suma2, sg1, volei1, team, elfi, cezar1, piramida1, mosia, vanatoare, spirala1, poligon3, panglica, cerc, tablou1, radioactiv, solitar
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, 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, 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, 2ndesc, 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, numere6, ceas2, paritate, test1, visul, numere9, accesibil, puteri35, sumb, joct, minmax, stele, secvb, goe, copii, b2k, becuri2, codpatrat, patrate7, cifrab, b210
Despre tablou: cuburi1, zuzu, robinson, cuburi2, joc9, suma2, vizibil, masina3, cub2, lacusta, furnica, numere8, copaci1, ogorul, pesti, stelar, macheta, mxl, segmente, joc19, triunghi4, parc1, interclasare, rascoala, cifre5, monede2, betisoare, qvect, traseu3
surse trimise | ajutor