MeanMedian
SRM 768 · 2019-10-09 · by Errichto
Problem Statement
Bear Limak has just started a new year at school. The school teaches N subjects. At the end of the year Limak will get a grade for each of the subjects. Each grade will be an integer between 0 (worst) and 10 (best), inclusive.
The grade for each subject depends on the number of days Limak will spend studying that subject. If he does not study a subject at all, his grade for that subject will be 0. Each subject has its own difficulty rating d[i]: each d[i] days spent studying the subject will increase Limak's grade by 1 (up to a maximum of 10, of course).
Note that these increases are discrete. E.g., if Limak spends d[i]-1 days studying subject i, his grade will still be 0.
Limak's parents are quite strict. Each of them has made a request:
- Mama bear told Limak that his mean grade must be at least needMean.
- Papa bear told Limak that his median grade must be at least needMedian.
Compute and return the smallest possible number of days of studying Limak needs in order to satisfy the requests of both parents.
Notes
- The mean of N values is their sum divided by N. (The mean can be non-integer.)
- The median of N values is the middle element of a sorted list of all those values. (In this problem, N is always odd and thus the middle element always exists.)
Constraints
- needMean will be between 0 and 10, inclusive.
- needMedian will be between 0 and 10, inclusive.
- N (the number of elements in d) will be between 1 and 49, inclusive.
- N will be odd.
- Each element in d will be between 1 and 1000, inclusive.
2
4
{30, 25, 20}
Returns: 180
There are three subjects at school. Limak's grades should have mean at least 2 and median at least 4. The only optimal solution is to study subject 0 for 0 days, subject 1 for 4*25 = 100 days and subject 2 for 4*20 = 80 days. Afterwards, Limak's grades will be {0, 4, 4}. Their mean is 8/3 (which is more than we need) and their median is 4 (which is exactly what we need).
4
4
{30, 25, 20}
Returns: 260
Limak should get grades 0, 4, 8. The mean is exactly 4 and so is the median. The answer is 4*25+8*20=260.
10
3
{1, 4, 3, 2, 1}
Returns: 110
0
0
{1000}
Returns: 0
8
3
{4, 8, 12, 16, 18, 20, 22, 23, 24}
Returns: 1046
Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MeanMedian with a public method int minEffort(int needMean, int needMedian, vector<int> d) · 71 test cases · 2 s / 256 MB per case