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

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


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

Ionica a primit moştenire de la bunici o parcelă de teren. Terenul este de formă dreptunghiulară şi este împărţit în mxn bucăţele de câte 1 m2, care pot fi identificate prin linia şi coloana pe care se găsesc (liniile numerotate de sus în jos cu 1, 2, ..., m, iar coloanele de la stânga la dreapta cu 1, 2, ..., n). Terenul conţine zone mlăştinoase. O zonă mlăştinoasă este formată din bucăţele mlăştinoase de câte 1 m2, astfel încat oricare două bucăţele din zonă fie sunt vecine, fie există o succesiune de bucăţele mlăştinoase din zonă vecine prin care se poate ajunge de la una la cealaltă. In plus, zona trebuie să fie maximală cu această proprietate. Două bucăţele de teren de câte 1 m2 sunt vecine dacă au cel puţin un punct comun.
Pentru că Ionel îşi iubeşte bunicii se hotărăşte ca toţi banii pe care îi are (suma S) să-i folosească la desecarea zonelor mlăştinoase din parcela de teren. Problema este că o zonă mlăştinoasă poate fi desecată complet sau deloc şi din acest motiv este posibil ca banii să nu-i ajungă pentru toate zonele mlăştinoase. Pentru desecarea unui m2 de teren mlăştinos se cheltuieşte 1 euro.

Cerinţă

Se cere să se determine suprafaţa maximă de teren care se poate deseca respectând regulile anterioare.

Date de intrare

Fişierul de intrare parcela.in conţine pe prima linie 3 numere naturale separate prin spaţii m n S, reprezentând numărul de linii, numărul de coloane din parcelă şi respectiv suma de bani. Pe următoarele m linii se află câte n cifre de 1 sau 0 separate prin câte un spaţiu ce codifică fiecare m2 din parcela de teren, cu semnificaţia 1 – mlaştină şi 0 – contrar.

Date de ieşire

Fişierul de ieşire parcela.out va conţine o singură linie pe care va fi afişat un număr natural reprezentând suprafaţă maximă de teren care se poate deseca cu suma disponibilă.

Restricţii

  • 0 < m, n <= 250
  • 0 < S <= 40000
Exemple
parcela.in parcela.out Explicaţie
4 5 6
1 1 0 0 0
0 0 1 0 1
1 0 0 0 0
1 1 1 0 0
5

Sunt trei zone mlăştinoase, de suprafeţe 3, 1 şi 4. Pentru fiecare ar trebui să se cheltuiască, 3, 1 şi respectiv 4 euro. Cu suma de bani 6 euro, putem deseca cel mult zonele cu suprafeţele 1 m2, respectiv 4 m2.


prof. Doru Popescu Anastasiu
C.N. "Radu Greceanu", Slatina
dopopan@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
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, stele, covor, subm, mess, secvnumber, cladire, ssmax, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: degrade, hora, noroc, test, tren, grad, palma, cs, h, vagoane, scaune, tir, nrcuv2, piata, vocale, prop, poligon, text2, onu2, creioane, exp, donald, young, albine, turn, linie, tub, suma1, triunghi, cod1, pic, zuzu, pav, prieteni1, banda10, numar2, prime1, ziduri, puncte2, texan, part, ucif, numere7, mare, furnica, pavare, cifre3, domino, exp1, coduri, efort, prodmax, char, dartz, operatii, jucarii, cd1, codif, bileprime, echipa, covor, pavari, grad1, ec, stalpi2, grad2, testament, nrpomi, elicop, triburi1, showroom, cartite
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre fill: rebus, sarpe, insule, lacuri, zuzu, joc11, gradina, dreptunghiuri, drenaj, fillmat, acces, tsunami, betasah, zona, zone, taxa, foto, ferma1, antitero, robotzi
surse trimise | ajutor