Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.


Limits 1s, 512 MB

Let me tell you a story of a dangerous prison. There were N prisoners in that prison. It is guaranteed that N is odd. Now each prisoner had a bounty bi set on his head. The warden of the prison was a very bad guy. He along with some of his friends (The Mafia Lords) had an idea of playing a game with the lives of the prisoners! The Game was simple; each day randomly two prisoners will be selected (who are alive!) and they will have to fight each other. They must fight until one dies and the sad part is the winning prisoner is also killed by the prison guards as the prison lords don’t want to see the same person fighting another day! The Game ends when there will be exactly one prisoner who will be left alive. The warden of the prison will set him free and will also give him money equivalent to his bounty as a reward. Now suppose you are one of the prisoners (Ahh sad for you) who wants to know what will be the expected bounty of the prisoner who will be alive at last i.e. when the game ends.


Input starts with an integer T (0 ≤ T ≤ 100), denoting the number of test cases.

Each case starts with an integer N (1 ≤ N ≤ 105) which denotes the number of prisoners initially present in the prison. It is guaranteed that n will always be odd. In the next line there will be N space separated integers, where the ith integer is bi (0 ≤ bi ≤ 103) denoting the bounty of the ith prisoner.


For each case, print the expected bounty of the alive prisoner (when the game ends). Errors less than 10-6 will be ignored.


1 2 3
200 933 100 6 20 103 310 1 143

For the first test case in sample, there is only one prisoner. So the expected value will be 1 × 10 = 10.

For the second test case in sample, there are three prisoners. On the first game any pair can die out of three possible pairs (1-2), (1-3), (2-3). So the expected value will be (13) × 1 + (13) × 2 + (13) × 3 = 2.



95% Solution Ratio

daryanZEarliest, Aug '15

E.NahidFastest, 0.1s

Tanim018Lightest, 0 B

maddogShortest, 88B


Login to submit