JDCC '15 Contest 1 P3 - Test Candy

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

After a slew of poor test results, Ms. Dyke has decided to give the students who pass her tests candy as incentive for everyone to work harder. Unfortunately, candy is apparently really expensive and the department has little money. To work around this, she has decided to adjust her student's marks (by adding or subtracting some constant value from each mark) in order to minimize the amount of candy she needs to give out. However, she can't have the class average be less than 50\% or she'll get in trouble! Ms. Dyke has picked you to figure out what is the minimum number of candy she can give out, don't let her down!

Input Specification

The first line of the input provides the number of test cases, T (1 \le T \le 100). T test cases follow. The first line of each test case provides the number of students in her class, N (2 \le N \le 1000). The next N lines each contain a real number M (0 \le M \le 100), the mark of one of her students. Marks are given in increasing order and no two marks are the same.

Output Specification

A single integer denoting the minimum amount of candy she needs to give out.

Sample Input


Sample Output


Explanation for Sample

In the first case, the average is 70\% so she can lower everyone's mark by 20\%, meaning two people passed the test. In the second case, she has to raise the mark by at least 49.85\%, so the two highest marks must be above average.


There are no comments at the moment.