Goro has 4 arms. Goro is very strong. You don't mess with Goro. Goro needs to sort an array of
Goro wants to sort the array as quickly as possible. How many hits will it take Goro to sort the given array, on average, if he acts intelligently when choosing which elements of the array to hold down before each hit of the table? Goro has an infinite number of fingers on the two hands he uses to hold down the array.
More precisely, before each hit, Goro may choose any subset of the elements of the array to freeze in place. He may choose differently depending on the outcomes of previous hits. Each hit permutes the unfrozen elements uniformly at random. Each permutation is equally likely.
Input Specification
The first line of the input gives the number of test cases,
Output Specification
For each test case, output one line containing Case #x: y
, where
Limits
The second line of each test case will contain a permutation of the
Memory limit: 1GB.
Small dataset
Time limit: 30 seconds.
Large dataset
Time limit: 60 seconds.
Sample Input
3
2
2 1
3
1 3 2
4
2 1 4 3
Sample Output
Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000
Explanation
In test case #3, one possible strategy is to hold down the two leftmost elements first. Elements
Note
This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >60.000s
regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.
Comments