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

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ă.")

Explicatie

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