Untitled

 avatar
unknown
python
a year ago
904 B
2
Indexable
def count_inversions(arr):
    n = len(arr)
    inversions = 0

    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                inversions += 1

    return inversions


def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


def main():
    n = int(input())
    permutation = list(map(int, input().split()))

    total_inversions = 0
    count_permutation = 0

    for i in range(n):
        for j in range(i + 1, n):
            new_permutation = permutation.copy()
            new_permutation[i], new_permutation[j] = new_permutation[j], new_permutation[i]
            count_permutation += 1
            total_inversions += count_inversions(new_permutation)

    t = gcd(total_inversions, count_permutation)
    print(f'{total_inversions//t}/{count_permutation//t}')


if __name__ == "__main__":
    main()
Leave a Comment