lsort

Lsort

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

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 următorii $N–1$ paşi, 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.

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 construcÅ£ie al lui $L2$ constă din $N$ paÅŸi, la fiecare pas stergandu-se un element din $L1$ ÅŸi adaugand acest element in $L2$ (conform restrictiilor precizate). La pasul $i$ ($1 ≤ i ≤ N$), lista $L1$ conÅ£ine $N–i+1$ elemente ÅŸi lista $L2$ conÅ£ine $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*}$. După mutarea elementului, lista $L1$ va avea cu un element mai puÅ£in (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$ paÅŸi.

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$ ÅŸ.a.m.d.).

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

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 $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$.

* 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") ==

2151