시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 28 15 12 48.000%

문제

여기, 특이한 방법으로 정렬을 하려고 하는 사람이 있다.

그리고 그의 이름은 존 시나!!!!

CENA.png

알고리즘 전문이 아닌 존 시나는 자신만의 방법으로 수를 정렬하려고 한다. 존 시나가 정렬할 배열에는 1부터 N까지의 자연수가 하나씩 들어있다. 우선 존 시나는 배열 안에서 몇 개의 원소를 골라 "You can't see me"라고 발언한다. 그 후 선택한 원소에 동시에 파이브 너클 셔플을 날린다. 그러면 선택한 원소들이 큰 대미지를 입으며 순서가 무작위로 섞이게 된다.

존 시나는 섞을 원소를 선택할 때 최적의 전략을 사용하고자 한다. 즉, 정렬하는 데 필요한 파이브 너클 셔플 횟수의 기대값을 최소화하려고 한다. (동시에 사용하는 파이브 너클 셔플은 하나로 친다.) 그 기대값은 얼마일까?

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다. 첫 줄에는 배열의 길이 N이 주어진다. 두 번째 줄에는 배열의 원소가 차례대로 주어진다.

1 ≤ T ≤ 100이고, 1 ≤ N ≤ 1000이다. 배열에는 1부터 N까지의 자연수가 하나씩 있다.

출력

각 줄에 테스트케이스 번호 x와 최소 기대값 y를 Case #x: y의 형태로 출력한다. y는 반올림하여 소수점 아래 6자리까지 출력한다.

예제 입력

3
2
2 1
3
1 3 2
4
2 1 4 3

예제 출력

Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000

힌트

케이스 #1: 존 시나는 두 원소를 모두 선택하여 파이브 너클 셔플을 날린다. 1/2의 확률로 배열이 정렬되고, 1/2의 확률로 그대로 있으므로 기대값은 2가 된다.

케이스 #2: 존 시나는 3과 2를 선택하여 파이브 너클 셔플을 날린다. #1과 마찬가지로 기대값은 2가 된다.

케이스 #3: 존 시나는 2와 1을 선택하여 파이브 너클 셔플을 날린다. #1과 마찬가지로 이때까지의 기대값은 2가 된다. 그 후 4와 3을 선택하여 파이브 너클 셔플을 날리면 총 기대값은 4가 된다.