FoxJumping | Topcoder Archive

Problem Statement

Fox Ciel likes to jump around in large fields. She is currently at point (0, 0) of a field, and she wants to land at point (Tx, Ty) using exactly R jumps.

In one jump, she can move 0, 1, 2, ..., Mx units in the positive x direction and 0, 1, 2, ..., My units in the positive y direction. All jumps must have a non-zero distance. In addition, there are some jumps which she is not good at. These jumps are described in the int[] bad. If bad contains the number b, it means she cannot make a diagonal jump where she moves exactly b units in the positive x direction and b units in the positive y direction. Each element of bad will be a multiple of 10.

For instance, if Mx=12, My=11, bad={10} and she is at point (0, 0), then the only points she can jump to are the green ones shown below:

Return the number of ways she can start at (0, 0), jump exactly R times, and land at (Tx, Ty), modulo 10,007. Two ways are considered to be different if there is an index i, 0 <= i < R, such that Ciel lands at different points after the i-th (0-based) jump in these ways.

Definition

Class:: FoxJumping
Method:: getCount
Parameters:: int, int, int, int, int, int[]
Returns:: int
Method signature:: int getCount(int Tx, int Ty, int Mx, int My, int R, int[] bad)
(be sure your method is public)

Constraints

Tx and Ty will each be between 1 and 800, inclusive.
Mx and My will each be between 1 and 800, inclusive.
R will be between 1 and 1,600, inclusive.
bad will contain between 0 and 50 elements, inclusive.
Each element of bad will be between 1 and min(Mx, My), inclusive, and be a multiple of 10.
All elements of bad will be distinct.

Examples

```
2
```
```
2
```
```
1
```
```
1
```
```
2
```
```
{}
```
```
Returns: 1
```
There is only 1 way to reach the destination.
```
2
```
```
2
```
```
1
```
```
1
```
```
3
```
```
{}
```
```
Returns: 6
```
The following are the 6 ways she can reach her destination. Note that when she jumps, she must move a distance of at least one unit.
```
10
```
```
10
```
```
10
```
```
10
```
```
1
```
```
{}
```
```
Returns: 1
```
She can jump only once, so there is 1 way to reach the destination.
```
10
```
```
10
```
```
10
```
```
10
```
```
1
```
```
{10}
```
```
Returns: 0
```
This case is almost the same as the previous one. However, in this case, the required jump is a bad jump, so she cannot reach the destination in a single jump.
```
11
```
```
11
```
```
11
```
```
11
```
```
2
```
```
{10}
```
```
Returns: 140
```

{30, 40, 20, 10, 50}

Returns: 6723

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.