시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 7 1 1 100.000%

문제

랜덤 소트는 크기가 N인 순열 P를 아래와 같은 알고리즘을 이용해서 정렬하는 방법이다.

function random_sort(permutation P) {
	swaps = 0;
	while (not sorted P) {
		(i, j) = random pair (1 <= i < j <= n)
		swap(P[i], P[j])
		swaps = swaps + 1;
	}
	return swaps;
}

순열 P가 주어졌을 때, random_sort 함수의 리턴값의 기대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 순열의 크기 N (2 ≤ N ≤ 10)이 주어진다.

둘째 줄에 순열이 주어진다.

출력

입력으로 주어진 순열 P를 random_sort 함수로 정렬할 때, 리턴값의 기대값을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1

2
2 1

예제 출력 1

1.0000000

예제 입력 2

3
2 1 3

예제 출력 2

5.0000000

예제 입력 3

4
2 3 4 1

예제 출력 3

27.5000000

예제 입력 4

6
2 5 1 3 4 6

예제 출력 4

781.0416667

출처