MeanMedianCount
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.
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.
There are 11 possible grades for each subject, so 11^N possible scenarios in total (each being a sequence of N grades). Among them, count and return the number of scenarios for which Limak would satisfy the requests of both parents. Return the answer modulo 1000000007 (this is 10^9 + 7).
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
- N will be between 1 and 49, inclusive.
- N will be odd.
- needMean will be between 0 and 10, inclusive.
- needMedian will be between 0 and 10, inclusive.
3 9 10 Returns: 10
Limak has three subjects and he needs the mean 9 or greater, and the median exactly 10 (you can't go higher with grades up to 10). There are ten scenarios where these two conditions are satisfied: (7,10,10), (8,10,10), (9,10,10), (10,7,10), (10,8,10), (10,9,10), (10,10,7), (10,10,8), (10,10,9), (10,10,10).
3 7 8 Returns: 162
There are 162 allowed scenarios and one of them is (10, 3, 9). The mean is (10+3+9)/3 = 22/3 = 8.3333..., which is not smaller than the required mean of 8. A sorted sequence of grades would be (3, 9, 10) so the median is 9.
5 10 8 Returns: 1
There is only one way to get the mean of grades at least 10. Limak needs to get grade 10 in all five subjects: (10, 10, 10, 10, 10).
5 7 1 Returns: 14874
49 0 0 Returns: 21051900
The answer is 11^49. Don't forget about modulo.
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MeanMedianCount with a public method int getCount(int N, int needMean, int needMedian) · 57 test cases · 2 s / 256 MB per case