Alpin

alpin

==Include(page="template/taskheader" task_id="alpin")==

== include(page="template/taskheader" task_id="alpin") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| alpin.in | alpin.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="alpin") ==

==Include(page="template/raw")==
 
alpin
 
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. 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 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. Restrictii
 
o 1 <= N <= 1024
o Altitudinea maxima nu depaseste 16 384
o Daca exista mai multe solutii de lungime maxima, se va afisa oricare dintre ele
o Daca determinati corect doar lungimea maxima, veti primi 50% din punctajul pe testul respectiv
 
h2. Exemplu
 
 
 
alpin.in alpin.out
6 16
 
29 10 8 9 8 10 4 3
 
22 11 7 3 7 20 3 3
 
17 15 3 14 45 30 2 3
 
19 5 2 41 19 17 1 3
 
23 8 90 39 20 18 1 2
 
27 30 32 35 70 19 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")==