Untitled
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