SpaceMission | Topcoder Archive

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 int[] parity where the value 0 denotes that this country will send an even-numbered team while 1 is a team of odd size.

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.

Definition

Class:: SpaceMission
Method:: count
Parameters:: int[], int[], int[], int, int, int
Returns:: int
Method signature:: int count(int[] minn, int[] maxn, int[] parity, int mint, int maxt, int modulus)
(be sure your method is public)

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.

Examples

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

Returns: 210

```
{10}
```
```
{10}
```
```
{0}
```
```
11
```
```
11
```
```
12345
```
```
Returns: 0
```

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.