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

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


Timp maxim de execuţie/test:
0.3 secunde
Memorie totala disponibilă/stivă:
64 MB/8 MB

Fie o matrice cu N linii şi N coloane de numere naturale. Liniile şi coloanele sunt numerotate de la 1 la N. Se doreşte traversarea matricei pe un drum pornind din poziţia (1, 1) în (N, N), mergând pas cu pas. La un pas, de la o poziţie (i, j) se poate trece într-una din poziţiile (i+1, j), (i+1, j+1), (i, j+1). Costul drumului este dat de suma valorilor componentelor care fac parte din drum.

Cerinţă

Scrieţi un program care determină un drum de cost maxim de la poziţia (1, 1) la (N, N) şi cu proprietatea că acest cost maxim este multiplu de 3.

Date de intrare

Fisierul de intrare maxtri.in conţine pe prima linie un număr natural N, iar pe următoarele N linii se află câte N numere naturale separate prin câte un spaţiu reprezentând valorile de pe o linie din matrice.

Date de ieşire

Fisierul de iesire maxtri.out va conţine un singur număr natural reprezentând costul maxim divizibil cu 3 al unui drum de la poziţia (1, 1) la (N, N). Dacă nu există niciun drum de cost divizibil cu 3, se va afişa valoarea 0.

Restricţii

  • 1 <= n <= 500
  • Elementele matricei sunt numere naturale cuprinse între 1 şi 10 000

Exemple

maxtri.in maxtri.out Explicaţii
3
2 3 1
5 6 7
9 8 4
24 Drumul de cost maxim trece prin componentele de coordonate (1,1) (2,1) (2,2) (2,3) (3,3). Costul său este 2+5+6+7+4 = 24, iar 24 este divizibil cu 3.
De remarcat că există drumuri de cost mai mare, dar care nu sunt divizibile cu 3.
maxtri.in maxtri.out Explicaţii
3
1 3 3
3 3 3
3 3 3
0 Nu există niciun drum de la (1,1) la (3,3) de cost divizibil cu 3.

prof. Dan Pracsiu
Grupul Şcolar „Ştefan Procopiu” Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la XOR 2012: proddiv, perechi2, expeval, combcuv, dfs
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
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, 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, 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, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 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 Lee: inginer, insule, lbd, ocean14, iepuras2, sah, radio, lacuri, castel, excursia, soricel2, masina2, paianjen, suma2, soricel3, cub2, alee, rj, taxe1, sotron1, tom, ny, ai, robot3, pixy, valet, oras1, lgdrum, gheizere, abq, cartite, joc21, traseu3, wow, panda
surse trimise | ajutor