drum2

Drum2

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

Poveste si cerinta...

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.
 
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.
 
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~.
 
Scrieti un program care sa citeasca numarul natural nenul $n$ si cele $m$ numere naturale nenule {$c$}~1~, {$c$}~2~,...,{$c$}~m~  si  apoi sa determine si sa afiseze suma maxima $S$ care se poate obtine insumand toate valorile asociate punctelor de pe un drum construit in modul descris in enunt, precum si drumul pentru care se obtine suma maxima. Daca exista mai multe drumuri pentru care se obtine suma maxima, se va afisa primul drum din punct de vedere lexicografic.

h2. Date de intrare

Fisierul de intrare $drum2.in$ ...

Fisierul de intrare $drum2.in$ contine pe prima linie un numar natural nenul $n$. A doua linie contine $m$ numere naturale nenule {$c$}~1~,{$c$}~2~,...,{$c$}~m~, separate prin cate un spatiu, reprezentand valorile asociate punctelor din multimea ordonata $M$.

h2. Date de iesire

In fisierul de iesire $drum2.out$ ...

In fisierul de iesire $drum2.out$ va contine pe prima linie un numar natural reprezentand suma maxima $S$. A doua linie va contine un drum pentru care se obtine suma maxima $S$, scriindu-se numarul fiecarui punct aflat pe drum, in ordinea parcurgerii acestora, numerele separandu-se prin cate un singur spatiu.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 30$;
* {$1 &le; c$}~i~ {$< 100$}, $1 &le; i &le; m$;
* Punctele de coordonate $(n,i,j)$ nu au succesori $(1&le;i&le;n, 1&le;j&le;n)$
* Pentru suma maxima $S$ corecta se acorda 60% din punctaj; pentru un drum pentru care se obtine suma maxima $S$ se acorda 20% din punctaj, iar pentru primul drum din punct de vedere lexicografic pentru care se obtine suma maxima $S$ se acorda 40% din punctaj.

h2. Exemplu
table(example). |_. drum2.in |_. drum2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
3 6 5 7 2 4 5 8 7 6 1 7 8 13
| 18
1 4 13

|
h3. Explicatie

...

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