문제1241--Random Sort

1241: Random Sort

실행시간 제한: 7 Sec  메모리사용 제한: 128 MB
제출: 66  통과: 27
[제출] [채점기록] [묻고답하기]

문제 설명

You are given a int[] permutation containing a permutation of the first n positive integers (1 through n), and you want to sort them in ascending order. To do this, you will perform a series of swaps. For each swap, you consider all pairs (i, j) such that i < j and permutation[i] > permutation[j]. Among all those pairs, you choose one randomly and swap permutation[i]and permutation[j]. Each pair has the same probability of being chosen. Return the expected number of swaps needed to sort permutation in ascending order.

 

입력 설명

 

The first line contains the number of test cases T (T ≤ 200).

For each test case, space-separated two integers n - number of elements in permutation - and n integers as permutation given on the first line.

 

Constraints

- permutation will contain between 1 and 8 elements, inclusive.
- permutation will contain each integer between 1 and n, inclusive, exactly once, where n is the number of elements in permutation.

출력 설명

Output the answer of each test case on a separate line. You should round the result to sixth digits after the decimal point.

 

 

 

입력 예시 Copy

4
3 1 3 2
4 4 3 2 1
1 1
6 2 5 1 6 3 4

출력 예시 Copy

1.00000
4.06667
0.00000
5.66667

출처/분류