Diferente pentru problema/lsort intre reviziile #1 si #10

Diferente intre titluri:

lsort
Lsort

Diferente intre continut:

== include(page="template/taskheader" task_id="lsort") ==
Poveste si cerinta...
Se considera o lista simplu inlantuita ({$L1$}) ce contine numerele intregi de la $1$ la $N$ (intr-o ordine oarecare). Se doreste construirea unei alte liste simplu inlantuite ({$L2$}) care sa contina numerele din lista $L1$ in ordine crescatoare. Pentru a obtine lista $L2$, se vor sterge elemente din $L1$ si se vor adauga in $L2$, conform procedeului descris in continuare: initial lista $L2$ e vida. La primul pas putem sterge orice element din $L1$ si acesta se adauga in $L2$. Apoi, in urmatorii $N-1$ pasi, se poate sterge orice element din $L1$, dar acesta poate fi adaugat numai la inceputul sau la sfarsitul lui $L2$. La final, $L1$ nu va contine nici un element, iar $L2$ trebuie sa contina numerele de la $1$ la $N$ in ordine crescatoare. Intrucat exista mai multe posibilitati de a construi $L2$, vom defini in continuare costul constructiei lui $L2$ si vom dori sa determinam o posibilitate de constructie a lui $L2$ care sa aiba costul minim.
 
Algoritmul de constructie a lui $L2$ consta din $N$ pasi, la fiecare pas stergandu-se un element din $L1$ si adaugand acest element in $L2$ (conform restrictiilor precizate). La pasul $i$ ({$1 ≤ i ≤ N$}), lista $L1$ contine $N-i+1$ elemente si lista $L2$ contine $i-1$ elemente. Daca se muta elementul de pe pozitia $k$ din $L1$ in $L2$ la pasul $i$ ({$1 ≤ k ≤ N-i+1$}), costul acestei mutari este egal cu ${*k*i*}$. Dupa mutarea elementului, lista $L1$ va avea cu un element mai putin (toate elementele de pe pozitii mai mari decat $k$ vor ajunge cu o pozitie mai in fata) si lista $L2$ va avea cu un element mai mult. Costul total al constructiei lui $L2$ este egal cu suma costurilor mutarilor efectuate la fiecare dintre cei $N$ pasi.
h2. Date de intrare
...
Pe prima linie a fisierului $lsort.in$ se afla numarul $N$, reprezentand numarul de elemente din $L1$. Urmatoarea linie contine numerele intregi de la $1$ la $N$, separate prin cel putin un spatiu, in ordinea in care se afla acestea pozitionate in lista $L1$ (primul numar se afla pe pozitia $1$ in $L1$, al doilea numar pe pozitia $2$ s.a.m.d.).
h2. Date de iesire
...
Pe prima linie a fisierului de iesire $lsort.out$ se va afisa costul minim de constructie a lui $L2$. Pe urmatoarea linie se va afisa modul de constructie al acesteia. Pe aceasta linie se va afisa ordinea in care sunt mutate elementele din lista $L1$ in lista $L2$. Primul numar afisat va reprezenta numarul mutat din $L1$ in $L2$ la primul pas; al doilea numar va reprezenta numarul mutat la pasul $2$ s.a.m.d. Numerele afisate trebuie separate prin cel putin un spatiu. In cazul in care exista mai multe posibilitati de constructie a listei $L2$ avand costul minim, se poate afisa oricare dintre ele.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1000$
h2. Exemplu
h2. Exemple
table(example). |_. lsort.in |_. lsort.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
|4
4 1 3 2
|15
3 4 2 1
|
|7
6 3 5 4 1 7 2
|43
6 5 4 3 2 1 7
|
 
h3. Explicatie pentru primul exemplu
 
* La pasul $1$, $L1$ = $[4, 1, 3, 2]$ si $L2$ = $[]$. Se sterge din $L1$ elementul $3$ (care se afla pe pozitia 3) si se introduce in $L2$. Costul acestei mutari este $3*1=3$.
* La pasul $2$, $L1$ = $[4, 1, 2]$ si $L2$ = $[ 3 ]$. Se sterge din $L1$ elementul $4$ (care se afla pe pozitia $1$) si se introduce in $L2$ (este evident ca acest element trebuie adaugat la sfarsitul listei $L2$ si nu la inceputul ei; in caz contrar, lista $L2$ nu ar mai fi sortata). Costul acestei mutari este $1*2=2$.
* La pasul $3$, $L1$ = $[1, 2]$ si $L2$ = $[3, 4]$. Se sterge din $L1$ elementul $2$ (care se afla pe pozitia $2$) si se introduce in $L2$ (din nou, pozitia unde trebuie adaugat elementul este evidenta : la inceputul listei L2). Costul acestei mutari este $2*3=6$.
* La pasul $4$, $L1$ = $[ 1 ]$ si $L2$ = $[2, 3, 4]$. Se sterge din $L1$ elementul $1$ (care se afla pe pozitia $1$) si se introduce in $L2$. Costul acestei mutari este $1*4=4$.
Costul total al constructiei listei $L2$ este $3+2+6+4=15$.
 
== include(page="template/taskfooter" task_id="lsort") ==
h3. Explicatie
...
== include(page="template/taskfooter" task_id="lsort") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2151