Fişierul intrare/ieşire:	lsort.in, lsort.out	Sursă	ONI 2005, clasele 11-12
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.025 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

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

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.

Restrictii

• 1 ≤ N ≤ 1000

Exemple

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 = ³. 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 = ¹ 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.

Cum se trimit solutii?