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

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


Timp maxim de executie/test:
0.4 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Seiful bancii romane este format din N siruri a cate M sertare de dimensiuni egale dispuse unul langa altul. Dimineata cand se deschide banca toate sertarele sunt inchise. In timpul zilei banca va primii bani (monede), iar angajatii bancii vor pune monedele in sertare aleatoare. La sfarsitul zilei un robot trebuie sa rearanjeze monedele astfel incat in toate sertarele deschise sa fie aceelasi numar de monede. El nu va lua in considerare sertarele inchise. Robotul se misca doar orizontal sau vertical. Efortul facut de robot pentru a muta P monede este egal cu P*nr, unde font face="Courier New, Courier, mono">nr este numarul de sertare peste care trece robotul.

Cerinta

Scrieti un program care sa gaseasca efortul minim efectuat de robot pentru a rearanja monedele. Se garanteaza existenta unei solutii.

Date de intrare

Pe prima linie a fisierului de intrare monede1.in sunt scrise numerele naturale N M separate printr-un singur spatiu.
Pe urmatoarele N linii sunt scrise cate M numere separate prin spatii reprezentand numarul de monede din sertare. Daca numarul de monede este 0 inseamna ca sertarul este inchis si nu va fi luat in considerare de robot.

Date de iesire

Prima linie a fisierului monede1.out va contine efortul minim cerut.

Restrictii

  • 1 < N, M < 128
  • 2 < numarul de sertare deschise < 128
  • 0 < numarul de monede dintr-un sertar < 1024

Exemplu

monede1.in

monede1.out

5 4
2 4 0 1
0 0 0 0
4 0 0 0
0 0 0 0
0 1 0 6          

17

Fechete Dan Ionut
Universitatea Bucuresti, Facultatea de Matematica si Informatica
mailto:f.dan.ionut@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: 2sec, croco, judete, tetris2, trafic, mesaj1, diamant, ratina, import, drept1, gard, pitici1, curent
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre flux: matrice2, furtuna, croco, kimberley, datorii, trafic, sponsori, bomboane, algola, trasee, drumuri, magic5, teroristi, universitate, terenuri3d, asfalt1
surse trimise | ajutor