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

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


Timp maxim de execuţie/test:
0.2 secunde
Memorie totală disponibilă/stivă:
16MB/8 MB

Lui OMan îi place viteza, aşa că s-a dus la schi! Pârtia este de formă pătrată şi este împărţită în n x n pătrate egale numerotate de la stânga la dreapta şi de sus în jos cu numere de la 1 la n.
Fiecare pătrăţel are asociată o anumită înălţime exprimată în milimetri. OMan pleacă din pătratul de coordonate (1, 1) cu viteza iniţială 1 şi trebuie să ajungă în pătratul de coordonate (n, n) cu viteză maximă. Aflându-se într-un pătrat de coordonate (i, j), OMan poate trece fie în pătratul din sud, adică de coordonate (i+1, j), fie în pătratul de la est, adică de coordonate (i, j+1). La fiecare pas, dacă pătratul în care se află are înălţimea x iar pătratul vecin are înălţimea y, atunci viteza sa creşte cu x – y (dacă x >= y), sau scade cu y – x (dacă x < y). Mai mult, dacă pasul curent schimbă direcţia faţă de direcţia de la pasul anterior, atunci viteza cu care ajunge în pătratul vecin se înjumătăţeşte (se obţine câtul împărţirii la 2).
De exemplu, presupunem că OMan a ajuns din (2, 5) în (3, 5) (deci mergând pe direcţia sud) cu viteza de 10 şi pătratul (3, 5) are înălţimea 8. Acum OMan se deplasează spre est, deci în pătratul (3, 6) de înălţime 5. Atunci înseamnă că a schimbat direcţia şi viteza sa în pătratul (3, 6) este (10+8–5)/2 = 6. Evident, OMan nu se poate deplasa cu viteză negativă sau zero.

Cerinţă

Scrieţi un program care determină viteza maximă pe care o poate obţine OMan în pătratul de coordonate (n, n) plecând din pătratul de coordonate (1,1) cu viteza iniţială 1.

Date de intrare

Fişierul speed.in conţine pe prima linie numărul natural n, iar pe următoarele n linii şi n coloane sunt date înălţimile celor n x n pătrate ale pârtiei.

Date de ieşire

Fişierul speed.out va conţine un singur număr natural reprezentând viteza maximă.

Restricţii

  • 2 <= n <= 300
  • înălţimile  pătratelor sunt numere naturale cuprinse între 0 şi 1000
  • Dacă OMan nu poate ajunge în poziţia (n, n) datorită vitezei mai mici sau egale cu 0, atunci în fişier se va afişa valoarea 0
  • Din poziţia (1,1) OMan se poate deplasa în ambii vecini de la est şi sud fără a se considera că schimbă direcţia.

Exemplu

speed.in speed.out Explicaţii
3
9 8 6
9 5 2
7 1 1
5
Traseul care îi dă viteză maximă este:
din (1,1) în (1,2) – viteză 1+(9–8)=2
din (1,2) în (1,3) – viteză 2+(8–6)=4
din (1,3) în (2,3) – viteză (4+5–1)/2=4 (a schimbat direcţia)
din (2,3) în (3,3) – viteză 4+(2–1)=5.
prof. Dan Pracsiu
Liceul "Stefan Procopiu" Vaslui
dpracsiu@yahoo.com
prof. Adrian Panaete
Colegiul National „A. T. Laurian” Botoşani
acpanaete@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
surse trimise | ajutor