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

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


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

Ionică are un joc a cărui tablă conţine NxM turnuleţe de înălţimi distincte, dispuse pe N linii şi M coloane.
Jocul conţine şi o bilă pe care Ionică o poate aşeza pe oricare turnuleţ al tablei. Din orice poziţie s-ar afla, bila va cădea pe turnul vecin de înălţime minimă, doar dacă înălţimea acestuia este strict mai mică decât a turnuleţului unde se află bila. Două turnuri sunt vecine dacă ele se află pe aceeaşi linie şi pe coloane alăturate sau pe aceeaşi coloană şi pe linii alăturate. Bila se rostogoleşte până când ajunge pe un turn care nu are un turn vecin cu înălţime strict mai mică. Tabla este înconjurată de o bordură mai înaltă decât orice turn al ei.

Cerinţă

Realizaţi un program care afişează numărul maxim de turnuri pe care se poate rostogoli bila, precum şi cea mai mică înălţime a unui turn pe care trebuie aşezată iniţial bila astfel încât să se rostogolească pe un număr maxim de turnuri.

Date de intrare

Fişierul de intrare bila.in conţine pe prima linie numerele naturale N şi M. Pe fiecare dintre următoarele N linii se află câte M numere naturale reprezentând înălţimile turnuleţelor aflate pe fiecare linie a tablei. Valorile scrise pe aceeaşi linie sunt separate prin spaţii.

Date de ieşire

În fişierul de ieşire bila.out se vor afişa pe prima linie, separate printr-un spaţiu, două numere naturale MAX HMIN reprezentând, în ordine, numărul maxim de turnuri pe care se poate rostogoli bila (inclusiv turnul de plecare) şi, respectiv, înălţimea cea mai mică a unui turn pe care poate fi plasată iniţial bila astfel încât să se rostogolească pe MAX turnuri.

Restricţii

1 < N ≤ 125
1 < M ≤ 125
• Înălţimile turnurilor de pe tablă sunt distincte două câte două.
1 ≤ Înălţimile turnurilor ≤ 65000

Exemple

bila.inbila.outExplicaţii
5 5 109 120 4 5 7 107 212 1 100 8 106 105 103 101 12 6 10 104 102 9 3 2 19 20 21 7 101


Bila se va rostogoli în ordine peste turnurile de înălţime
101 12 8 7 5 4 1

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONIG 2010: control1, figura, joc14, fractie1, neuroni, raze, char, maraton1, roboti1, cluburi, domino1, dartz
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
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, 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, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor