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

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


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

Nu se ştie de ce, ai decis subit să începi o carieră în construcţii. Zidurile pe care le construieşti sunt formate din cărămizi cubice de latură 1, aşezate în mai multe straturi.
Pentru a proiecta un astfel de zid, ai trasat un caroiaj format din MxN pătrate de latură 1, organizate în M linii şi N coloane. Liniile caroiajului sunt numerotate de la 1 la M, începând de jos în sus, iar coloanele sunt numerotate de la 1 la N de la stânga la dreapta.
Fiecare căsuţă a caroiajului are asociat un anumit cost, care trebuie plătit în cazul în care plasăm o cărămidă în căsuţa respectivă. Costul construirii unui zid este egal cu suma costurilor căsuţelor în care sunt plasate cărămizile zidului.
Zidurile tale trebuie să respecte următoarele condiţii:
1. fiecare strat de cărămizi este format dintr-o singură secvenţă de cărămizi, oricare două cărămizi consecutive fiind adiacente (mai exact, cărămizile de pe un strat sunt plasate în căsuţe ale caroiajului situate pe aceeaşi linie, pe coloane consecutive);
2. cel puţin o cărămidă de pe fiecare strat i trebuie să fie aşezată pe o altă cărămidă de pe stratul de dedesubt
(i-1); cel mai de jos strat trebuie să fie aşezat pe pământ (pământul fiind sub linia 1 a caroiajului);
3. numărul de cărămizi folosit în construcţia zidului nu trebuie să depăşească un număr natural X.



Cerinţă

Fiind un zidar dornic de afirmare şi ştiind că dispui de o sumă de T euro, calculează numărul maxim de cărămizi pe care le poţi folosi în construcţia unui zid care costă cel mult T euro.

Date de intrare

Fişierul de intrare zidar.in conţine pe prima linie patru numere naturale M N X T separate prin câte un spaţiu cu semnificaţia din enunţ. Pe fiecare dintre următoarele M linii se află câte N numere naturale cuprinse între 1 şi 100 reprezentând costul aşezării unei cărămizi pentru fiecare dintre căsuţele caroiajului (mai precis, elementul j de pe a (i+1)-a linie a fişierului de intrare reprezintă costul aşezării unei cărămizi în căsuţa de pe linia i şi coloana j a caroiajului).

Date de ieşire

Fişierul de ieşire zidar.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul maxim de cărămizi pe care îl poate conţine zidul tău, respectând condiţiile impuse.

Restricţii

1 ≤ M ≤ 50
1 ≤ N ≤ 20
1 ≤ X ≤ 60
1 ≤ T ≤ 10000

Pentru 30% din teste T ≤ 60. Pentru 60% din teste N ≤ 10.

Exemple

zidar.inzidar.outExplicaţii
4 5 20 8 2 2 3 2 1 4 7 1 2 3 2 1 1 1 1 1 2 5 7 3 6 Pentru a construi zidul marcat în figură ai nevoie de exact 8 euro. Nu se pot construi ziduri cu mai multe cărămizi folosind această sumă de bani.



autor: Adrian Vladu
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, randuri, desc, felinar, joc6, log, maxq, tric, cover, dist, munte1, promo, puncte1, role
De acelaşi autor: castel, cover, centru
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, 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, parcela, 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 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, 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 recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor