Statistics

Problem Statement for "DynamiteBoxes"

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

    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.

  2. 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.

  3. 1

    3

    Returns: 0.3125

  4. 1

    4

    Returns: 0.0625

  5. 1

    5

    Returns: 0.0

  6. 2

    1

    Returns: 0.99609375

  7. 2

    2

    Returns: 0.86328125

  8. 2

    3

    Returns: 0.69921875

  9. 2

    4

    Returns: 0.51171875

  10. 3

    6

    Returns: 0.439697265625

  11. 3

    7

    Returns: 0.302978515625

  12. 10

    15

    Returns: 0.2844286304543857

  13. 30

    28

    Returns: 0.1650298245829558

  14. 24

    9

    Returns: 0.9733089907984582

  15. 25

    15

    Returns: 0.6903910319928076

  16. 30

    121

    Returns: 0.0

  17. 30

    1

    Returns: 1.0

  18. 2

    1

    Returns: 0.99609375

  19. 6

    24

    Returns: 5.9604644775390625E-8

  20. 3

    3

    Returns: 0.859130859375

  21. 10

    5

    Returns: 0.9774791877916869

  22. 10

    12

    Returns: 0.47678915627147944

  23. 10

    20

    Returns: 0.10997145969122357

  24. 10

    30

    Returns: 8.332200595759787E-4

  25. 1

    121

    Returns: 0.0

  26. 15

    18

    Returns: 0.29437221377808725

  27. 30

    1

    Returns: 1.0

  28. 30

    10

    Returns: 0.9762525388430822

  29. 27

    17

    Returns: 0.5960931387368702

  30. 5

    6

    Returns: 0.7011480331420898

  31. 9

    2

    Returns: 0.9999505102314288

  32. 9

    4

    Returns: 0.9897641579882475

  33. 8

    7

    Returns: 0.8076985066290945

  34. 8

    11

    Returns: 0.44327822723425925

  35. 8

    13

    Returns: 0.3057946553453803

  36. 8

    15

    Returns: 0.20625532558187842

  37. 8

    17

    Returns: 0.1319829821586609

  38. 8

    18

    Returns: 0.10094104520976543

  39. 15

    51

    Returns: 1.4391727479884375E-8

  40. 30

    30

    Returns: 0.12479774445489643

  41. 29

    29

    Returns: 0.13733040320492726

  42. 11

    39

    Returns: 6.946203257029993E-8

  43. 24

    5

    Returns: 0.9999374345466958

  44. 5

    1

    Returns: 0.9999990463256836

  45. 5

    2

    Returns: 0.9954118728637695

  46. 5

    3

    Returns: 0.9694929122924805

  47. 5

    4

    Returns: 0.9065961837768555

  48. 5

    5

    Returns: 0.8157243728637695

  49. 5

    6

    Returns: 0.7011480331420898

  50. 5

    7

    Returns: 0.5835123062133789

  51. 5

    8

    Returns: 0.4780397415161133

  52. 5

    9

    Returns: 0.3855609893798828

  53. 5

    10

    Returns: 0.30373191833496094

  54. 5

    11

    Returns: 0.22811126708984375

  55. 5

    12

    Returns: 0.15743255615234375

  56. 5

    13

    Returns: 0.09514522552490234

  57. 5

    14

    Returns: 0.047659873962402344

  58. 5

    15

    Returns: 0.018891334533691406

  59. 5

    16

    Returns: 0.005722999572753906

  60. 5

    17

    Returns: 0.0012807846069335938

  61. 5

    18

    Returns: 2.0122528076171875E-4

  62. 5

    19

    Returns: 2.002716064453125E-5

  63. 5

    20

    Returns: 9.5367431640625E-7

  64. 30

    120

    Returns: 7.52316384526264E-37

  65. 30

    60

    Returns: 0.0012988848638603332

  66. 30

    30

    Returns: 0.12479774445489643

  67. 29

    19

    Returns: 0.5071246252017507

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.
This problem was used for: