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).
Definition
- Class:
- MeanMedianCount
- Method:
- getCount
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int getCount(int N, int needMean, int needMedian)
- (be sure your method is public)
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.
Examples
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.
1
4
8
Returns: 3
1
9
5
Returns: 2
1
0
0
Returns: 11
1
0
1
Returns: 10
1
1
0
Returns: 10
1
9
10
Returns: 1
1
10
9
Returns: 1
1
10
10
Returns: 1
3
0
0
Returns: 1331
3
0
1
Returns: 1300
3
1
0
Returns: 1321
3
9
10
Returns: 10
3
10
9
Returns: 1
3
10
10
Returns: 1
5
2
7
Returns: 41344
5
8
2
Returns: 3003
7
0
6
Returns: 7821875
9
7
0
Returns: 75828577
11
0
4
Returns: 24951519
13
7
10
Returns: 535634731
15
10
6
Returns: 1
17
10
2
Returns: 1
19
3
10
Returns: 413843015
25
1
8
Returns: 796864928
27
4
8
Returns: 571458070
29
8
4
Returns: 422487571
31
1
2
Returns: 196984819
33
2
1
Returns: 956887568
35
2
2
Returns: 388624237
45
9
8
Returns: 531231092
47
8
9
Returns: 315188317
47
9
9
Returns: 417905090
49
1
3
Returns: 744698946
47
3
1
Returns: 19904097
49
3
3
Returns: 965415276
49
1
6
Returns: 213285912
49
2
10
Returns: 869041164
49
2
3
Returns: 547013693
49
2
10
Returns: 869041164
49
6
4
Returns: 158461264
49
5
0
Returns: 183444177
49
3
1
Returns: 321352154
49
7
3
Returns: 742421908
49
2
4
Returns: 267947890
49
4
2
Returns: 665396467
49
0
0
Returns: 21051900
49
10
10
Returns: 1
49
0
10
Returns: 869041164
49
10
0
Returns: 1
1
1
1
Returns: 10
5
3
4
Returns: 119497
13
4
2
Returns: 801095039