Ezzat and Two Subsequences
-
For Solution
Click Here!
Ezzat has an array of nn integers (maybe negative). He wants to split it into two non-empty subsequences aa and bb, such that every element from the array belongs to exactly one subsequence, and the value of f(a)+f(b)f(a)+f(b) is the maximum possible value, where f(x)f(x) is the average of the subsequence xx.
A sequence xx is a subsequence of a sequence yy if xx can be obtained from yy by deletion of several (possibly, zero or all) elements.
The average of a subsequence is the sum of the numbers of this subsequence divided by the size of the subsequence.
For example, the average of [1,5,6][1,5,6] is (1+5+6)/3=12/3=4(1+5+6)/3=12/3=4, so f([1,5,6])=4f([1,5,6])=4.
The first line contains a single integer tt (1≤t≤1031≤t≤103)— the number of test cases. Each test case consists of two lines.
The first line contains a single integer nn (2≤n≤1052≤n≤105).
The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109).
It is guaranteed that the sum of nn over all test cases does not exceed 3⋅1053⋅105.
For each test case, print a single value — the maximum value that Ezzat can achieve.
Your answer is considered correct if its absolute or relative error does not exceed 10−610−6.
Formally, let your answer be aa, and the jury’s answer be bb. Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6|a−b|max(1,|b|)≤10−6.
input
4 3 3 1 2 3 -7 -6 -6 3 2 2 2 4 17 3 5 -3
output
4.500000000 -12.500000000 4.000000000 18.666666667
In the first test case, the array is [3,1,2][3,1,2]. These are all the possible ways to split this array:
- a=[3]a=[3], b=[1,2]b=[1,2], so the value of f(a)+f(b)=3+1.5=4.5f(a)+f(b)=3+1.5=4.5.
- a=[3,1]a=[3,1], b=[2]b=[2], so the value of f(a)+f(b)=2+2=4f(a)+f(b)=2+2=4.
- a=[3,2]a=[3,2], b=[1]b=[1], so the value of f(a)+f(b)=2.5+1=3.5f(a)+f(b)=2.5+1=3.5.
Therefore, the maximum possible value 4.54.5.In the second test case, the array is [−7,−6,−6][−7,−6,−6]. These are all the possible ways to split this array:
- a=[−7]a=[−7], b=[−6,−6]b=[−6,−6], so the value of f(a)+f(b)=(−7)+(−6)=−13f(a)+f(b)=(−7)+(−6)=−13.
- a=[−7,−6]a=[−7,−6], b=[−6]b=[−6], so the value of f(a)+f(b)=(−6.5)+(−6)=−12.5f(a)+f(b)=(−6.5)+(−6)=−12.5.
Therefore, the maximum possible value −12.5−12.5.
-
For Solution
Click Here!
