CustomDice
SRM 416 · 2008-09-03 · by xOberon
Problem Statement
In a Las Vegas casino, a new type of six-sided die is being introduced. These dice may have any positive integers written its sides, but no two sides of the same die can contain the same number. For each die, the casino owner wants the mean value of the numbers written on its sides to not exceed M.
Compute the total number of allowed dice. Two dice are considered different if one can't be obtained from the other using rotations. Since the resulting number may be quite large, return it modulo 1000000007.
Constraints
- M will be between 1 and 1000000, inclusive.
3 Returns: 0
The die with the smallest possible mean is {1,2,3,4,5,6}. Its mean is 3.5, which is greater than M=3.
4 Returns: 210
There are 30 different dice with numbers {1,2,3,4,5,6} on their sides, they each have a mean of 3.5. There are 30 different dice with numbers {1,2,3,4,5,7} on their sides, they each have a mean of 22/6=3.(6). There are 60 different dice with {1,2,3,4,5,8} or {1,2,3,4,6,7} on their sides, they each have a mean of 23/6=3.8(3). There are 90 different dice with {1,2,3,4,5,9}, {1,2,3,4,6,8} or {1,2,3,5,6,7} on their sides, they each have a mean of 24/6=4.
10 Returns: 863010
20 Returns: 101548350
50 Returns: 375588112
Submissions are judged against all 36 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CustomDice with a public method int countDice(int M) · 36 test cases · 2 s / 256 MB per case