Fişierul intrare/ieşire:traseu4.in, traseu4.outSursăOJI 2019, clasa a 10-a
AutorIonel-Vasile Pit-RadaAdăugată detamionvTamio Vesa Nakajima •tamionv
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Traseu4

O suprafaţă de teren de formă dreptunghiulară este divizată în N fâşii orizontale şi M fâşii verticale, de lăţimi egale. Se formează astfel N x M zone de formă pătrată, cu latura egală cu o unitate. Astfel, suprafaţa este reprezentată sub forma unui tablou bidimensional cu N linii şi M coloane, în care pentru fiecare zonă este memorat un număr ce reprezintă altitudinea zonei respective. Interesant este că în tablou apar toate valorile $1, 2, …, N*M. Suprafaţa este destinată turismului. Deoarece spre laturile de Est şi Sud ale suprafeţei există peisaje de o frumuseţe uimitoare, se doreşte găsirea unor trasee turistice în care deplasarea să se realizeze cu paşi de lungime unitară mergând doar spre Est şi spre Sud. O comisie, care trebuie să rezolve această problemă, a stabilit că un traseu este atractiv dacă şi numai dacă ultima poziţie a traseului are altitudinea mai mare decât prima poziţie a traseului. Un traseu poate începe, respectiv se poate încheia, în oricare dintre zonele terenului, cu respectarea condiţiilor anterioare.
Se cere să se determine numărul maxim Z de zone pe care le poate avea un traseu atractiv.

Date de intrare

În fişierul de intrare traseu4.in se află scrise pe prima linie numerele N şi M, cu semnificaţia din enunţ. Pe fiecare dintre următoarele N linii se află scrise câte M numere naturale, reprezentând, elementele tabloului bidimensional precizat în enunţ. Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.

Date de ieşire

În fişierul de ieşire traseu4.out se va scrie numărul Z, cu semnificaţia din enunţ. Dacă nu există niciun traseu atractiv, atunci se va scrie 0.

Restricţii

  • 1 ≤ N ≤ 500
  • 1 ≤ M ≤ 500
  • Pentru teste in valoare de 40 de puncte, N ≤ 50 şi M ≤ 50
  • 10 puncte sunt din oficiu: corespund unor teste egale cu primul exemplu.

Exemplu

traseu4.in
traseu4.out
Explicaţii
3 4
12 11 10 6
7 5 4 3
9 2 8 1
4
Traseele atractive de lungime 2 sunt: 7-9, 4-8, 2-8
Traseele atractive de lungime 3 sunt: 5-2-8, 5-4-8
Traseele atractive de lungime 4 (maximă) sunt:
7-5-4-8, 7-5-2-8, 7-9-2-8.
3 3
5 8 7
9 6 4
3 1 2
3
Traseele atractive de lungime 2 sunt: 5-8, 5-9, 1-2
Traseele atractive de lungime 3 (maximă) sunt: 5-9-6,5-8-6,5-8-7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?