== include(page="template/taskheader" task_id="alpin") ==
==Include(page="template/taskheader" task_id="alpin")==
Poveste ...
Un alpinist se afla intr-o regiune muntoasa codificata sub forma unei matrici patratice de dimensiune $N$, fiecare element al matricii reprezentand altitudinea respectivei portiuni de teren. Alpinistul isi poate porni traseul din orice punct al regiunii ( deci de la oricare dintre elementele matricii ) si poate termina acest traseu oriunde. El poate merge pe oricare din directiile {N, S, E, V} cu conditia sa nu paraseasca regiunea. In plus, trebuie sa urce in permanenta, sau, altfel spus, altitudinea regiunii curente sa fie strict mai mica decat altitudinea regiunii urmatoare de pe traseu.
h2. Cerinta
...
Sa se determine cel mai lung traseu pe care il poate face alpinistul.
h2. Restrictii
h2. Date de Intrare
...
Pe prima linie a fisierului de intrare $alpin.in$ se va afla numarul $N$, dimensiunea regiunii. Urmatoarele $N$ linii contin cate $N$ numere naturale pozitive separate prin exact un spatiu, descriind codificarea matriceala a regiunii.
h2. Date de intrare
h2. Date de Iesire
...
Pe prima linie a sa, fisierul de iesire $alpin.out$ va contine $LMAX$, lungimea maxima a traseului parcurs. Urmeaza $LMAX$ linii, descriind traseul urmat prin casutele sale, in ordine, de la prima la ultima, inclusiv.
h2. Date de iesire
h2. Restrictii
...
* $1 ≤ N ≤ 1024$
* Altitudinea maxima nu depaseste $16.384$
* Daca exista mai multe solutii de lungime maxima, se va afisa oricare dintre ele
* Daca determinati corect doar lungimea maxima, veti primi $50%$ din punctajul pe testul respectiv
h2. Exemplu
| alpin.in | alpin.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. alpin.in |_. alpin.out |
| 6
29 10 8 9 8 10
22 11 7 3 7 20
17 15 3 14 45 30
19 5 2 41 19 17
23 8 90 39 20 18
27 30 32 35 70 19
| 16
4 3
3 3
2 3
1 3
1 2
2 2
3 2
3 1
4 1
5 1
6 1
6 2
6 3
6 4
5 4
4 4 |
== include(page="template/taskfooter" task_id="alpin") ==
==Include(page="template/taskfooter" task_id="alpin")==
