Problem Statement
Young Ania's dream has come true: a great aquapark was built in her town. There are many attractions in the aquapark. For each valid i, there is an attraction that costs c[i] dollars.
Ania is going to visit the aquapark exactly k times. As she doesn't have too much money, she decided that:
- during each visit she is going to visit each attraction at most once
- during each visit she will spend at most m dollars on attractions
You are given the
Two ways are considered different if there are integers i and j such that on the i-th visit to the aquapark she is going to visit the j-th attraction in one of the ways but not in the other.
Definition
- Class:
- AquaparkPuzzle
- Method:
- countSchedules
- Parameters:
- int, int, int[]
- Returns:
- int
- Method signature:
- int countSchedules(int k, int m, int[] c)
- (be sure your method is public)
Notes
- During some visits to the aquapark Ania may not visit any attractions at all.
Constraints
- k will be between 2 and 1,000,000, inclusive.
- m will be between 1 and 1,000, inclusive.
- Each element of c will be between 1 and 1,000, inclusive.
- c will have between 2 and 11 elements.
Examples
3
3
{1, 2}
Returns: 16
Ania has enough money to visit all attractions during each visit to the aquapark, so we can treat each attraction independently. For each attraction we have 4 possibilities: either she visits it all three times, or she skips it on one of her three visits to the aquapark. Hence, there are 4*4 = 16 valid schedules.
3
3
{2, 2}
Returns: 0
During each visit Ania can only afford one attraction. Given that constraint, three visits to the aquapark are not enough to visit each attraction at least twice.
4
3
{1, 2, 2}
Returns: 66
6
7
{2, 3, 4, 7}
Returns: 4800
1000
20
{8, 2, 13, 18, 7, 3}
Returns: 15681195
3
2
{1, 1, 1}
Returns: 6
2
30
{5,1,3,1,4}
Returns: 1
1000000
1000
{1,2,3,4,5,6,7,8,9,10,11}
Returns: 5069980
1000000
100
{1,2,32,2,4,5,6,101}
Returns: 0
4
500
{5,4,12,4,70}
Returns: 161051
1000
1000
{1,2,3,4,5,6,7,8,9,10,11}
Returns: 986077190
39454
998
{329,434,101,666,900}
Returns: 167005902
10
100
{54,23,90,22,1,32,5,12}
Returns: 305004511
432
924
{129,234,300,46,500,678,709,809,924,103}
Returns: 162356642
32134
786
{129,245,343,490,5,621,79,376,724,103,119}
Returns: 127460261
453554
67
{6,2,2,4,5,12,4,1,19,3,13}
Returns: 316427994
364672
600
{165,225,34,40,565,6,79,87,92,104,119}
Returns: 248513222
999324
812
{125,285,37,41,56,63,72,83,9,102,111}
Returns: 17832262
978333
997
{125,254,373,414,536,633,754,802,99,104,111}
Returns: 897336312
455345
17
{1,1,1,1,1,1,1,1,1,1,10}
Returns: 62856788
897111
1000
{897,54,3,45,15,6,78,8,9,102,11}
Returns: 401578363
1000000
63
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }
Returns: 145144693