== include(page="template/taskheader" task_id="drum2") ==

Fie $P$, de coordonate carteziene $(a,b,c)$, si $Q$, de coordonate carteziene $(x,y,z)$, doua puncte distincte din spatiul tridimensional. Pe multimea punctelor din spatiu se defineste relatia de ordine `<` astfel: un punct $P$ este mai mic decat un punct $Q$ (adica {$P<Q$}) daca este satisfacuta una dintre relatiile:

Fie $P$, de coordonate carteziene $(a,b,c)$, si $Q$, de coordonate carteziene $(x,y,z)$, doua puncte distincte din spatiul tridimensional. Pe multimea punctelor din spatiu se defineste relatia de ordine $‘<’$ astfel: un punct $P$ este mai mic decat un punct $Q$ (adica {$P<Q$}) daca este satisfacuta una dintre relatiile:

# $a<x$;
# $a=x$ si $b<y$;
# $a=x, b=y$ si $c<z$.

Fie $n$ un numar natural nenul si $M$ multimea ordonata crescator, pe baza relatiei de ordine `<`, a tuturor punctelor din spatiu ale caror coordonate $(k,i,j)$ sunt numere naturale si satisfac conditiile: $1&le;k&le;n$, $1&le;i&le;k$, $1&le;j&le;k$.  Numarul punctelor din multimea $M$ este $m=1+4+9+...+n^2^$. Punctele din multimea ordonata $M$ se numeroteaza cu numerele distincte $1,2,...,m$ in ordinea in care apar in aceasta.

Fie $n$ un numar natural nenul si $M$ multimea ordonata crescator, pe baza relatiei de ordine $‘<’$, a tuturor punctelor din spatiu ale caror coordonate $(k,i,j)$ sunt numere naturale si satisfac conditiile: $1&le;k&le;n$, $1&le;i&le;k$, $1&le;j&le;k$.  Numarul punctelor din multimea $M$ este $m=1+4+9+...+n^2^$. Punctele din multimea ordonata $M$ se numeroteaza cu numerele distincte $1,2,...,m$ in ordinea in care apar in aceasta.

Fiecarui punct din multimea ordonata $M$ i se asociaza cate o valoare naturala nenula. Astfel, primului punct {$P$}{~1~}&isin; $M$ i se asociaza valoarea $c$~1~, celui de-al doilea punct  {$P$}{~2~}&isin; $M$ i se asociaza valoarea $c$~2~,..., celui de-al $m$-lea punct {$P$}{~m~}&isin; $M$ i se asociaza valoarea $c$~m~, iar $P$~1~$<P$~2~$<...<P$~m~.

Pornind de la punctul {$P$}~1~ de coordonate $(1,1,1)$, se contruiesc drumuri astfel incat succesorul unui punct de pe drum, de coordonate carteziene $(k,i,j)$, poate fi unul dintre cele $3$ puncte din $M$ ale caror coordonate sunt: $(k+1,i,j+1)$, $(k+1,i+1,j)$, $(k+1,i+1,j+1)$, pentru $1 &le; k < n$. De exemplu, daca $n>3$ succesorul punctului de coordonate $(3,1,2)$ poate fi oricare din punctele de coordonate: $(4,1,3)$, $(4,2,2)$, $(4,2,3)$. Daca $n=3$ atunci punctul de coordonate $(3,1,2)$ nu are succesor.

Pornind de la punctul {$P$}~1~ de coordonate $(1,1,1)$, se contruiesc drumuri astfel incat succesorul unui punct de pe drum, de coordonate carteziene $(k,i,j)$, poate fi unul dintre cele $3$ puncte din $M$ ale caror coordonate sunt: $(k+1,i,j+1)$, $(k+1,i+1,j)$, $(k+1,i+1,j+1)$, pentru $1&le;k<n$. De exemplu, daca $n>3$ succesorul punctului de coordonate $(3,1,2)$ poate fi oricare din punctele de coordonate: $(4,1,3)$, $(4,2,2)$, $(4,2,3)$. Daca $n=3$ atunci punctul de coordonate $(3,1,2)$ nu are succesor.

Drumul {$A$}~1~,{$A$}~2~,{$A$}~3~,...,{$A$}~n~ precede lexicografic drumul {$B$}~1~,{$B$}~2~,{$B$}~3~,...,{$B$}~n~ daca exista un indice $j$ $(1&le;j&le;n)$ astfel incat {$A$}~i~{$=B$}~i~ $(1&le;i<j)$ si {$A$}~j~{$<B$}~j~.

Sunt $14$ puncte in multimea $M$. Suma maxima care se poate obtine este $18$, valoare ce se va scrie pe prima linie a fisierului $drum.out$. Sunt $2$ drumuri pentru care se obtine suma maxima: {$(P$}~1~,{$P$}~4~,{$P$}~13~{$)$} si {$(P$}~1~,{$P$}~5~,{$P$}~14~{$)$}. Primul drum fiind cel mai mic (lexicografic) se vor scrie pe a doua linie a fisierului $drum.out$ numerele $1 4 13$, obtinandu-se punctajul maxim.
== include(page="template/taskfooter" task_id="drum2") ==

3082