Fişierul intrare/ieşire:invsort.in, invsort.outSursăONI 2004
AutorMihai PatrascuAdăugată de
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Invsort

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.

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

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

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 ≤ i < j ≤ N.

Restrictii

  • 2 ≤ N ≤ 32000
  • valorile sirului care trebuie ordonat sunt intre 0 si 31999

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

Exemplu

invsort.ininvsort.out
5
1
0
1
1
0
3 5
1 3

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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content