TopCoder Statistics - Problem Statement

Problem Statement

We have balls of K different colors. The colors are numbered 0 through K-1, and the number of balls of color i is X[i]. We want to divide the balls into as few packages as possible. Each package must contain between 1 and K balls, inclusive. Additionally, each package must be either a "normal set" (all balls in the package have the same color), or a "variety set" (no two balls have the same color).
You are given the int K. You are also given ints A, B, C, and D. Use these to generate the array X using the following pseudocode:

X[0] = A
for i = 1 to K-1:
    X[i] = (X[i-1] * B + C) % D + 1

Compute and return the smallest possible number of packages.

Definition

Class:: PackingBallsDiv1
Method:: minPacks
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int minPacks(int K, int A, int B, int C, int D)
(be sure your method is public)

Notes

You can assume that the answer will fit into a signed 32-bit integer.

Constraints

K will be between 1 and 100,000, inclusive.
B, C and D will be between 1 and 1,000,000,000, inclusive.
A will be between 1 and D, inclusive.

Examples

3

4

2

5

6

Returns: 4

There are three colors of balls. Using the pseudocode in the problem statement, we can compute that X[0]=4, X[1]=2, and X[2]=4. As there are 10 balls and we can only put at most 3 into each package, we need at least 4 packages. One possible solution with 4 packages is {0,1,2}, {0,0}, {0,1}, and {2,2,2}. (That is, the first package contains one ball of each color, the second package contains two balls of color 0, and so on.)
1

58

23

39

93

Returns: 58

All the balls have the same color, and each package can only contain one ball. Thus, the number of packages is the same as the number of balls.
23

10988

5573

4384

100007

Returns: 47743
100000

123456789

234567890

345678901

1000000000

Returns: 331988732

Watch out for integer overflow when generating X.
7

1

2

3

10

Returns: 6
98767

251470493

480455801

951252597

926813327

Returns: 462771730
99052

444166754

624944751

919286231

985340641

Returns: 492977964
27

1

48

7

20

Returns: 16
36

26

32

4

30

Returns: 29
21

24

22

22

43

Returns: 25
36

13

16

35

31

Returns: 27
32

31

7

3

47

Returns: 39
5

26

19

11

34

Returns: 21
31

7

27

49

37

Returns: 28
14

104563326

668440963

226153708

423439112

Returns: 177443175
13

521442917

148558074

507183992

536070243

Returns: 280865176
31

979913795

814324545

194354308

986989638

Returns: 337434349
17

48160033

862427138

401615360

221893665

Returns: 108852366
44

587079029

145914576

21214306

774284254

Returns: 375516580
23

159806751

135240513

888341047

214446033

Returns: 109836193
16

35514762

952775469

171349755

335835435

Returns: 171608945
99491

20

251588215

451096778

79

Returns: 79
92553

9

370487255

629638464

17

Returns: 9
1026

2

142476470

419125693

32

Returns: 26
13751

51

91873631

466871330

92

Returns: 92
45436

9

477613935

320716791

16

Returns: 15
34730

8

729340259

711151032

31

Returns: 29
7352

25

923244187

249506546

84

Returns: 82
49786

139534595

489084386

581304035

792664302

Returns: 396619723
70082

520509350

627837732

466908491

962137397

Returns: 482237157
99403

848004375

394554335

974306805

960464607

Returns: 480015690
26231

323483867

893115928

110952423

451489190

Returns: 225854313
13733

613701921

253201673

721759661

733019738

Returns: 367283436
36068

9927974

234430622

330178007

353209272

Returns: 176230186
59704

117914770

499278540

677931742

369638787

Returns: 184948520
90799

858324559

899110833

125169351

916684842

Returns: 459037619
95702

319365462

631352621

368391001

927176835

Returns: 468611914
92223

567367330

266300017

295942084

906127506

Returns: 453033279
96966

327981394

794506723

698376990

900474609

Returns: 450201134
98385

401933010

784546852

509060284

913305259

Returns: 456731536
99703

165041745

151531055

757341912

950595580

Returns: 476898526
97364

562197501

816681317

421688200

928910375

Returns: 463546891
99166

104706251

333916106

339706383

980887699

Returns: 490777933
93519

485431044

959586916

571119413

905397197

Returns: 453992309
99497

330885191

262069039

789247046

931550584

Returns: 466416080
92006

311038857

829072678

698992535

936977791

Returns: 467955106
93738

759689197

890346460

592761289

924547904

Returns: 462626300
93005

602472521

875328112

268570801

979984996

Returns: 491006690
90200

689476936

560207448

931025089

951494377

Returns: 476942553
98925

727707914

480779065

69114402

994591612

Returns: 498052551
92161

