Group Them All!!!
All submissions for this problem are available.
“United we stand, divided we fall” – says the professor. There are N students in the college and there is large disunity among students.The size of any group is the number of students in it. The professor wants to group them into a large single group(of size N). He knows that each student has its own skill level given by the array skill[ ] and that every student is a group of its own(of size 1).
The professor carries out many statistical and mathemaitcal research. He comes to the conclusion that to successfully bind the team, a group can be formed by a merging atleast p smaller groups. Also the skill set of the group formed by merging x(x &ge p) groups with skill sets s0,s1,s2,… sx-1 is the average of them; i.e. (s0+s1+s2+… +sx-1) /x. Given the skills of each student, you need to find out the maximum possible skill set of the final group.
The first line of input consists of the number of test cases T. The description of T test cases follows. Each test case begins with a line with two numbers N and p (all separated by single space). The next line has N integers which tell the skill level of each student. All numbers are space separated.
For each test case output the maximum possible skill set of the final group formed.
Note that the answers would be accepted only if it has an absolute or relative error of less than 10-6
2 ≤ p ≤ N
0 &le |skill[i]| &103 //Yes. Some students are too naughty and have negative skills.
Input: 3 3 2 -3 4 5 4 2 1 1 1 1 3 3 -3 4 5 Output: 2.75 1.00 2.00
Example case 1.Firstly group first two students, the new group formed as skill of (-3+4)/2= 0.5. Now group the newly group formed (of skill 0.5) with the last student. The resulting skill is (0.5+5)/2=2.75.
Note that there are three other ways of forming groups. These are shown below. But these do not give maximum value.
- (-3+5)/2 =1 ; (1+4)/2 =2.5
- (4+5)/2 =4.5; (4.5+(-3))/2=0.75
- (-3+4+5) /3 =2.0
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.