TopCoder Statistics - Problem Statement

Problem Statement

One of the modes in the game "osu!" is called "catch the beat". In this mode, you control a character that catches falling fruit.

The game is played in the vertical plane. For simplicity, we will assume that both your character and all pieces of fruit are points in that plane.

You start the game at the coordinates (0, 0). Your character can only move along the x-axis. The maximum speed of your character is 1 unit of distance per second. For example, you need at least 3 seconds to move from (-2, 0) to (1, 0).

There are n pieces of fruit. The pieces are numbered 0 through n-1. For each i, fruit i starts at (x[i], y[i]). All pieces of fruit fall down with constant speed of 1 unit of distance per second. That is, a fruit currently located at (xf, yf) will move to (xf, yf-t) in t seconds. You will catch a fruit if the character is located at the same point as the fruit at some moment in time.

The initial coordinates x[] and y[] are generated using the following pseudocode:

x[0] = x0
for i = 1 to n-1:
    x[i] = (x[i-1] * a + b) % mod1

for i = 0 to n-1:
    x[i] = x[i] - offset

y[0] = y0
for i = 1 to n-1:
    y[i] = (y[i-1] * c + d) % mod2

(In the pseudocode, '%' represents the 'modulo' operator.)

You are given all the ints used in the above pseudocode. Return the maximum number of pieces of fruit you can catch.

Definition

Class:: CatchTheBeat
Method:: maxCatched
Parameters:: int, int, int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset)
(be sure your method is public)

Constraints

n will be between 1 and 500,000, inclusive.
mod1 and mod2 will be between 1 and 1,000,000,000, inclusive.
x0, a and b will be between 0 and (mod1 - 1), inclusive.
y0, c and d will be between 0 and (mod2 - 1), inclusive.
offset will be between 0 and 1,000,000,000, inclusive.

Examples

3

0

0

1

1

1

1

100

100

1

Returns: 2

There are 3 pieces of fruit. Their initial coordinates are (-1, 0), (0, 1), and (1, 2). Clearly you cannot catch fruit 0. You can catch the other two. One way of doing so: Wait at (0, 0) for 1 second. Catch fruit 1. Move to (1, 0) in 1 second. Immediately catch fruit 2.
1

0

1234

0

0

0

0

1000000000

1000000000

1000

Returns: 1

The only fruit is located at (-1000, 1234). We can go to (-1000, 0) and then wait for 234 seconds to catch it.
1

0

999

0

0

0

0

1000000000

1000000000

1000

Returns: 0

Now the only fruit is located at (-1000, 999). We can't catch it.
100

0

0

1

1

1

1

3

58585858

1

Returns: 66
500000

123456

0

1

0

1

1

1000000000

1000000000

0

Returns: 376544

The fruits are located in (123456, 0), (123456, 1), ..., (123456, 499999).
500000

0

0

0

0

0

0

1

1

0

Returns: 500000

In this case all the fruits start at (0, 0). Note that there can be more than one fruit at any position. We can catch all such fruit at the same time.
10

999999957

79

993948167

24597383

212151897

999940854

999999986

999940855

3404

Returns: 3

Watch out for integer overflow when generating the coordinates.
293

12815915

0

22628638

12788120

0

0

22648717

1

9274173

Returns: 0
37712

28743

17

17228

26018

572

204

65548

758

56848

Returns: 32
447

759978

229622

4919844

6033250

150353

285631

6706730

515007

5347689

Returns: 8
91324

75

0

95

83

0

0

119

1

109

Returns: 0
778

2

503574

1

1

491732

577850

3

709162

2

Returns: 778
8

35135

5958362

322064

610965

5714260

8115202

637754

8358910

560352

Returns: 6
97625

0

7513

1

3

29407

7755

4

33603

3

Returns: 24408
1

5259535

833214

7319021

12271749

242237

355472

13658128

854894

7247111

Returns: 0
799

