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 numar_inversiuni_permutare(n, permutare):

   numar_inversiuni = 0

   for i in range(n - 1):
       for j in range(i + 1, n):
           if permutare[i] > permutare[j]:
               numar_inversiuni += 1

   return numar_inversiuni

def main():

   # Citirea datelor de intrare de la tastatură
   n = int(input("Introduceti numarul n: "))
   permutare = list(map(int, input(f"Introduceti permutarea de lungime {n}, separate prin spatiu: ").split()))

   # Calcularea numărului de inversiuni
   rezultat = numar_inversiuni_permutare(n, permutare)

   # Afișarea rezultatului
   print(f"Numarul de inversiuni in permutare este: {rezultat}")

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

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