TopCoder Statistics - Problem Statement

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
123

456

70

80

90

{30, 40, 20, 10, 50}

Returns: 6723
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
72

90

44

59

1587

{20,40}

Returns: 0

large R
349

791

154

199

1533

{40,90,130}

Returns: 0

large R
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
800

800

800

800

1550

{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: 6975
800

800

800

800

1587

{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: 2007
800

800

800

800

1521

{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: 6518
800

800

800

800

808

{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: 4067
800

800

800

800

472

{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: 3177
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
800

800

800

800

422

{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: 4240
1

1

1

1

1

{}

Returns: 1

small cases
1

2

1

1

1

{}

Returns: 0
1

2

1

2

1

{}

Returns: 1
2

2

2

2

1

{}

Returns: 1
5

5

5

5

1

{}

Returns: 1
1

1

1

1

2

{}

Returns: 2
1

2

1

1

2

{}

Returns: 2
2

1

1

2

2

{}

Returns: 2
2

1

2

1

2

{}

Returns: 4
2

1

2

2

2

{}

Returns: 4
2

2

1

1

2

{}

Returns: 1
2

2

2

2

2

{}

Returns: 7
3

1

1

1

2

{}

Returns: 0
3

1

2

2

2

{}

Returns: 4
2

3

2

2

2

{}

Returns: 6
1

1

1

1

3

{}

Returns: 0
1

1

1

2

3

{}

Returns: 0
1

1

2

2

3

{}

Returns: 0
1

2

1

1

3

{}

Returns: 3
1

2

1

2

3

{}

Returns: 3
1

2

2

1

3

{}

Returns: 3
1

3

1

2

3

{}

Returns: 9
1

3

1

3

3

{}

Returns: 9
2

3

2

2

3

{}

Returns: 24
2

3

2

3

3

{}

Returns: 27
3

3

1

1

3

{}

Returns: 1
3

3

2

2

3

{}

Returns: 37
3

3

3

3

3

{}

Returns: 55
28

25

23

10

51

{}

Returns: 7792

middle cases (bad = {})
20

18

8

13

31

{}

Returns: 8377
10

11

9

11

20

{}

Returns: 3120
19

20

19

15

33

{}

Returns: 2144
34

27

3

11

52

{}

Returns: 2417
10

12

7

4

22

{}

Returns: 6198
21

20

8

15

35

{}

Returns: 493
30

33

11

9

55

{}

Returns: 470
67

54

27

1

105

{}

Returns: 75
64

107

34

53

163

{}

Returns: 9493
113

118

88

62

209

{}

Returns: 9365
95

107

47

80

172

{}

Returns: 4780
103

96

5

91

195

{}

Returns: 8950
131

118

35

18

218

{}

Returns: 5863
79

120

31

21

181

{}

Returns: 4207
64

48

24

48

107

{}

Returns: 954
322

247

17

154

529

{}

Returns: 1203
252

315

185

123

528

{}

Returns: 4335
220

203

38

182

406

{}

Returns: 7750
337

254

217

124

509

{}

Returns: 3137
292

213

63

92

445

{}

Returns: 5898
296

210

94

13

454

{}

Returns: 207
318

250

310

55

522

{}

Returns: 8170
302

272

292

213

507

{}

Returns: 632
332

513

79

380

835

{}

Returns: 1764
501

513

398

86

857

{}

Returns: 3372
590

513

199

419

1030

{}

Returns: 1611
510

689

317

124

1065

{}

Returns: 6170
501

480

107

426

810

{}

Returns: 1440
583

619

16

296

943

{}

Returns: 8108
500

703

460

4

1132

{}

Returns: 4173
560

557

135

453

1076

{}

Returns: 4598
796

708

498

345

1476

{}

Returns: 7062
779

763

150

157

1534

{}

Returns: 3109
739

773

386

160

1472

{}

Returns: 1754
794

731

593

520

1519

{}

Returns: 1058
777

792

98

519

1550

{}

Returns: 8397
789

738

117

175

1487

{}

Returns: 7610
766

793

458

408

1488

{}

Returns: 8244
723

794

421

262

1495

{}

Returns: 5377
17

20

43

285

31

{}

Returns: 6506
17

20

15

672

31

{}

Returns: 6506
18

24

357

171

39

{}

Returns: 28
18

24

12

172

39

{}

Returns: 28
12

14

149

89

24

{}

Returns: 4003
12

14

132

12

24

{}

Returns: 4003
26

25

644

118

39

{}

Returns: 9482
26

25

14

627

39

{}

Returns: 9482
64

58

273

603

103

{}

Returns: 1675
64

58

108

55

103

{}

Returns: 1675
62

75

643

597

126

{}

Returns: 5292
62

75

9

151

126

{}

Returns: 5816
51

88

82

192

134

{}

Returns: 8425
51

88

336

71

134

{}

Returns: 8425
59

50

517

108

108

{}

Returns: 6952
59

50

456

31

108

{}

Returns: 6952
236

299

629

549

487

{}

Returns: 621
236

299

303

57

487

{}

Returns: 621
255

191

473

272

440

{}

Returns: 9398
255

191

53

323

440

{}

Returns: 9398
232

226

245

430

452

{}

Returns: 3185
232

226

22

359

452

{}

Returns: 3185
312

305

474

390

539

{}

Returns: 5011
312

305

22

636

539

{}

Returns: 944
502

491

648

545

872

{}

Returns: 5254
502

491

692

197

872

{}

Returns: 5254
439

540

762

708

928

{}

Returns: 8727
439

540

408

659

928

{}

Returns: 8727
680

632

737

779

1073

{}

Returns: 2773
680

632

721

59

1073

{}

Returns: 8543
476

468

743

793

910

{}

Returns: 910
476

468

135

675

910

{}

Returns: 910
749

794

770

796

1518

{}

Returns: 3351
749

794

144

796

1518

{}

Returns: 3351
686

766

708

771

1414

{}

Returns: 7035
686

766

720

414

1414

{}

Returns: 7035
724

784

725

786

1498

{}

Returns: 1566
724

784

614

789

1498

{}

Returns: 1566
798

776

798

791

1479

{}

Returns: 209
798

776

800

582

1479

{}

Returns: 209
1

1

10

10

1

{10}

Returns: 1

bad.length = 1
1

1

10

10

2

{10}

Returns: 2
2

3

10

10

1

{10}

Returns: 1
2

3

10

10

2

{10}

Returns: 10
8

6

10

10

4

{10}

Returns: 9194
9

10

10

10

1

{10}

Returns: 1
10

9

10

10

10

{10}

Returns: 2143
10

9

10

10

19

{10}

Returns: 2315
10

9

10

10

20

{10}

Returns: 0
10

10

10

10

1

{10}

Returns: 0
10

10

10

10

2

{10}

Returns: 119
800

1

10

10

80

{10}

Returns: 80
800

1

10

10

222

{10}

Returns: 4241
800

1

10

10

799

{10}

Returns: 1774
800

1

10

10

800

{10}

Returns: 9559
800

1

10

10

801

{10}

Returns: 801
800

800

10

10

79

{10}

Returns: 0
800

800

10

10

80

{10}

Returns: 0
800

800

10

10

81

{10}

Returns: 0
800

800

10

10

99

{10}

Returns: 1908
800

800

10

10

121

{10}

Returns: 2249
800

800

10

10

589

{10}

Returns: 4527
800

800

10

10

1600

{10}

Returns: 2809
784

799

11

12

99

{10}

Returns: 5508
725

748

13

12

127

{10}

Returns: 9813
698

797

89

201

666

{10}

Returns: 5953
698

797

89

201

666

{20}

Returns: 4408
698

797

89

201

666

{30}

Returns: 7130
698

797

89

201

666

{40}

Returns: 5144
698

797

89

201

666

{50}

Returns: 3584
698

797

89

201

666

{60}

Returns: 5541
698

797

89

201

666

{70}

Returns: 8745
800

800

800

800

1

{800}

Returns: 0
800

800

800

800

2

{800}

Returns: 1151
799

800

792

798

2

{790}

Returns: 6006
798

800

792

798

3

{790}

Returns: 4761
799

800

792

798

55

{790}

Returns: 8382
799

800

792

798

2

{740}

Returns: 6006
798

800

792

798

3

{740}

Returns: 4268
799

800

792

798

49

{740}

Returns: 9111
60

606

736

744

3

{160,730,500,140,210}

Returns: 7364

random (bad.length >=2 )
758

31

800

791

4

{210,360,420,670,520,560,620,790}

Returns: 9177
83

659

784

777

4

{730,660,580,510,470,450,420,350,270,30}

Returns: 4910
613

157

733

696

12

{650,430,400,380}

Returns: 7270
596

525

660

679

68

{110,100,320,590,330,360}

Returns: 4479
90

106

798

798

42

{10,100,170,210,420,460,480,540,780,790}

Returns: 5071
737

224

794

780

252

{660,210,120,770,190,690,560,50,440}

Returns: 9119
577

49

753

771

1097

{10,70,180,300,330,350,520,620,740}

Returns: 0
721

423

783

780

1159

{20,30,180,690}

Returns: 0
587

213

753

757

1011

{590,380,160}

Returns: 0
300

78

791

794

3

{760,700,680,670,660,650,520,490,410,350,260,220,210,140,130,100,80,50,20}

Returns: 1907
434

364

800

800

2

{30,60,70,160,200,250,280,340,350,370,410,430,440,450,580,590,600,650,670,700,730,740,750,780,800}

Returns: 8650
730

753

797

796

4

{60,70,90,110,210,230,260,290,300,320,350,390,420,440,460,490,540,600,630,650,680,740,770}

Returns: 8577
689

256

800

800

13

{520,670,50,500,800,430,260,60,710,200,220,280,750,80,210,400,790,100,580,470,720,780,630,420,90,540,600,270,360}

Returns: 3919
201

213

789

775

41

{740,710,620,610,560,520,490,400,320,250,220,180,170,160,150,130,110,80,70,30,10}

Returns: 9321
117

388

791

777

90

{740,380,490,150,590,100,520,550,30,330,440,80}

Returns: 5333
594

29

764

794

298

{50,200,330,510,180,470,130,440,240,720,250,750,190,400,150,420,460,520,230,260,170,690,480,390}

Returns: 8941
633

793

800

794

1103

{30,60,90,110,140,150,180,230,300,370,400,470,520,600,660,690,720,790}

Returns: 2388
632

690

797

796

1028

{790,770,760,750,670,630,620,540,520,490,480,430,410,360,340,320,310,290,280,250,230,200,150,120,110,30}

Returns: 8950
650

154

795

796

1067

{770,420,350,10,30,780,390,670,290,20,380,90,720,340,40,410,190,790,710,640,260,750,440,150,690,360,270}

Returns: 0
719

570

781

789

4

{410,440,520,750,310,260,590,180,780,330,90,340,140,490,210,250,40,550,320,450,280,220,10,600,30,350,740,710,150,190,720,770,680,130,390,690}

Returns: 1208
2

275

800

800

2

{60,80,90,120,130,140,150,160,170,180,210,230,240,250,260,270,310,320,330,340,370,390,450,460,500,510,530,540,570,580,590,600,610,640,660,670,690,700,800}

Returns: 826
33

91

793

794

4

{10,50,60,80,130,140,190,200,210,280,290,350,400,420,430,520,530,540,570,590,600,610,630,640,650,710,720,760,780,790}

Returns: 7787
712

672

794

761

18

{710,680,110,170,180,320,340,230,560,490,440,80,130,270,400,380,570,620,540,760,60,660,420,450,310,240,480,530,300,140,160,740,650}

Returns: 2990
304

471

794

791

98

{790,780,770,760,750,720,670,650,630,580,570,560,550,540,530,510,500,490,470,460,420,400,370,350,340,320,300,290,280,270,260,240,230,210,200,160,150,120,110,100,80,70,60,20,10}

Returns: 9026
375

164

776

778

46

{10,20,30,40,50,70,90,110,140,170,180,190,230,240,250,290,300,320,330,370,390,400,440,450,490,530,580,600,610,620,650,670,680,710,730,770}

Returns: 5465
679

595

798

793

384

{770,760,740,730,710,630,570,550,540,520,510,490,470,450,420,390,350,340,300,290,250,240,180,140,130,120,110,100,80,60,50,40}

Returns: 6044
255

652

794

783

1045

{10,30,40,50,70,80,90,100,110,150,170,180,190,200,210,220,230,240,250,280,300,310,320,360,410,430,480,490,500,530,550,600,620,680,690,710,740,750,780}

Returns: 0
747

495

800

800

1014

{230,170,240,650,480,150,610,350,430,220,770,60,630,160,210,100,20,420,190,760,750,390,130,700,470,260,560,800,790,490,280,70,30,330,780,510,580,410,270,730,710,740}

Returns: 8459
505

236

782

797

1058

{620,30,470,590,680,380,640,350,20,570,500,140,160,750,660,670,630,610,120,770,560,330,400,210,290,130,40,280,780,420,430,460,440,550,270}

Returns: 0
666

115

800

800

3

{800,770,760,720,710,700,690,680,670,660,650,640,620,610,560,550,530,490,450,430,420,390,380,360,340,330,320,290,280,270,250,230,200,180,170,160,150,140,130,110,100,90,80,70,60,40,20}

Returns: 3319
15

558

799

791

4

{790,770,760,750,740,730,720,700,690,680,650,640,620,590,580,570,560,540,530,520,510,500,490,460,440,430,410,390,370,360,350,310,290,280,250,220,210,190,170,160,150,140,120,100,90,70,50,40,20}

Returns: 9255
665

683

800

800

2

{10,20,30,50,60,80,110,140,150,160,170,180,210,220,240,250,260,280,310,340,350,380,390,410,420,430,440,470,480,490,500,510,530,540,580,590,630,640,670,680,730,740,760,770,780,790,800}

Returns: 5151
786

327

795

795

10

{770,610,400,510,660,480,290,790,350,440,740,600,300,80,690,210,100,340,420,650,720,270,60,190,780,700,540,380,390,170,730,360,680,320,240,310,130,410,550,570,140,220,20,260,120,630,30}

Returns: 901
1

560

800

794

48

{790,780,770,750,740,700,680,620,610,600,590,580,570,560,550,540,520,510,500,490,480,460,450,440,430,420,410,400,390,380,370,350,300,280,270,250,220,210,190,180,170,160,150,130,120,110,100,80,70,60}

Returns: 3373
286

536

800

800

83

{800,780,770,760,740,720,710,700,680,670,660,640,590,540,530,510,480,470,450,430,420,410,390,380,370,360,350,320,300,290,280,270,250,230,220,210,200,170,140,130,110,80,70,30,20,10}

Returns: 5036
222

403

781

792

667

{10,30,40,60,70,80,90,110,140,180,190,200,210,220,240,270,330,340,350,380,390,410,420,430,450,460,470,490,510,520,530,540,560,570,590,600,620,650,660,690,710,730,740,750,780}

Returns: 0
724

345

789

787

1011

{260,180,530,730,360,780,380,20,120,670,90,370,70,50,770,520,290,480,580,230,200,130,80,210,40,60,630,390,400,550,140,320,650,610,500,490,430,470,440,460,220,310,640,300,30,250,710,760,150}

Returns: 5544
524

14

792

792

1134

{700,200,530,340,160,110,680,740,590,10,190,380,460,690,260,560,40,410,310,790,90,720,230,610,300,80,70,170,100,350,490,660,400,60,780,240,640,620,440,650,430,130,420,330,480,140,550,20,710}

Returns: 0
567

190

800

800

1155

{800,770,740,730,720,710,700,690,670,660,640,610,570,540,530,510,470,460,450,440,430,420,410,390,380,350,320,310,300,290,270,260,250,230,220,210,200,190,180,170,160,150,120,110,100,40,20,10}

Returns: 0
258

102

25

257

281

{20,10}

Returns: 0

Result divisible by MOD
168

194

273

35

214

{10,20}

Returns: 10006

MOD-1
83

260

255

277

162

{50,100,200,20,90}

Returns: 0

Result divisible by MOD
123

456

70

80

90

{30, 40, 20, 10, 50 }

Returns: 6723
800

800

70

80

90

{30, 40, 20, 10, 50 }

Returns: 1902
800

800

800

800

800

{10, 30, 40, 50, 70 }

Returns: 6576
799

707

613

790

1533

{420, 240, 130, 530, 300, 70, 110, 510, 470, 220, 160, 80, 440, 280, 380, 140, 430, 170, 30, 290, 410, 570, 20, 540, 350, 400, 550, 190, 320, 260, 520, 580, 250, 40, 560, 370, 90, 460, 210, 200, 450, 50, 390, 340, 150, 230, 120, 180, 270, 60 }

Returns: 0
800

800

800

800

1600

{ }

Returns: 2809

Statistics

Problem Statement for "FoxJumping"

Problem Statement

Definition

Constraints

Examples