SP7566 IITD5 - Expected Cycle Sums

We are given a sequence S of N distinct integers. Denote by S\[i\] as ith element of S. Hardik picks up a random permutation of S , breaks it into product of disjoint cycles & looks at cycle containing S\[i\].He notes down the sum of all element of this cycle. Call the expected value of this sum as cycleSum\[i\]. Your task is to find the minimum value amongst all cycleSums. Assume all permutations of these N numbers are equally likely. **Input Format :** First line contains an integer T which denotes the number of test cases. Then follow description of T test scenarios. Each test scenario takes 2 lines. First line contains a single integer N, the size of S. Then follows second line containing N elements of S. **Output Format :** Print answer for each test case , rounded to exactly one decimal place , in one line each. **Sample Input :** 2 1 1 2 1 2 **Sample Output:** 1.0 2.0 **Note:** Notion of cycles for any sequence is defined by using index in the sequence (1-N). **Explaination for sample output** : In first case only possible permutation is (1) So answer is trivially 1.0 In second case possible permutations are (1)(2) & (12). As both of these are equally likely, cycleSum\[1\] = 1/2 \* 1 + 1/2 \* (1+2) = 2.0 And cycleSum\[2\] = 1/2 \* 2 + 1/2 \* (1+2) = 2.5. Smaller of these is 2.0 , hence the answer. **Constraints :** 1

N/A

N/A