Mean Maximization

 JJ loves playing with averages. He has an array 

A$A$ of length N$N$. He wants to divide the array A$A$ into two non-empty subsets P$P$ and Q$Q$ such that the value of mean(P)+mean(Q)$mean(P)+mean(Q)$ is as large as possible. (Note that each Ai$A_i$ must belong to either subset P$P$ or subset Q$Q$).

Help him find this maximum value of mean(P)+mean(Q)$mean(P)+mean(Q)$.

As a reminder, the mean of a subset X$X$ of size M$M$ is defined as: mean(X)=∑Mi=1XiM$mean(X)={\displaystyle \frac{\sum _{i=1}^M{X}_i}{M}}$.

For example, mean([3,1,4,5])=3+1+4+54=3.25$mean([3,1,4,5])=\frac{3+1+4+5}{4}=3.25$.

Input Format

• The first line contains T$T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ - the size of the array A$A$.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the array A$A$.

Output Format

Output the largest value of mean(P)+mean(Q)$mean(P)+mean(Q)$.

Your answer is considered correct if its absolute or relative error does not exceed 10−6${10}^{-6}$.

Formally, let your answer be a$a$, and the jury's answer be b$b$. Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6$\frac{|a-b|}{max(1,|b|)}\le {10}^{-6}$.

Constraints

• 1≤T≤100$1\le T\le 100$
• 2≤N≤1000$2\le N\le 1000$
• 1≤Ai≤106$1\le A_i\le {10}^6$

Sample Input 1 

2
2
4 5
5
2 2 2 2 2

Sample Output 1 

9.000000
4.000000

Explanation

Test case-1: We can divide the two elements into two non-empty subsets P$P$ and Q$Q$ as follows: P=[4]$P=[4]$, Q=[5]$Q=[5]$.

Therefore, mean(P)+mean(Q)=9$mean(P)+mean(Q)=9$.

Test case-2: In whatever way we divide the elements of the array, mean of both the subsets will always be 2$2$.

Therefore, mean(P)+mean(Q)=4$mean(P)+mean(Q)=4$.

• Tweet
• Share
• Share
• Share
• Share

Related Post