Fişierul intrare/ieşire:inversiuni1.in, inversiuni1.outSursăLot II Juniori 2016
AutorDan PracsiuAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Inversiuni1 (Lot Juniori)

Ludwig are o permutare p=(p1,p2,...,pN) a mulţimii {1,2,..,N} şi o masă pe care putea aşeza numerele din permutare. Ludwig ia primul număr din permutare, adică p1, şi îl aşează pe masă. Al doilea număr, p2, îl pune fie în stânga lui p1, fie în dreapta lui p1. La fiecare pas, dacă s-au aşezat pe masă deja numerele p1,p2,...,pi, atunci numărul pi+1 este pus fie în stânga numerelor deja aşezate, fie în dreapta lor.

Cerinţă

Ajutaţi-l pe Ludwig să determine o modalitate de aşezare a întregii permutări pe masă astfel încât în final să se obţină o nouă permutare care are un număr minim de inversiuni.

Date de intrare

Fişierul inversiuni1.in conţine pe prima linie numărul natural N, iar pe linia a doua, separate prin câte un spaţiu, numerele p1,p2,...,pN.

Date de ieşire

Fişierul inversiuni1.out conţine un singur număr natural reprezentând numărul minim de inversiuni care se pot obţine.

Restricţii

  • 1 ≤ N ≤ 200 000
  • O inversiune în permutare este o pereche de indici (i,j) cu i<j şi pi>pj. De exemplu, permutarea p=(3,2,1,4) are ca inversiune perechea de indici (1,3) pentru că p1>p3; o altă inversiune este perechea de indici (2,3) pentru că p2>p3.

Exemplu

inversiuni1.ininversiuni1.outExplicaţii
4
2 1 3 4
0
Se aşează elementele pe masă astfel:
2
1 2 (1 este aşezat la stânga)
1 2 3 (3 este aşezat la dreapta)
1 2 3 4 (4 este aşezat la dreapta)
Se obţine permutarea identică, adică zero inversiuni.
4
2 1 4 3
1
Se aşează elementele pe masă astfel:
2
1 2 (1 este aşezat la stânga)
1 2 4 (4 este aşezat la dreapta)
1 2 4 3 (3 este aşezat la dreapta)
Se obţine o permutare care are o inversiune.
Trebuie sa te autentifici pentru a trimite solutii. Click aici