DynamiteBoxes | Topcoder Archive

Problem Statement

Consider a 2 x 2 x height stack of cube-shaped boxes of identical size. The stack has height levels of boxes, each level containing 4 boxes arranged in a 2 x 2 pattern. Each box has a 50% probability of containing dynamite and a 50% probability of being empty. Two dynamite-filled boxes, A and B, are in the same dynamite cluster if:

a face of A touches a face of B
OR a face of A touches a face of some box C, and C is in the same dynamite cluster as B.

A stack is dangerous if it contains a dynamite cluster that contains at least dangerousClusterSize boxes. Given height and dangerousClusterSize, compute the probability that the stack is dangerous.

Definition

Class:: DynamiteBoxes
Method:: getProbability
Parameters:: int, int
Returns:: double
Method signature:: double getProbability(int height, int dangerousClusterSize)
(be sure your method is public)

Notes

Your answer must be within 1E-9 absolute or relative error.

Constraints

height will be between 1 and 30, inclusive.
dangerousClusterSize will be between 1 and 121, inclusive.

Examples

```
1
```
```
1
```
```
Returns: 0.9375
```
Here, any stack that contains a dynamite-filled box is dangerous. There are 16 possible 2 x 2 x 1 stacks, each occurring with the same probability. Only one of the possible stacks is not dangerous - the stack with no dynamite-filled boxes. So, the answer is 15/16 = 0.9375.
```
1
```
```
2
```
```
Returns: 0.5625
```
In this example, stacks that contain dynamite-filled boxes that don't touch any other dynamite-filled boxes are not dangerous. There are 7 such stacks: 1 with no dynamite-filled boxes, 4 with a single dynamite-filled box, and 2 with two dynamite-filled boxes each placed diagonally so that they don't touch each other. The answer then is 1 - 7/16 = 0.5625.
```
2
```
```
4
```
```
Returns: 0.51171875
```
```
3
```
```
3
```
```
Returns: 0.859130859375
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.