1

80253

6

2

26490

44118

9

84990

5

Returns: 799
8468

5

1086994

1

5

4346748

1446108

10

4369359

2

Returns: 8468
293

12815915

0

22628638

12788120

0

0

22648717

1

9274173

Returns: 0
37712

28743

17

17228

26018

572

204

65548

758

56848

Returns: 32
447

759978

229622

4919844

6033250

150353

285631

6706730

515007

5347689

Returns: 8
91324

75

0

95

83

0

0

119

1

109

Returns: 0
778

2

503574

1

1

491732

577850

3

709162

2

Returns: 778
8

35135

5958362

322064

610965

5714260

8115202

637754

8358910

560352

Returns: 6
97625

0

7513

1

3

29407

7755

4

33603

3

Returns: 24408
1

5259535

833214

7319021

12271749

242237

355472

13658128

854894

7247111

Returns: 0
799

1

80253

6

2

26490

44118

9

84990

5

Returns: 799
55282

1658

1621411

7208

5925

544984

2289116

8010

4183623

1592

Returns: 21541
29

21

0

63

65

0

0

87

1

11

Returns: 2
511

0

0

0

0

0

0

1

1

0

Returns: 511
977

55955

6154335

59341

34159

2695241

1614904

68693

6653435

67466

Returns: 362
10

2377

43096524

2408

2952

27721571

1739595

3298

48596106

2732

Returns: 10
41833

5016387

3

6681507

5968581

6

0

9417757

7

7112608

Returns: 0
1

736

3

350

654

1

2

746

4

732

Returns: 0
44373

38059631

2807

20611346

38050409

9652

5362

55018071

17519

35523489

Returns: 5
5

57179

0

123734

77838

0

0

173062

1

64392

Returns: 0
236

31619

4310

30811

30916

4360

6744

55761

7286

12156

Returns: 8
5485

370

2

376

603

4

2

1120

8

125

Returns: 0
78

3958

3714596

2245

725

37928260

12471844

5628

57865424

5506

Returns: 78
772

0

12

0

2

15

2

4

25

2

Returns: 772
2304

686125

0

175609

187015

0

0

712325

4

546475

Returns: 0
1

276346

215516

90120

429334

780837

92001

481627

793358

8848

Returns: 0
6560

52

5546249

11

27

750880

670958

56

8863585

18

Returns: 6493
1

286528

38490859

52224

256861

24224803

31719029

352742

43787826

239604

Returns: 1
7

29648

0

45068

34613

0

0

70549

1

35632

Returns: 0
73

0

77

1

6

9

27

8

96

4

Returns: 55
40336

4

5157

0

1

3773

2520

6

8504

2

Returns: 40335
8

465798

1

467645

115464

1

0

498214

2

164801

Returns: 0
95707

161

0

144

85

0

0

172

1

19

Returns: 0
9

13671

73711

8111

3421

37187

20532

42914

78713

16139

Returns: 3
1133

4919

191

3597

1671

832

445

5088

902

3759

Returns: 18
4682

4

11

1

1

14

47

9

59

2

Returns: 522
854

449406

3750

115061

9331

176002

762463

735749

802258

375074

Returns: 38
14

1060728

6

3185076

5710317

3

0

5901949

7

2769786

Returns: 0
3937

0

127

0

0

33

216

1

231

0

Returns: 3937
5

0

6700

0

0

35611

5278

1

51125

0

Returns: 5
903

2020

124494

4320

4196

418353

444281

4949

620675

1307

Returns: 362
14

2647156

6922

2723440

5188083

88629

49103

7682723

116411

4297371

Returns: 0
556

33443350

0

1914615

29990941

2

2

49903040

3

43451268

Returns: 0
8133

0

4590

0

0

1283

5338

1

5791

0

Returns: 8133
59677

425052

70

240256

74561

54

72

502599

87

62198

Returns: 0
65

74912

27939

