Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-04-26 18:20:29.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ordonare.in, ordonare.outSursăConcurs de incalzire 2020
AutorBogdan PopAdăugată deBodo171Bogdan Pop Bodo171
Timp execuţie pe test0.5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ordonare

Petrică, plictisit de socializare şi arbori, a decis să-şi găsească un nou hobby: curăţenia. El a dat de o cameră destul de ciudată (extrem de lungă, dar foarte îngustă, atât de îngustă încât poate fi reprezentata ca axa Ox).El a găsit în cameră n obiecte, aflându-se la diverse coordonate pe axa Ox. Totuşi, unele din acestea se aflau la coordonate identice, fapt ce nu era tolerat de noua obsesie a lui Petrică. Astfel, el s-a hotărât să mute obiectele astfel încât toate să se afle la coordonate distincte. Ca să mute un obiect cu +1 sau -1 pe axa Ox, Petrică are nevoie de o secundă. El ar vrea să afle timpul minim (în secunde) pentru a ordona camera după criteriul său.

Date de intrare

Fişierul de intrare ordonare.in conţine pe prima linie n, numărul de obiecte, iar pe a doua linie n numere întregi x(i), reprezentând coordonatele obiectelor.

Date de ieşire

În fişierul de ieşire ordonare.out conţine un singur număr, timpul minim cerut de Petrică.

Restricţii

  • n ≤ 100.000 , -1.000.000.000 ≤ x(i) ≤ 1.000.000.000
  • Pentru 10 puncte, n ≤ 10 , -50 ≤ x(i) ≤ 50
  • Pentru alte 10 puncte, n ≤ 50 , -50 ≤ x(i) ≤ 50
  • Pentru alte 10 puncte n ≤ 100 , -50 ≤ x(i) ≤ 50
  • Pentru alte 20 de puncte n ≤ 1.000 , -500 ≤ x(i) ≤ 500
  • Pentru alte 30 de puncte n ≤ 1.000

Exemplu

ordonare.inordonare.out
5
1 2 2 3 4
2
2
-1 -2
0
3
1 4 4 3
1

Explicaţie

În primul exemplu, Petrică mută obiectul de la coordonata 1 la coordonata 0 şi unul din obiectele de la coordonata 2 la coordonata 1, luându-i în total 2 secunde.
În al doilea exemplu, deşi pare mai complicat pentru că numerele sunt negative, Petrică nu trebuie să facă nimic deoarece obiectele sunt deja la coordonate distincte.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?