568399886

956610461

624102086

955446244

Returns: 476941101
90107

152403308

865068313

511223941

906099509

Returns: 453861148
93794

491650667

162899831

498312525

925925139

Returns: 463620376
99526

648046304

326045164

604708358

952434695

Returns: 475745131
97195

146478208

2402202

491911744

987199616

Returns: 494511429
91284

581139205

306562424

795945739

938875044

Returns: 468886848
99963

4512782

6994545

621783390

937466871

Returns: 469384563
99879

185193995

859919017

479428496

952907378

Returns: 475184453
91641

347439275

161544349

677966041

984796195

Returns: 491880024
99597

775123478

948510196

660412841

949728867

Returns: 476324489
99278

795804985

73350247

975183553

963185211

Returns: 482484027
90391

719886058

744156817

750374308

966883153

Returns: 481917501
94379

463301686

759391009

656426230

929134297

Returns: 463675222
92388

967104559

293548043

876369849

978562704

Returns: 487365142
90462

335507002

641474757

837623936

948592654

Returns: 474851705
95669

270889827

351428486

118685892

933392055

Returns: 465868337
99714

468183988

255373464

397510974

978411950

Returns: 488412801
99388

903551441

655086257

750293519

976763648

Returns: 488808780
97055

775074242

868692674

391367501

987533766

Returns: 493305133
95299

763035757

343232910

15135385

933785974

Returns: 467255205
97302

736142872

276358674

34873416

944170102

Returns: 470527423
99568

717681126

998733990

684000162

952649384

Returns: 476802502
99941

171445960

992462617

180316931

903526745

Returns: 451666261
99277

945179141

79397033

326961247

988370657

Returns: 493653178
99026

10203108

7385612

775933140

935933356

Returns: 469450165
96490

491443446

639043990

599985193

964744983

Returns: 483001309
98343

683443038

678265259

50021087

983844802

Returns: 489271266
98066

94622195

775900485

747403459

965294203

Returns: 483196564
99962

507303041

327298220

743771517

912856732

Returns: 456429059
98877

94517126

842949961

505867904

910955079

Returns: 454544656
100000

1000000000

1

999999999

1000000000

Returns: 1000000000
100000

1

1

1000000000

1000000000

Returns: 100000
100000

123456789

234567890

345678933

1000000000

Returns: 883915480
99997

869978151

194292048

793365716

954791644

Returns: 478858711
5

5

2

4

6

Returns: 5
3

1

3

3

5

Returns: 3
100000

987654321

98765432

987654321

987654321

Returns: 492008309
100000

1

1

1

1000000000

Returns: 149999
100000

2343

345666

3454545

45454545

Returns: 22821773
100000

1

31337

65537

1000000000

Returns: 499675441
100000

1

1

1000000

899999999

Returns: 449200000
100000

131

234567890

345678901

555

Returns: 447
61724

9352566

4685810

70454754

77100289

Returns: 38608866
10000

6401

19170

15725

11479

Returns: 10165
100000

63472

27348

72348

100000

Returns: 99959
100000

11571

192

4304

20148017

Returns: 10134848
100000

42

26

2013

987654321

Returns: 493263810
23

10999

5573

4384

100007

Returns: 61598
100000

11111111

22222223

21212212

999999997

Returns: 500223525
3

2

10

2

10

Returns: 3
3

1

10

200

100

Returns: 8
100000

1

2

2

3

Returns: 2
50

1234567

654335

457854

68588611

Returns: 38001552
4

2

1

1

3

Returns: 3
7775

208827025

628894325

731963982

822804784

Returns: 411644829
100000

1

1

1

10000

Returns: 9999
100

1

1

1

3

Returns: 3
3

5

1

3

8

Returns: 4
20

1

4

62

63

Returns: 10
100000

1

1

1000000

1000000

Returns: 100000
100000

32115645

32132132

8654561

321321323

Returns: 160932381
50

1

1

1

5

Returns: 5
3

3

8

10

3

Returns: 3
4

10

4

10

15

Returns: 6
100000

1234678

238967890

310678901

900000000

Returns: 519779590
100000

79

258056174

111268468

99

Returns: 97
100000

23456789

34567890

45678901

100000007

Returns: 50108197
100000

1

1

2

2

Returns: 2
100000

12011201

78978977

35775377

39586731

Returns: 19777012
100000

12421596

12847152

35767847

23562363

Returns: 11804908
100000

7

13

53

10000009

Returns: 5051778
432

1234

35

634

43623

Returns: 22974
5

5

10

1

10000

Returns: 1605

Statistics

Problem Statement for "PackingBallsDiv1"

Problem Statement

Definition

Notes

Constraints

Examples