AquaparkPuzzle
SRM 645 · 2014-12-30 · by w10d
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.
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.
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
Submissions are judged against all 22 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AquaparkPuzzle with a public method int countSchedules(int k, int m, vector<int> c) · 22 test cases · 2 s / 256 MB per case