Fişierul intrare/ieşire:alpin.in, alpin.outSursăLista lui Francu
AutorCristian CadarAdăugată de
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

Cerinta

Sa se determine cel mai lung traseu pe care il poate face alpinistul.

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.

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.

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

Exemplu

alpin.inalpin.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content