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

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


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

Se consideră un tablou bidimensional cu m linii şi n coloane. Se numeşte traseu în V o parcurgere prin elementele tabloului astfel:
- se pleacă întotdeauna dintr-un element de pe prima linie a tabloului, se ajunge în final într-un alt element de pe prima linie a tabloului, trecând prin cel puţin 3 elemente, fără a trece printr-un element de mai multe ori;
- parcurgerea elementelor tabloului se face în forma unei singure litere V ca în desen, dintr-un element putându-se trece doar într-un alt element imediat vecin pe diagonală.
Fiecare element al tabloului conţine valori întregi. La parcugerea traseului se calculează suma elementelor de pe traseu.

Cerinţă

Determinaţi traseul în V care are suma maximă. În cazul în care există mai multe trasee de sumă maximă, se va alege traseul care parcurge cele mai puţine elemente. Dacă şi în acest caz există mai multe soluţii, se alege traseul cel mai din stânga (cel cu indicele coloanei de pornire cel mai mic).

Date de intrare

Din fişierul de intrare v.in se citesc de pe prima linie valorile naturale m şi n, separate printr-un spaţiu, reprezentând numărul de linii şi numărul de coloane ale tabloului. Pe următoarele m linii se află câte n valori întregi separate prin spaţii, reprezentând elementele tabloului.

Date de ieşire

Fişierul de ieşire v.out va conţine o singură linie pe care vor fi scrise trei valori naturale S C L, reprezentând suma maximă, coloana de pornire şi respectiv linia pe care se află vârful V-ului traseului determinat.

Restricţii

• 0 < m, n < 102
• -60000 <=
valorile elementelor tabloului <= 60000
Pentru datele de test suma valorilor din elementele oricărui traseu nu depăşeşte 1 000 000 000.

Exemple

v.inv.outExplicaţii
5 9 3 4 12 4 6 7 9 5 12 0 4 5 7 9 -5 1 1 5 0 98 34 0 1 7 7 1 1 6 7 8 -9 0 2 3 5 22 47 62 31 55 0 83 23 77 10 54 1 3 Exemple de alte trasee care se pot crea conform datelor de mai sus, dar care au suma mai mică decât cea din rezultat:



autor: Prof. Roxana Tîmplaru
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2004: cuvinte1, gaina, materom, puncte3, rez, sortari, base3, coach, color, magic5, patrate6, turnuri, invsort, peri, trans, politie, sea, poligon3, sir7, poligon2, logic, coduri, snipers, sablon1, submdisj, jetoane, prodmax, printesa, palindrom, reziston
De acelaşi autor: numere4, tablou, numar1, prieteni2, roboti, numere6, cartonas, test1, cuvant, roboti1, asfalt, grupe2, joc17, numar5, munte3
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, 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
surse trimise | ajutor