Editing 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 &les; n &les; 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).