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

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


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

Se dă o matrice cu R linii şi C coloane de numere distincte de la 1 la R*C. Bemo, personajul emoţional, doreşte să urmărească cel mai bun drum din colţul superior stânga, de coordonate (1, 1), în colţul inferior dreapta, de coordonate (R, C).

Un drum este o secvenţă de numere din matrice în care fiecare număr se găseşte în jos sau la dreapta numărului anterior; cu alte cuvinte dacă (i, j) este poziţia unui număr de pe drum, atunci următorul număr poate fi cel de pe poziţia (i+1,j) sau cel de pe poziţia (i,j+1). Pentru a determina dacă un drum A este mai bun decât un drum B, numerele fiecărui drum se vor sorta şi se va alege cel mai mic lexicografic, e.g. [1,3,5,6,8] < [1,4,5,6,7].

Cerinţă

Să se determine cel mai bun drum pe care Bemo îl poate alege.

Date de intrare

Fişierul de intrare bemo.in conţine pe prima linie două numere naturale R şi C, unde R este numărul liniilor, iar C numărul coloanelor matricei lui Bemo. Pe următoarele R linii se vor găsi câte C numere separate printr-un spaţiu. Fiecare număr va fi unic şi va fi cuprins în intervalul [1, R*C].

Date de ieşire

Fişierul de iesire bemo.out va conţine R+C-1 numere reprezentând cel mai bun drum pe care Bemo îl poate alege. Numerele vor fi separate prin câte un spaţiu.

Restricţii

0 < R, C < 1250
• Spunem că un drum A=(A1,A2,...,AR+C-1) este mai mic lexicografic decât un drum B=B1, B2,...,BR+C-1) dacă există o poziţie p astfel încât Ap < Bp şi A1 = B1, A2 = B2,..., Ap-1 = Bp-1.

Exemple

bemo.inbemo.out
4 4 7 4 13 3 8 11 12 2 10 9 1 5 16 14 15 6 7 4 11 9 1 5 6

autor: Student Marius Stroe
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2013: split, momente, gradina1, secvente2, flori2, romb1, cumpanit, spider, zone, taxa, ausoara, drumuri2, confuzie, xnumere, aranjare2, showroom, cntgcd
De acelaşi autor: gaz, arb1, ubuntzei, subsecvente, ausoara
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, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor