3206 - Nr Inversiuni

Enunt

Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].

Cerinta

Să se determine numărul inversiunilor permutării.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

Date de iesire

Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

Restrictii si precizari

• 1 ⩽ n ⩽ 100.000

Exemplul 1

Intrare

5

4 2 5 1 3

Iesire

Datele introduse corespund restrictiilor impuse

6

Exemplul 2

Intrare

5

-2 8 0 3

Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def este_permutare_valida(n, permutare):

   if n != len(permutare):
       return False

   elemente_unice = set(permutare)
   return len(elemente_unice) == n and all(1 <= elem <= n for elem in elemente_unice)

def numara_inversiuni(arr):

   if len(arr) <= 1:
       return arr, 0

   mijloc = len(arr) // 2
   stanga, inversiuni_stanga = numara_inversiuni(arr[:mijloc])
   dreapta, inversiuni_dreapta = numara_inversiuni(arr[mijloc:])

   concatenat, inversiuni_split = combina_si_numara(stanga, dreapta)

   inversiuni_totale = inversiuni_stanga + inversiuni_dreapta + inversiuni_split

   return concatenat, inversiuni_totale

def combina_si_numara(stanga, dreapta):

   concatenat = []
   inversiuni_split = 0
   i = j = 0

   while i < len(stanga) and j < len(dreapta):
       if stanga[i] <= dreapta[j]:
           concatenat.append(stanga[i])
           i += 1
       else:
           concatenat.append(dreapta[j])
           inversiuni_split += len(stanga) - i
           j += 1

   concatenat.extend(stanga[i:])
   concatenat.extend(dreapta[j:])

   return concatenat, inversiuni_split

if __name__ == "__main__":

   n = int(input("Introduceți numărul n: "))
   permutare = list(map(int, input("Introduceți permutarea: ").split()))

   if este_permutare_valida(n, permutare):
       _, inversiuni = numara_inversiuni(permutare)
       print("Numărul inversiunilor permutării:", inversiuni)
   else:
       print("Permutarea introdusă nu este validă.")

</syntaxhighlight>

Explicatie

Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).