SpaceMission
SRM 826 · 2022-03-28 · by misof
Problem Statement
Several countries want to take part in a project of a new space station. Each country will send some number of astronauts to the station.
Country i has the condition that the number of astronauts from the country must be between minn[i] and maxn[i], inclusive.
Different countries have different opinions on parity.
Some countries think it's important to have an even number of astronauts so that everyone can find a partner to work with.
Other countries think it's important to have an odd number of astronauts so that they are forced to interact with each other instead of just splitting into disjoint couples.
This opinion is given in the
According to the plans of the space station, the total size of the crew must be between mint and maxt, inclusive.
Two ways of sending astronauts to the space station differ if at least one country sent a different number of astronauts. Count all valid ways and report that count modulo modulus.
Constraints
- minn will have between 1 and 13 elements, inclusive.
- maxn will have the same number of elements as minn.
- parity will have the same number of elements as minn.
- For each valid i: 0 <= minn[i] <= maxn[i] <= 10^9.
- sum(maxn) will not exceed 10^9.
- Each element of parity will be 0 or 1.
- 0 <= mint <= maxt <= 10^9.
- modulus will be between 1 and 10^9, inclusive.
{0, 0}
{10, 10}
{0, 0}
1
9
10000
Returns: 14
Two countries A and B, each wants to send an even number of people between 0 and 10 to the station. The station can accommodate between 1 and 9 people total. The valid ways of sending the astronauts are AA, AAAA, AAAAAA, AAAAAAAA, BB, AABB, AAAABB, AAAAAABB, BBBB, AABBBB, AAAABBBB, BBBBBB, AABBBBBB, and BBBBBBBB.
{0, 0}
{10, 10}
{0, 0}
1
9
10
Returns: 4
Same as Example 0, but now we are calculating modulo 10 so the return value is different.
{1, 2, 3}
{100, 100, 100}
{1, 1, 1}
1
8
12345
Returns: 1
Each of these countries wants to send an odd number of astronauts. The minimum numbers are 1 + 3 + 3, and it is obvious that any other choice would produce a total that is larger than 8.
{1, 3, 7, 2}
{15, 22, 29, 30}
{1, 0, 0, 1}
7
28
10000
Returns: 210
{10}
{10}
{0}
11
11
12345
Returns: 0
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SpaceMission with a public method int count(vector<int> minn, vector<int> maxn, vector<int> parity, int mint, int maxt, int modulus) · 96 test cases · 2 s / 256 MB per case