AquaparkPuzzle | Topcoder Archive

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 ints k and m, and the int[] c. You know that during her k visits to the aquapark Ania wants to visit each attraction at least twice. Count the number of ways in which she can do so, and return that count modulo 1,000,000,007.

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

{8, 2, 13, 18, 7, 3}

Returns: 15681195

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.