385795

16651

10241

5993

586022

36065

489615

Returns: 1
3482

229

42

64

247

57

39

631

85

347

Returns: 217
89705

0

0

0

0

0

0

1

1

0

Returns: 89705
603

852440

0

666788

587366

0

0

967831

1

589051

Returns: 0
231

624

931

369

496

348

321

659

941

580

Returns: 21
5076

0

566517

0

0

546338

692273

1

853235

0

Returns: 5076
7

1105

2

557

1550

3

1

2394

5

680

Returns: 0
8653

0

60111

6

4

110085

63950

7

166250

2

Returns: 8653
167

229272

2

98828

201060

2

2

233510

4

196432

Returns: 0
5496

3881776

295730

297829

2952300

589246

99465

6221365

654461

5995997

Returns: 29
1

0

0

0

0

0

0

1

1

0

Returns: 1
57

404

0

1072

4285

0

0

5022

1

3204

Returns: 0
970

29996

98

17787

23201

320

116

35678

992

13762

Returns: 6
4

0

56435

0

0

276892

37701

1

353651

0

Returns: 4
1

1159

2441

3867

2007

822

2374

4365

8824

1886

Returns: 1
14

324594

0

192601

406914

0

0

511287

1

404658

Returns: 0
22757

2653

68849178

4368

753

78332234

52069810

9490

90982076

2517

Returns: 14391
83

71282

0

3857

32749

0

0

71370

1

21288

Returns: 0
1

0

73

20

51

36

56

92

91

56

Returns: 1
1

1086

710

287

283

399

1406

1498

1541

96

Returns: 0
1

16

0

12

2

0

0

19

1

5

Returns: 0
57

0

75584

0

0

17423

39295

1

85453

0

Returns: 57
18

0

30804

0

0

284989

380139

1

473524

0

Returns: 18
2679

743

0

855

873

0

0

900

1

846

Returns: 0
8

47341

0

51390

11861

1

1

85875

3

35558

Returns: 0
50181

28

0

14

25

0

0

66

1

38

Returns: 0
7433

6651

2051

5983

766

7378

2939

8523

7642

2211

Returns: 127
1

93

15

572

95

5

28

861

49

88

Returns: 1
1

47363

1

29287

35766

2

1

49860

4

36875

Returns: 0
7

27

32766559

43

13

10102806

18511973

46

48221551

38

Returns: 7
6

44146

0

41511

44556

0

1

63990

2

27439

Returns: 0
1970

1

26079

9

15

15904

1965

16

29169

5

Returns: 232
43581

5624466

2492

2062424

4497289

2819

2445

8018388

4508

4169380

Returns: 16
14

37909

35920

6723

76953

11718

46841

77538

47356

54024

Returns: 2
6

3

0

1

3

1

4

5

7

1

Returns: 4
13780

0

204

0

0

168

18

1

366

0

Returns: 13780
48468

65

1355460

51

25

3309955

30004314

70

44369359

62

Returns: 47437
90293

443141538

0

247387582

511059894

3

5

522648717

8

7545947

Returns: 0
237712

28743

543

17228

26018

1000

1958

65548

2758

56848

Returns: 442
7447

41432978

229622

32179384

25744730

150353

285631

76706730

515007

48112059

Returns: 11
500000

1189

0

4343

5783

1

0

6119

2

3056

Returns: 0
6778

9

4223452

10

1

3120328

943654

13

8709162

0

Returns: 6778
38

7718339

25698412

5560662

2217483

4580520

10570562

8637754

48358910

6478640

Returns: 14
500000

20

206611

45

3

216909

114745

84

233603

31

Returns: 132111
9

106217167

303444

84874685

58118053

346973

470492

113658128

1854894

43828391

Returns: 1
2799

350

182593

880

238

33040

200778

1009

284990

588

Returns: 1083
500000

15818

2023417

11138

14505

5845252

4939250

68010

