WolfInZooDivTwo
SRM 578 · 2012-12-13 · by tozangezan
SRM 578 · 2012-12-13 · by tozangezan · Dynamic Programming
Problem Statement
Problem Statement
Mr. Pasuterukun is walking along a straight road.
He is cautious, because he has heard that there may be some wolves on the road.
The road consists of N sections. The sections are numbered 0 through N-1, in order. Each section of the road contains at most one wolf.
You have M additional pieces of information about the positions of the wolves. Each piece of information is an interval of the road that contains at least one wolf. More precisely, for each i between 0 and M-1, inclusive, you are given two integers left[i] and right[i] such that the sections with numbers in the range from left[i] to right[i], inclusive, contain at least one wolf in total.
You are given twoString[] s L and R.
The concatenation of all elements of L will be a single space separated list containing the integers left[0] through left[M-1].
R contains all the integers right[i] in the same format.
Return the number of ways in which wolves can be distributed in the sections of the road, modulo 1,000,000,007.
The road consists of N sections. The sections are numbered 0 through N-1, in order. Each section of the road contains at most one wolf.
You have M additional pieces of information about the positions of the wolves. Each piece of information is an interval of the road that contains at least one wolf. More precisely, for each i between 0 and M-1, inclusive, you are given two integers left[i] and right[i] such that the sections with numbers in the range from left[i] to right[i], inclusive, contain at least one wolf in total.
You are given two
Return the number of ways in which wolves can be distributed in the sections of the road, modulo 1,000,000,007.
Constraints
- N will be between 1 and 300, inclusive.
- L and R will contain between 1 and 50 elements, inclusive.
- Each element of L and R will contain between 1 and 50 characters, inclusive.
- Each character in L and R will be a digit ('0'-'9') or a space (' ').
- M will be between 1 and 300, inclusive.
- The concatenation of all elements of L will be a single space separated list of M integers. The integers will be between 0 and N-1, inclusive, and they will be given without unnecessary leading zeroes.
- The concatenation of all elements of R will be a single space separated list of M integers. The integers will be between 0 and N-1, inclusive, and they will be given without unnecessary leading zeroes.
- For each i, the i-th integer in L will be smaller than or equal to the i-th integer in R.
Examples
0)
5
{"0 1"}
{"2 4"}
Returns: 27
There is at least one wolf on the sections 0 through 2, and at least one wolf on the sections 1 through 4.
1)
10
{"0 4 2 7"}
{"3 9 5 9"}
Returns: 798
2)
100
{"0 2 2 7 10 1","3 16 22 30 33 38"," 42 44 49 51 57 60 62"," 65 69 72 74 77 7","8 81 84 88 91 93 96"}
{"41 5 13 22 12 13 ","33 41 80 47 40 ","4","8 96 57 66 ","80 60 71 79"," 70 77 ","99"," 83 85 93 88 89 97 97 98"}
Returns: 250671525
You must first concatenate the elements of L and only then split it into integers. The same holds for R.
3)
1
{"0"}
{"0"}
Returns: 1
4)
3
{"1"}
{"2"}
Returns: 6
The following picture shows all possible patterns.
Submissions are judged against all 169 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class WolfInZooDivTwo with a public method int count(int N, vector<string> L, vector<string> R) · 169 test cases · 2 s / 256 MB per case