Fişierul intrare/ieşire:sport.in, sport.outSursăLot Juniori 2008 - Baraj 5
AutorConstantin GalatanAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sport

La ora de sport, cei N elevi din clasa s-au aliniat pe un singur rand in fata profesorului. Nu au incercat sa se ordoneze dupa inaltime, deoarece stiau ca profesorul are propria metoda de ordonare, pe care o aplica la inceputul fiecarei ore. Profesorul alege un elev, pe care-l trimite la unul dintre cele doua capete ale randului. Procedeul se repeta pana cand sirul de elevi este ordonat crescator dupa inaltime. Copiii s-au gandit sa-l ajute pe profesor sa-si perfectioneze metoda, astfel incat numarul de elevi care vor fi mutati prin acest procedeu la un capat sau la celalalt al sirului sa fie minim.

Cerinta

Cunoscand numarul de elevi, inaltimile si pozitiile lor initiale in sir, determinati numarul minim de mutari pe care profesorul de sport trebuie sa le aplice, pentru a ordona sirul de elevi, crescator dupa inaltime. 

Date de intrare

Fisierul de intrare sport.in contine pe prima linie numarul natural N reprezentand numarul de copii. Pe linia a doua, se gasesc N numere naturale distincte: A1, A2, ... , AN separate prin cate un singur spatiu. Al i-lea numar de pe linie reprezinta inaltimea copilului care se afla pe pozitia i inainte de orice operatie de mutare.

Date de iesire

In fisierul de iesire sport.out se va scrie pe prima linie un numar natural M, reprezentand numarul minim de mutari pe care profesorul le poate face pentru a sorta sirul de elevi, crescator dupa inaltime.

Restrictii

  • 1 ≤ N ≤ 1.000
  • 1 ≤ Ai ≤ 10.000

Exemplu

sport.insport.out
4
2 1 3 5
1
3
3 2 1
2
5
3 7 2 6 9
3

Explicatie

  1. Profesorul muta elevul de inaltime 1 la capatul din stanga: 1 2 3 5
  2. Profesorul are la dispozitie mai multe variante cu minimum 2 mutari. Prezentam una dintre acestea:
    • Muta elevul de inaltime 1 la capatul din stanga: 1 3 2
    • Muta elevul de inaltime 3 la capatul din dreapta: 1 2 3
  3. Minimum 3 mutari. Una dintre variante este:
    • Muta elevul de inaltime 7 la capatul din dreapta: 3 2 6 9 7
    • Muta elevul de inaltime 2 la capatul din stanga: 2 3 6 9 7
    • Muta elevul de inaltime 9 la capatul din dreapta: 2 3 6 7 9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content