GroupingNumbers
SRM 280 · 2005-12-28 · by dimkadimon
Problem Statement
Your are given a
Notes
- The return value must be within 1e-9 absolute or relative error of the actual result.
Constraints
- numbers will have between 1 and 9 elements inclusive.
- Each element in numbers will be between 1 and 1000 inclusive.
- n will be between 1 and the number of elements in numbers inclusive.
{1,2,99,100}
2
Returns: 0.0
The best split is (1,100) and (2,99). Both groups have an average of 50.5, so the difference is 0.
{3,3,3,3,3,3,3,3,3}
4
Returns: 0.0
When all the numbers are the same, the average of any group will be that number.
{2,3,5,7,11,13}
3
Returns: 0.33333333333333304
The best split is (2,5,13), (3,11) and (7). The first group has an average of 6.66..., and the other two groups both have averages of 7. The difference is 0.33...
{2,3,5,7,11,13,17,19,23}
6
Returns: 6.0
{2,3,7,7,11,13}
3
Returns: 0.25
{2,3,5,7,11,13,17,19,23}
5
Returns: 2.333333333333334
worst case
Submissions are judged against all 49 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GroupingNumbers with a public method double minRange(vector<int> numbers, int n) · 49 test cases · 2 s / 256 MB per case