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

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


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

Tina are o mică livadă cu copaci din specii diferite. Numărul acestora este m x n, iar poziţionarea lor este în centrul celulelor unei reţele cu m linii şi n coloane. Tina a sădit toţi copacii în aceeaşi zi. Fiecare copac, indiferent de specie, creşte cu câte 1 centimetru în fiecare zi în care nu este udat. În fiecare zi în care este udat, oricare copac creşte X centimetri. Se cunoaşte pentru fiecare copac situat pe linia i şi coloana j în livadă, înălţimea maximă hij pe care acesta poate să o atingă. Din momentul în care ajung la înălţimea maximă, copacii nu mai cresc şi nu depăşesc această înălţime, indiferent dacă mai sunt udaţi sau nu în zilele următoare. Înălţimile iniţiale ale copacilor se neglijează.
Tina nu este suficient de puternică pentru a căra multă apă într-o zi, motiv pentru care va uda cel mult un copac pe zi.

Cerinţă

Ajutaţi-o pe Tina să găsească o stratetegie potrivită pentru a uda livada, astfel încât toţi copacii să ajungă în timpul cel mai scurt la înălţimea maximă.

Date de intrare

Fişierul de intrare livada.in conţine pe prima linie trei numere naturale m n X. Pe fiecare dintre următoarele m linii se găsesc câte n numere naturale, reprezentând înălţimile maxime hij. Al j-lea număr de pe linia i+1 este hij.

Date de ieşire

Fişierul de ieşire livada.out va conţine o singură linie pe care se va scrie un număr natural Z, reprezentând numărul minim de zile necesare Tinei să-şi vadă toţi copacii din livadă ajunşi la înălţimile lor maxime.

Restricţii

1 < n, m <= 150
1 <= X <= 1000
1 <= h1 ... hn <= 10000

Orice copac poate fi udat de mai multe ori, în zile nu neaparat consecutive.

Exemple

livada.inlivada.outExplicaţii
1 2 3 3 5 3 Copacul de înălţime 5 este udat cel puţin o zi. Dacă este udat o zi, atunci mai sunt necesare încă două zile pentru ca atât primul, cât şi al doilea copac să ajungă la înălţimea maximă
1 3 5 4 5 2 2 Tina udă câte o zi copacii de înălţimi maxime 4 şi 5 şi nu udă copacul de înaţime 2
2 2 4 2 3 4 5 3 Tina udă în prima zi copacul de înălţime 4, iar în a doua zi pe cel de înălţime 5. Mai este nevoie şi de a treia zi pentru ca pomul de înălţime maximă 3 să-şi atingă limita de creştere

autor: Prof. Constantin Gălăţan
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2008: sir2, drept, monede, ocean14, seif, aztec, pendul, plopi
De acelaşi autor: ozn, pod, numere, vikingi, furtuna, teatru, iepuras2, kimberley, novel, friends2, stalpi, tabara, sport, randuri, panouri, powerpuff, cartele, joc15, stalpi1, autostrazi, telecab, pseudobil, harta2
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, 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, 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 căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
surse trimise | ajutor