TopCoder Statistics - Problem Statement

Problem Statement

Taro is standing on a rectangular island. The island is divided into width x height cells. The coordinate system is introduced so that cell in the bottom left corner has coordinates (0, 0) and cell in the top right corner has coordinates (width-1, height-1). Initially he is standing on cell (x, y).

He decides to take a random walk. Each step consists of walking one cell in a randomly chosen direction. Only the four cardinal directions are allowed, and each direction has an equal probability of being chosen on each step. If he steps off the island, he will fall into the sea. Taro's walk will consist of exactly steps steps, unless he falls into the sea before he finishes walking.

Return the probability that he will still be standing on the island after steps steps.

Definition

Class:: RectangularIsland
Method:: theProbablity
Parameters:: int, int, int, int, int
Returns:: double
Method signature:: double theProbablity(int width, int height, int x, int y, int steps)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

width will be between 1 and 1000, inclusive.
height will be between 1 and 1000, inclusive.
x will be between 0 and width - 1, inclusive.
y will be between 0 and height - 1, inclusive.
steps will be between 1 and 5000, inclusive.

Examples

5

8

4

3

1

Returns: 0.75

If Taro chooses up, down or left, he will remain on the island.
5

8

4

7

1

Returns: 0.5

If Taro chooses down or left, he will remain on the island.
2

2

0

1

5

Returns: 0.03125

From any cell, the probability of remaining after one step is 1/2, so the answer is (1/2)^5.
58

85

47

74

1000

Returns: 0.13056659769966347
1000

1000

123

456

5000

Returns: 0.9868611148475199
1000

1000

0

0

5000

Returns: 2.5457154130206994E-4
1000

1000

500

500

400

Returns: 0.9999999999999997
1

1

0

0

1

Returns: 0.0
1000

1

500

0

10

Returns: 9.765625E-4
1000

1000

0

500

200

Returns: 0.07954024919144759
1000

1000

933

743

1263

Returns: 0.992328172010765
1000

1000

529

700

509

Returns: 1.0000000000000004
1000

1000

752

256

2257

Returns: 0.9999999999998329
1000

1000

119

711

3352

Returns: 0.9966239886815323
1000

1000

843

705

4109

Returns: 0.9994676469071451
1000

1000

393

330

2367

Returns: 0.9999999999999993
1000

1000

169

932

1918

Returns: 0.9718887306061241
1000

1000

847

972

2869

Returns: 0.5401908137697314
1000

1000

980

223

3550

Returns: 0.36498126477364073
1000

1000

592

164

1170

Returns: 0.9999999999916024
428

552

282

192

636

Returns: 0.9999999999999998
945

921

80

157

3485

Returns: 0.9475182980942144
302

364

28

60

1877

Returns: 0.6256014014996005
930

432

517

115

492

Returns: 0.9999999999998891
345

191

24

171

1630

Returns: 0.31945650657732716
728

31

430

23

2335

Returns: 0.003232747403773143
761

105

131

50

257

Returns: 0.9999923373437386
573

933

32

907

4510

Returns: 0.21332364996646314
406

120

313

89

328

Returns: 0.984494129924734
498

720

410

516

3650

Returns: 0.9605862955349012
1000

1000

211

41

3603

Returns: 0.6775655681323534
1000

1000

77

889

2105

Returns: 0.9831805683435004
1000

1000

640

387

661

Returns: 1.0000000000000002
1000

1000

493

618

1531

Returns: 1.0000000000000004
1000

1000

389

549

3503

Returns: 1.000000000000001
1000

1000

659

294

219

Returns: 1.0
1000

1000

459

990

2494

Returns: 0.2229381467972777
1000

1000

892

505

1116

Returns: 0.9999952238103218
1000

1000

500

372

4718

Returns: 0.9999999999999848
1000

1000

557

598

24

Returns: 1.0
874

940

261

888

1945

Returns: 0.9045494518987042
523

903

17

855

4931

Returns: 0.188558885671433
588

472

313

234

2156

Returns: 0.9999999999988137
124

483

30

98

2965

Returns: 0.558903101223208
20

740

8

580

217

Returns: 0.36752603926123806
317

872

247

86

3594

Returns: 0.8651169296607703
805

846

25

778

1375

Returns: 0.672065126401078
645

912

78

807

4089

Returns: 0.9007817623318114
389

465

158

57

3285

Returns: 0.8475037333548828
733

500

672

64

844

Returns: 0.9954707413695709
999

999

1

1

4444

Returns: 0.0011451282783235155
1000

1000

500

500

5000

Returns: 1.0000000000000007
1000

1000

998

996

5000

Returns: 0.0020341315354996184
1000

1000

10

999

5000

Returns: 0.0027780520955662893
1000

950

998

946

5000

Returns: 0.0020341315354996184
999

999

555

555

5000

Returns: 1.0000000000000007
1000

1000

997

3

5000

Returns: 0.0030501809691999946
1000

1000

100

10

5000

Returns: 0.16656236921154452
1000

1000

1

1

5000

Returns: 0.001017879094968067
33

23

5

21

454

Returns: 0.011893831392275516
1000

999

555

555

4999

Returns: 1.0000000000000009
1000

1000

250

345

5000

Returns: 0.9999994853267649
1000

1000

5

5

5000

Returns: 0.009121960396294258
1000

1000

808

986

4865

Returns: 0.22344601449905835
1000

1000

789

945

5000

Returns: 0.7286269712424578

Statistics

Problem Statement for "RectangularIsland"

Problem Statement

Definition

Notes

Constraints

Examples