Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sport.in, sport.out | Sursă | Lot Juniori 2008 - Baraj 5 |
| Autor | Constantin Galatan | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | sport.out |
|---|---|
| 4 2 1 3 5 | 1 |
| 3 3 2 1 | 2 |
| 5 3 7 2 6 9 | 3 |
Explicatie
- Profesorul muta elevul de inaltime 1 la capatul din stanga: 1 2 3 5
- 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
- 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
