Fişierul intrare/ieşire:	drum2.in, drum2.out	Sursă	ONI 2008, clasele 11-12
Autor	Carmen Minca	Adăugată de	Sima Cotizo •sima_cotizo
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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:

1. a<x;
2. a=x si b<y;
3. 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≤k≤n, 1≤i≤k, 1≤j≤k. Numarul punctelor din multimea M este m=1+4+9+...+n². 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₁∈ M i se asociaza valoarea c₁, celui de-al doilea punct P₂∈ M i se asociaza valoarea c₂,..., celui de-al m-lea punct P_m∈ M i se asociaza valoarea c_m, iar P₁<P₂<...<P_m.

Pornind de la punctul P₁ 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 ≤ 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₁,A₂,A₃,...,A_n precede lexicografic drumul B₁,B₂,B₃,...,B_n daca exista un indice j (1≤j≤n) astfel incat A_i=B_i (1≤i<j) si A_j<B_j.

Scrieti un program care sa citeasca numarul natural nenul n si cele m numere naturale nenule c₁, c₂,...,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.

Date de intrare

Fisierul de intrare drum2.in contine pe prima linie un numar natural nenul n. A doua linie contine m numere naturale nenule c₁,c₂,...,c_m, separate prin cate un spatiu, reprezentand valorile asociate punctelor din multimea ordonata M.

Date de iesire

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.

Restrictii

• 1 ≤ n ≤ 30;
• 1 ≤ c_i < 100, 1 ≤ i ≤ m;
• Punctele de coordonate (n,i,j) nu au succesori (1≤i≤n, 1≤j≤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.

Exemplu

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₁,P₄,P₁₃) si (P₁,P₅,P₁₄). 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.

Cum se trimit solutii?