NarrowPassage2
SRM 638 · 2014-08-25 · by cgy4ever
SRM 638 · 2014-08-25 · by cgy4ever · Math
Problem Statement
Problem Statement
There is a narrow passage.
Inside the passage there are some wolves.
You are given a int[] size that contains the sizes of those wolves, from left to right.
The passage is so narrow that some pairs of wolves cannot pass by each other. More precisely, two adjacent wolves may swap places if and only if the sum of their sizes is maxSizeSum or less. Assuming that no wolves leave the passage, what is the number of different permutations of wolves in the passage? Note that two wolves are considered different even if they have the same size.
Let X be the number of permutations of wolves that can be obtained from their initial order by swapping a pair of wolves zero or more times. Compute and return the value (X modulo 1,000,000,007).
The passage is so narrow that some pairs of wolves cannot pass by each other. More precisely, two adjacent wolves may swap places if and only if the sum of their sizes is maxSizeSum or less. Assuming that no wolves leave the passage, what is the number of different permutations of wolves in the passage? Note that two wolves are considered different even if they have the same size.
Let X be the number of permutations of wolves that can be obtained from their initial order by swapping a pair of wolves zero or more times. Compute and return the value (X modulo 1,000,000,007).
Constraints
- size will contain between 1 and 50 elements, inclusive.
- Each element in size will be between 1 and 1,000,000,000, inclusive.
- maxSizeSum will be between 1 and 1,000,000,000, inclusive.
Examples
0)
{1, 2, 3}
3
Returns: 2
From {1, 2, 3}, you can swap 1 and 2 to get {2, 1, 3}. But you can't get other permutations.
1)
{1, 2, 3}
1000
Returns: 6
Here you can swap any two adjacent wolves. Thus, all 3! = 6 permutations are possible.
2)
{1, 2, 3}
4
Returns: 3
You can get {1, 2, 3}, {2, 1, 3} and {2, 3, 1}.
3)
{1,1,1,1,1,1,1,1,1,1,1,1,1}
2
Returns: 227020758
All of these wolves are different, even though their sizes are the same. Thus, there are 13! different permutations possible.
4)
{2,4,6,1,3,5}
8
Returns: 60
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NarrowPassage2 with a public method int count(vector<int> size, int maxSizeSum) · 82 test cases · 2 s / 256 MB per case