DynamiteBoxes
SRM 297 · 2006-04-06 · by igorsk
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.
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.
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.
1 3 Returns: 0.3125
1 4 Returns: 0.0625
1 5 Returns: 0.0
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DynamiteBoxes with a public method double getProbability(int height, int dangerousClusterSize) · 67 test cases · 2 s / 256 MB per case