FoxJumping

SRM 498 · 2010-11-01 · by ir5

SRM 498 · 2010-11-01 · by ir5 · Dynamic Programming, Math

Show categories

Class Name: FoxJumping

Return Type: int

Method Name: getCount

Arg Types: (int, int, int, int, int, vector<int>)

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.

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

776
612
800
800
333
{30,60,80,110,200}
Returns: 6355

random case

725
677
23
481
33
{20}
Returns: 6041

random case

714
2
91
800
202
{}
Returns: 2805

random case

1
1
1
1
1600
{}
Returns: 0

large R

10)

72
90
44
59
1587
{20,40}
Returns: 0

large R

11)

349
791
154
199
1533
{40,90,130}
Returns: 0

large R

12)

800
800
800
800
1600
{10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500}
Returns: 2809

Full power

18)

800
800
800
800
1599
{10,30,50,70,90,110,130,150,170,190,210,230,250,270,290,310,330,350,370,390,410,430,450,470,490,510,530,550,570,590,610,630}
Returns: 5639

odd number only

20)

1
1
1
1
1
{}
Returns: 1

small cases

48)

28
25
23
10
51
{}
Returns: 7792

middle cases (bad = {})

128)

1
1
10
10
1
{10}
Returns: 1

bad.length = 1

168)

60
606
736
744
3
{160,730,500,140,210}
Returns: 7364

random (bad.length >=2 )

208)

258
102
25
257
281
{20,10}
Returns: 0

Result divisible by MOD

209)

168
194
273
35
214
{10,20}
Returns: 10006

MOD-1

210)

83
260
255
277
162
{50,100,200,20,90}
Returns: 0

Result divisible by MOD

Submissions are judged against all 216 archived test cases, of which 20 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FoxJumping with a public method int getCount(int Tx, int Ty, int Mx, int My, int R, vector<int> bad) · 216 test cases · 2 s / 256 MB per case