MeanMedianCount | Topcoder Archive

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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.