TopCoder Statistics - Problem Statement

Problem Statement

You have just finished shopping at a supermarket and you are heading to the checkout. There are two lines available. The first line currently has len1 people, while the second line has len2 people. In each line, the cashier is just going to start checking out the first person.

The time to check out a person depends on the cashier's experience. For each pair of positive integers (p,k): the probability that a cashier with experience p will take exactly k seconds to check out any single person is given by the formula ((1/p) * (1 - 1/p)^(k-1)). The cashier in the first line has experience p1, and the cashier in the second line has experience p2.

You are given the ints len1, len2, p1, and p2. Compute the probability that standing in the first line is a strictly better choice than standing in the second line. More precisely, compute the probability that the last person currently standing in the first line will finish checking out strictly before the last person in the second line is done.

Definition

Class:: Queueing
Method:: probFirst
Parameters:: int, int, int, int
Returns:: double
Method signature:: double probFirst(int len1, int len2, int p1, int p2)
(be sure your method is public)

Notes

Your return value must have absolute or relative error less than 1e-9.
When evaluating the formula, assume that 0^0 = 1. Hence, the probability that a cashier with experience 1 checks out a person in 1 second is 1 * 0^0 = 1.

Constraints

len1,len2,p1,p2 will be between 1 and 1,000, inclusive.

Examples

1

2

2

1

Returns: 0.5

There are two lines. The first line has one person, the second line has two people. The first cashier has experience 2, and the second cashier has experience 1. The cashier with experience 1 will process each customer in exactly 1 second. So, we want to know the probability that the first cashier can finish processing the only customer in 1 second. This happens with probability 0.5.
1

3

3

7

Returns: 0.9835390946502058
3

1

7

3

Returns: 0.010973936899862834
12

34

56

78

Returns: 0.999996203228025
3

6

8

4

Returns: 0.5229465300297028
739

472

691

138

Returns: 0.0
604

259

303

513

Returns: 5.156019002856837E-6
167

303

405

276

Returns: 0.9872711986032693
677

533

589

380

Returns: 0.0
289

491

826

606

Returns: 0.9986698635516139
503

920

827

9

Returns: 0.0
941

472

631

322

Returns: 0.0
716

630

524

177

Returns: 0.0
202

993

860

212

Returns: 0.9947716769686621
136

295

21

889

Returns: 0.9999999999999124
171

159

980

649

Returns: 5.5763881128249234E-6
161

275

469

912

Returns: 0.99999999999262
522

714

953

105

Returns: 0.0
401

75

484

687

Returns: 0.0
21

797

201

774

Returns: 1.0000000000000324
568

828

853

831

Returns: 0.999999999950043
603

829

181

378

Returns: 0.9999999999987234
676

843

853

878

Returns: 0.9999993995623064
381

530

86

948

Returns: 0.9999999999996555
506

633

35

290

Returns: 1.0000000000005786
719

53

81

587

Returns: 5.539622936417099E-7
795

344

928

251

Returns: 0.0
494

240

202

225

Returns: 3.978928239980143E-16
634

395

438

997

Returns: 0.9999999590165183
728

120

161

96

Returns: 0.0
379

850

459

323

Returns: 0.999999999982268
273

334

745

608

Returns: 0.49354720082324993
251

883

316

597

Returns: 0.999999999991513
818

385

622

319

Returns: 0.0
732

57

300

274

Returns: 0.0
114

661

844

822

Returns: 0.9999999999958616
391

649

476

14

Returns: 0.0
975

518

389

482

Returns: 2.197535697132553E-15
577

896

970

221

Returns: 0.0
499

933

281

545

Returns: 1.0000000000021245
81

93

460

325

Returns: 0.0855509787418571
481

201

980

600

Returns: 0.0
893

156

76

456

Returns: 0.6982419607054006
558

375

261

987

Returns: 0.9999999999943484
530

865

139

63

Returns: 3.088658306369333E-8
826

587

323

485

Returns: 0.8846594700143373
939

513

695

551

Returns: 0.0
663

332

40

282

Returns: 1.0000000000013658
222

932

655

7

Returns: 0.0
14

587

968

508

Returns: 1.0000000000002003
629

341

891

416

Returns: 0.0
246

19

128

715

Returns: 2.537606664542101E-5
512

943

246

659

Returns: 1.000000000009465
471

698

9

411

Returns: 1.0
340

105

806

374

Returns: 0.0
416

278

371

665

Returns: 0.9895898921597295
265

291

944

863

Returns: 0.5187534397951143
494

969

36

494

Returns: 0.9999999999996897
373

495

430

958

Returns: 0.9999999999914425
678

221

865

322

Returns: 0.0
164

376

802

487

Returns: 0.9998525798054837
392

856

769

113

Returns: 0.0
305

333

114

125

Returns: 0.9887420979718222
964

89

511

961

Returns: 0.0
155

238

116

920

Returns: 1.000000000000271
109

824

830

18

Returns: 0.0
723

669

776

631

Returns: 5.567937304620946E-8
290

161

900

140

Returns: 0.0
714

359

699

278

Returns: 0.0
634

497

825

412

Returns: 0.0
213

856

56

361

Returns: 0.9999999999993059
365

271

319

198

Returns: 0.0
450

970

854

574

Returns: 1.0000000000057467
679

28

89

979

Returns: 1.2537106365010844E-6
370

454

959

743

Returns: 0.2358671730759477
230

235

509

61

Returns: 0.0
759

560

172

141

Returns: 0.0
449

33

948

286

Returns: 0.0
77

895

947

925

Returns: 0.999999999999773
248

573

391

20

Returns: 0.0
674

90

75

31

Returns: 0.0
64

49

337

663

Returns: 0.9830154836049493
983

307

549

857

Returns: 0.0
710

478

777

569

Returns: 0.0
902

607

130

48

Returns: 0.0
561

612

768

704

Returns: 0.5003304073836778
810

825

110

108

Returns: 0.500015281489512
159

205

410

318

Returns: 0.5017512614285871
308

418

133

98

Returns: 0.501458077875496
758

570

570

758

Returns: 0.49894666244252894
900

720

716

895

Returns: 0.4992542628448521
725

319

88

200

Returns: 0.4964599620884265
188

654

327

94

Returns: 0.5060741122802498
540

600

140

126

Returns: 0.5003728957288719
619

619

487

487

Returns: 0.49998833995753894
765

800

160

153

Returns: 0.5001187860962221
231

231

866

866

Returns: 0.49998926014680745
878

878

577

577

Returns: 0.49999173953801024
167

78

156

334

Returns: 0.4932942876162258
819

819

713

713

Returns: 0.49999307948847527
969

936

624

646

Returns: 0.49988708641567164
339

933

933

339

Returns: 0.5039333177195598
280

168

555

925

Returns: 0.49673802670347006
365

511

77

55

Returns: 0.5014322701000529
42

56

476

357

Returns: 0.5038414132363133
264

110

305

732

Returns: 0.49375247211661577
172

28

112

688

Returns: 0.4803841137989237
491

230

230

491

Returns: 0.4961225705006058
239

478

276

138

Returns: 0.5034869181664311
184

92

206

412

Returns: 0.4942816424606922
273

364

232

174

Returns: 0.5014875303718099
531

204

204

531

Returns: 0.4950932009954025
540

999

814

440

Returns: 0.5021126151479123
49

493

986

98

Returns: 0.5163181997306866
728

916

458

364

Returns: 0.5007444433198475
199

997

8

155

Returns: 1.0
98

980

49

450

Returns: 0.9999999999999343

Statistics

Problem Statement for "Queueing"

Problem Statement

Definition

Notes

Constraints

Examples