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

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


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

Se consideră o matrice cu M linii şi N coloane. În fiecare celulă (element) a matricei este memorat câte un număr întreg. Numim „Z” o mulţime de celule din matrice formată dintr-un grup de celule consecutive, situate pe aceeaşi linie, legate printr-un şir de celule, situate în diagonală (pe direcţia Nord-Est -> Sud-Vest), de un alt grup de celule consecutive situate pe o altă linie a matricei, neadiacentă (neconsecutivă) cu prima linie (adică între linia de sus şi cea de jos a unui “Z” să mai existe cel puţin încă o linie a matricei).
Un astfel de„Z” îndeplineşte condiţiile:
• fiecare dintre cele două linii orizontale ale „Z”-ului are cel puţin două celule;
• diagonala începe cu celula cea mai din dreapta a liniei de sus a „Z”-ului, fiecare dintre celulele următoare se află imediat în stânga şi în jos faţă de cea anterioară, ultima celulă a diagonalei este cea mai din stânga celulă a liniei de jos a „Z”-ului.
Dintre imaginile următoare, doar imaginea E conţine un „Z”:



Asociem fiecărui astfel de „Z” un cost egal cu suma numerelor memorate în celulele care alcătuiesc „Z”-ul.

Cerinţă

Scrieţi un program care să citească numerele naturale M şi N, cele MxN numere memorate în celulele matricei şi să determine cel mai mare cost al unui „Z” din matrice.

Date de intrare

Fişierul de intrare zmax.in conţine pe prima linie numerele naturale M şi N, separate printr-un spaţiu. Pe fiecare dintre următoarele M linii se găsesc câte N numere întregi, separate de câte un spaţiu.

Date de ieşire

Fişierul de ieşire zmax.out va conţine pe prima linie un singur număr întreg reprezentând cel mai mare cost al unui „Z” din matrice.

Restricţii

3 <= M, N <= 500
• Numerele memorate în celulele matricei sunt numere întregi din intervalul închis [-10000,10000]

Exemple

zmax.inzmax.outExplicaţii
5 4 3 -5 -2 4 -2 7 1 -3 1 1 1 1 2 -3 2 -3 3 -2 1 -4 10 3 -5 -2 4
-2 7 1 -3
1 1 1 1
2 -3 2 -3
3 -2 1 -4

Matricea are 5 linii şi 4 coloane şi conţinutul din imaginea alăturată.
Cel mai mare cost care poate fi asociat unui „Z” din matrice(„Z” -ul din imagine) este 10.



autor: Prof. Nistor-Eugen Moţ
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONIGIM 2013: cursa1, patrate7, secvp, latin, swap, extraprime, greieri, onigim, divizori1, remi1, tetris3, amestec, sudoku1, eoliene
De acelaşi autor: cursa, insule, termen, div, mese, hperm, zmeu, chimie2, mere2, vile, dans, multiplu, paralel, divizor, ghici, barca1, fibo, parc, circular, sant, mobile, pattern, mutare, concurs2, soricel1, soricel2, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, pion, el, tort1, triunghi4, bile6
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, 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, 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, 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, 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
surse trimise | ajutor