Sortarea prin oglindiri (o problema)

[•baTTLe4u_15]

Am gasit urmatoarea problema:

Se citeşte de la tastatură un şir de n numere naturale cuprinse între 1 si 60000. Se cere ordonarea crescătoare a acestui şir folosind următoarea operaţie: se fixează un element al şirului şi apoi se oglindesc secvenţele din stânga şi din dreapta lui. De exemplu, dacă în şirul (6 5 7 8 9 4 6 5) se fixează elementul de pe poziţia 4 se va obţine şirul (7 5 6 8 5 6 4 9) adică se oglindeşte şirul (6 5 7) şi şirul (9 4 6 5), şiruri aflate în stânga şi respectiv în dreapta elementului de pe poziţia 4. Se pot fixa şi elementele fictive de pe poziţiile 0 si n+1.
Să se afişeze toate poziţiile care s-au fixat pentru a ajunge la soluţie. Numărul acestor poziţii fixate trebuie să nu fie mai mare decât 3n.
   Exemplu. Pentru şirul (4,20,5,50,25) poziţiile fixate sunt (4,5,5,6,4, 5,5,6,5,6).

Asta am lucrat eu pana acum
http://pastebin.com/YKSawJze 

Trebuie sa-mi mai dau seama in ce mod se alege pozitia pentru oglindire 

[•cristiavra]

pot sa te intreb unde ai gasit problema?

[•baTTLe4u_15]

Mi-a dat doamna profesoara sa lucrez, dar nici dansa nu stie s-o rezolve...

[•mihaipopa12]

Cred ca problema este si pe infoarena :
http://www.infoarena.ro/problema/order2

[•baTTLe4u_15]

Interesant 
Nu stiam , n-am mai intalnit-o. Si totusi, are 0.1 sec limita de timp, merge cat de cat oglindirea facuta de mine ? Sau sunt complet paralel cu problema...?

[•mihaipopa12]

Solutia problemei e O(n^2). Functia de oglindire e buna dar trebuie sa vezi cum folosesti oglindirile incat sa sortezi sirul. Nu e corecta abordarea ta cu citirea x-ului la care sa oglindesti 

[•baTTLe4u_15]

Stiu, am pus chestia cu citirea pozitiei pentru a testa mai rapid exemplele date de mine si sincer sa fiu nici exemplele nu le pot duce pana la capat.. din momemnt ce nu le-am inteles matematic nici n-am ce implementa. (as crede ca trebuie un if ceva.. sa caut o secventa crescatoare/descrescatoare sau nu stiu.... inca n-am gasit o idee care sa mearga pe caz general).

[•mihaipopa12]

http://probleme.francu.com/arhiva/R0028/enunt.html

De aici e luata problema, vad ca e si rezolvarea acolo.
Bafta!

[•baTTLe4u_15]

Multumesc pentru sursa. O sa studiez cu atentie sa vad care-i faza cu pozitiile acelea pe acolo.