Fişierul intrare/ieşire:rover.in, rover.outSursăOJI 2017, clasa a 10-a
AutorMircea Lupse-TurpanAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rover

NASA plănuieşte o nouă misiune Rover pe Marte în anul 2020. Principalul obiectiv al acestei misiuni este de a determina, cu ajutorul unui nou Rover, dacă a existat în trecut viaţă pe Marte. Până când va fi lansată misiunea, Roverul este supus la tot felul de teste în laboratoarele NASA. Într-unul din teste, Roverul trebuie să parcurgă o suprafaţă de forma unui caroiaj cu N linii şi N coloane. Acesta porneşte din zona de coordonate (1,1) şi trebuie să ajungă în zona de coordonate (N,N), la fiecare pas putându-se deplasa din zona în care se află într-una din zonele învecinate la nord, sud, est sau vest. Pentru fiecare zonă de coordonate (i,j) se cunoaşte Ai,j, stabilitatea terenului din acea zonă. Ştiind că Roverul are o greutate G, o zonă cu stabilitatea terenului cel puţin egală cu G se consideră o zonă sigură pentru deplasarea Roverului, iar o zonă cu stabilitatea terenului mai mică decât G se consideră o zonă periculoasă pentru Rover.

Cerinţe

  1. Determinaţi numărul minim posibil de zone periculoase pe care le traversează Roverul pentru a ajunge din zona (1,1) în zona (N,N).
  2. Determinaţi greutatea maximă pe care o poate avea un Rover care să ajungă din zona (1,1) în zona (N,N), fără a traversa nicio zonă periculoasă pentru el.

Date de intrare

Pe prima linie a fişierului de intrare rover.in se găseşte numărul natural V a cărui valoare poate fi doar 1 sau 2. Dacă V este 1, pe a doua linie a fişierului de intrare se găsesc două numere naturale N şi G cu semnificaţia din enunţ, iar dacă V este 2, pe a doua linie a fişierului de intrare se află doar numărul N.
Pe următoarele N linii se află câte N numere Ai,j, reprezentând stabilitatea terenului din zona (i,j).

Date de ieşire

Fişierul de ieşire este rover.out.
Dacă valoarea lui V este 1, atunci fişierul de ieşire va conţine pe prima linie un număr natural reprezentând numărul minim de zone periculoase pe care trebuie să le traverseze Roverul de greutate G.
Dacă valoarea lui V este 2, atunci fişierul de ieşire va conţine pe prima linie un număr natural reprezentând greutatea maximă a unui Rover care poate ajunge din zona (1,1) în zona (N,N) fără a traversa zone periculoase pentru el.

Restricţii

  • Pentru 50% din teste V = 1, pentru 50% din teste V = 2.
  • 1 ≤ N ≤ 500
  • 1 ≤ G ≤ 5000
  • 1 ≤ Ai,j ≤ 10000
  • Zonele de coordonate (1,1) şi (N,N) nu sunt zone periculoase pentru Rover.
  • Roverul nu va trece de mai multe ori prin aceeaşi zonă.

Exemplu

rover.inrover.outExplicaţie
1
5 5
5 1 3 4 7
5 2 1 8 5
2 9 5 3 3
4 1 1 1 9
5 1 6 1 8
3
Numărul minim de zone periculoase traversate de la poziţia (1,1) până la poziţia (5,5) este 3.
2
5
5 1 3 4 7
5 2 1 8 5
2 9 5 3 3
4 1 1 1 9
5 1 6 1 8
2
Greutatea maximă a unui Rover care poate ajunge din zona (1,1) în zona (5,5) fără a trece prin zone periculoase pentru el este 2.

Explicaţie

Un traseu posibil a fost îngroşat în ambele exemple.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?