Untitled
unknown
python
2 years ago
904 B
9
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()
Editor is loading...
Leave a Comment