Fişierul intrare/ieşire:drum2.in, drum2.outSursăONI 2008, clasele 11-12
AutorCarmen MincaAdăugată desima_cotizoSima Cotizo sima_cotizo
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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+...+n2. 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 P1M i se asociaza valoarea c1, celui de-al doilea punct P2M i se asociaza valoarea c2,..., celui de-al m-lea punct PmM i se asociaza valoarea cm, iar P1<P2<...<Pm.

Pornind de la punctul P1 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 A1,A2,A3,...,An precede lexicografic drumul B1,B2,B3,...,Bn daca exista un indice j (1≤j≤n) astfel incat Ai=Bi (1≤i<j) si Aj<Bj.

Scrieti un program care sa citeasca numarul natural nenul n si cele m numere naturale nenule c1, c2,...,cm 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 c1,c2,...,cm, 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 ≤ ci < 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

drum2.indrum2.out
3
3 6 5 7 2 4 5 8 7 6 1 7 8 13
18
1 4 13

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: (P1,P4,P13) si (P1,P5,P14). 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content