14183623

16652

Returns: 14437
329

266

8

341

354

6

9

887

10

66

Returns: 2
2511

0

2

0

1

2

9

2

10

1

Returns: 2511
9977

55955

5082570

59341

34159

5446381

1019479

68693

16653435

67466

Returns: 2029
50

49583

772038114

40688

13556

367894313

730681185

53298

848596106

16386

Returns: 50
241833

14434144

33

7947862

18981665

38

19

29417757

47

23924757

Returns: 1
5

3188

5

1914

2336

5

10

4746

14

2802

Returns: 0
244373

178204199

594085

160755914

93068480

166982

13616

355018071

917519

205776483

Returns: 35
25

2237145

2

4277222

2940740

2

0

9173062

3

2755008

Returns: 0
100236

300323

7716

264643

41293

11638

14138

355761

17286

192759

Returns: 97
500000

65

1355460

51

25

3309955

30004314

70

44369359

62

Returns: 416847
500000

443141538

0

247387582

511059894

3

5

522648717

8

7545947

Returns: 0
500000

28743

543

17228

26018

1000

1958

65548

2758

56848

Returns: 918
500000

41432978

229622

32179384

25744730

150353

285631

76706730

515007

48112059

Returns: 79
500000

1189

0

4343

5783

1

0

6119

2

3056

Returns: 0
500000

9

4223452

10

1

3120328

943654

13

8709162

0

Returns: 500000
500000

7718339

25698412

5560662

2217483

4580520

10570562

8637754

48358910

6478640

Returns: 2350
500000

20

206611

45

3

216909

114745

84

233603

31

Returns: 132111
500000

106217167

303444

84874685

58118053

346973

470492

113658128

1854894

43828391

Returns: 222
500000

350

182593

880

238

33040

200778

1009

284990

588

Returns: 20868
500000

15818

2023417

11138

14505

5845252

4939250

68010

14183623

16652

Returns: 14437
500000

266

8

341

354

6

9

887

10

66

Returns: 565
500000

0

2

0

1

2

9

2

10

1

Returns: 500000
500000

55955

5082570

59341

34159

5446381

1019479

68693

16653435

67466

Returns: 15549
500000

49583

772038114

40688

13556

367894313

730681185

53298

848596106

16386

Returns: 115867
500000

14434144

33

7947862

18981665

38

19

29417757

47

23924757

Returns: 1
500000

3188

5

1914

2336

5

10

4746

14

2802

Returns: 0
500000

178204199

594085

160755914

93068480

166982

13616

355018071

917519

205776483

Returns: 51
500000

2237145

2

4277222

2940740

2

0

9173062

3

2755008

Returns: 0
500000

300323

7716

264643

41293

11638

14138

355761

17286

192759

Returns: 215
500000

999999957

79

993948167

24597383

212151897

999940854

999999986

999940855

3404

Returns: 992
500000

12314

53542

532561259

95385721

25712847

248217541

1000000000

999999937

500000000

Returns: 992
500000

123456

21

32

51

93

15

100000075

1000000000

0

Returns: 3139
500000

0

34

34

325342

345

325

1000000000

1000000000

100000000

Returns: 512
500000

123456789

987654321

314159265

271828182

271828182

314159265

999999999

999999999

500000000

Returns: 988
500000

42

1234

13

17

12345

5432

100003

100019

50000

Returns: 1006
500000

0

234

1

1235

435

233

1000000000

1000000000

1

Returns: 265
500000

453

65

43

312

321

543

32323

41245

231

Returns: 360
500000

100

100

100

100

100

100

132134

543787

200000

Returns: 1753
500000

55

3333

55

321

54321

123

100007

1234557

50000

Returns: 3463
500000

123

321

33

44

5432

2345

100003

100019

50000

Returns: 1158

Statistics

Problem Statement for "CatchTheBeat"

Problem Statement

Definition

Constraints

Examples