Diferente pentru problema/invsort intre reviziile #2 si #5

Diferente intre titluri:

invsort
Invsort

Diferente intre continut:

== include(page="template/taskheader" task_id="invsort") ==
==Include(page="template/taskheader" task_id="invsort")==
Poveste ...
Se da un sir de $N$ numere naturale, care trebuie ordonat crescator. Singura operatie permisa este sa considerati elementele de pe pozitiile $i, i+1, ..., j$ (pentru $i$ si $j$ arbitrare, $i<j$), si sa inversati ordinea acestor elemente (adica elementul de pe pozitia $i$ ajunge pe pozitia $j$, $i+1$ ajunge pe pozitia $j-1$, ..., $j$ ajunge pe pozitia $i$). Costul unei astfel de operatii este numarul de elemente din subsirul inversat, si anume $j-i+1$.
h2. Cerinta
...
Scrieti un program care sa determine o secventa de operatii care ordoneaza crescator sirul dat si are un cost total cat mai mic (dar nu obligatoriu minim).
h2. Restrictii
h2. Date de Intrare
 
Fisierul de intrare $invsort.in$ contine pe prima linie numarul $N$, si apoi $N$ linii cu elementele sirului dat (nu neaparat distincte).
 
h2. Date de Iesire
...
Fisierul de iesire $invsort.out$ va contine pe fiecare linie descrierea unei operatii. O operatie este descrisa prin numerele $i$ si $j$, separate printr-un spatiu. Aceste numere satisfac $1 &le; i < j &le; N$.
h2. Date de intrare
h2. Restrictii
...
* $2 &le; N &le; 32000$
* valorile sirului care trebuie ordonat sunt intre $0$ si $31999$
h2. Date de iesire
h2. Punctaj
...
* daca sirul de operatii (executate in ordinea din fisierul de iesire) nu ordoneaza intrarea, primiti $0$ puncte
* in cazul in care costul total este cel mult $4000000$ (patru milioane) primiti punctaj maxim
* in cazul in care costul total este cel mult $40000000$ (patruzeci de milioane) primiti $40%$ din punctajul pe test
* in $50%$ din teste sirul de intrare contine numai elemente de $0$ si $1$
* pentru toate testele folosite la corectare, $N=32000$
h2. Exemplu
| invsort.in | invsort.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. invsort.in |_. invsort.out |
| 5
1
0
1
1
0 | 3 5
1 3 |
 
h3. Explicatie
 
* prima operatie are efectul: $1 0 [1 1 0] -> 1 0 0 1 1$
* a doua operatie are efectul: $[1 0 0] 1 1 ->  0 0 1 1 1$
* costul total este $3 + 3 = 6$
== include(page="template/taskfooter" task_id="invsort") ==
==Include(page="template/taskfooter" task_id="invsort")==
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2286