Statistics

Problem Statement for "FallingBall"

Problem Statement

In a popular game, a ball is dropped from the top of a triangle of cells containing n rows. The ball keeps falling down row by row until it reaches the bottom of the triangle. In each row, the ball can fall either left or right. The first row contains one cell, the second contains two, and so on. The game looks like the following picture (where a cell is the space between two consecutive points in a row):

The rows are numbered from top to bottom starting from zero, and the cells in each row are numbered from left to right starting from zero. Note that row i will have i+1 cells numbered 0 to i, and if the ball is on cell k of row i, it will either fall left to cell k of row i+1, or right to cell k+1 of row i+1.

Given a String[] cells, containing a list of cells, and an int n, the number of rows in the triangle, return the number of paths in which the ball passes through all of the given cells. Each element of cells will be formatted "<row> <cell>" (quotes for clarity), where <row> is the cell's row, and <cell> is the cell's position within that row.

Definition

Class:
FallingBall
Method:
howMany
Parameters:
String[], int
Returns:
int
Method signature:
int howMany(String[] cells, int n)
(be sure your method is public)

Constraints

  • cells will have between 1 and 50 elements, inclusive.
  • n will be between 1 and 30, inclusive.
  • Each element of cells will be formatted " ", where and are each integers, with no extra leading zeros.
  • Each in cells will be between 0 and n-1, inclusive.
  • In each element of cells, will be between 0 and , inclusive.

Examples

  1. {"3 2","5 2"}

    7

    Returns: 6

    This example is shown in the picture above. There are 3 ways to reach the cell (3,2), then only one way to reach the second cell (5,2), and two more ways of reaching the bottom. That gives a total of 6 ways of passing through the cells.

  2. {"0 0","0 0"}

    30

    Returns: 536870912

    All the possible paths pass through the cell (0,0).

  3. {"0 0","29 0"}

    30

    Returns: 1

    There is only one way to reach the bottom-right cell.

  4. {"10 0","10 1"}

    15

    Returns: 0

    Two different cells in the same row can never be touched in the same path.

  5. {"0 0","4 0"}

    5

    Returns: 1

  6. {"2 2"}

    4

    Returns: 2

  7. {"13 7","7 5","19 11","19 11","14 7","11 6"}

    21

    Returns: 1680

  8. {"16 11","5 4"}

    18

    Returns: 3300

  9. {"5 3"}

    6

    Returns: 10

  10. {"0 0","3 0"}

    4

    Returns: 1

  11. {"0 0"}

    3

    Returns: 4

  12. {"11 5","8 4","11 5","11 5","8 4","7 3"}

    12

    Returns: 105

  13. {"12 9","11 8","10 8","6 6","11 8"}

    13

    Returns: 6

  14. {"14 7","15 7"}

    17

    Returns: 6864

  15. {"11 6","26 16","10 6","24 16","26 16"}

    27

    Returns: 60060

  16. {"11 11","7 7","11 11","9 9","10 10","1 1","11 11"}

    12

    Returns: 1

  17. {"3 0","13 4","12 3","12 3"}

    17

    Returns: 672

  18. {"2 0","14 5","14 5","9 2","14 5","13 5"}

    15

    Returns: 84

  19. {"3 1","4 1","2 0"}

    5

    Returns: 1

  20. {"21 16","1 0","19 16","21 16","21 16","16 15"}

    23

    Returns: 6

  21. {"6 4","25 14","23 14","13 9","9 7"}

    26

    Returns: 22680

  22. {"15 6","15 6","15 6"}

    16

    Returns: 5005

  23. {"12 0","14 2","16 2","16 2"}

    17

    Returns: 1

  24. {"14 2","9 0"}

    15

    Returns: 10

  25. {"21 7","20 6","11 4","21 7","1 0"}

    22

    Returns: 7560

  26. {"0 0"}

    10

    Returns: 512

  27. {"12 7","4 1","13 8","8 4","10 6","10 6","11 7"}

    14

    Returns: 16

  28. {"1 1","13 11","1 1"}

    15

    Returns: 132

  29. {"5 0","11 1","10 0"}

    16

    Returns: 16

  30. {"7 1"}

    16

    Returns: 1792

  31. {"5 5","6 6","6 6","5 5"}

    7

    Returns: 1

  32. {"5 0","5 0","3 0","4 0"}

    6

    Returns: 1

  33. {"13 3","6 1","11 2","14 3","12 2","10 2"}

    15

    Returns: 24

  34. {"16 5","16 5","15 4"}

    17

    Returns: 1365

  35. {"8 5","1 1"}

    12

    Returns: 280

  36. {"15 10","6 5","6 5","13 8","13 8"}

    16

    Returns: 210

  37. {"23 9","18 4","2 2"}

    24

    Returns: 120

  38. {"22 16","23 16","11 8"}

    24

    Returns: 27225

  39. {"11 7","6 6","6 6"}

    29

    Returns: 655360

  40. {"1 1","0 0"}

    2

    Returns: 1

  41. {"0 0"}

    30

    Returns: 536870912

  42. {"12 9","19 9","19 9","18 9","18 9"}

    20

    Returns: 220

  43. {"4 0","2 0","5 0"}

    7

    Returns: 2

  44. {"21 17","21 17","21 17","21 17"}

    22

    Returns: 5985

  45. {"16 4","22 6"}

    23

    Returns: 27300

  46. {"4 0","4 0"}

    16

    Returns: 2048

  47. {"1 1"}

    5

    Returns: 8

  48. {"0 0"}

    15

    Returns: 16384

  49. {"3 1","6 1","7 1","6 1","1 1","7 1","7 1","6 1"}

    9

    Returns: 2

  50. {"23 16","23 16","22 16"}

    24

    Returns: 74613

  51. {"27 4","27 4"}

    29

    Returns: 35100

  52. {"1 1","0 0","0 0","0 0"}

    2

    Returns: 1

  53. {"0 0"}

    1

    Returns: 1

  54. {"16 16"}

    20

    Returns: 8

  55. {"3 2","4 2"}

    5

    Returns: 3

  56. {"22 13","15 9"}

    23

    Returns: 175175

  57. {"0 0","3 1"}

    4

    Returns: 3

  58. {"14 7","1 1","1 1","10 7"}

    15

    Returns: 84

  59. {"8 3","28 9","28 9","27 8","27 8","29 10"}

    30

    Returns: 651168

  60. {"16 9","16 9"}

    17

    Returns: 11440

  61. {"14 13","16 13","14 13"}

    23

    Returns: 896

  62. {"0 0","15 0"}

    19

    Returns: 8

  63. {"10 6","17 13","13 9"}

    21

    Returns: 1680

  64. {"13 0","16 0","13 0"}

    17

    Returns: 1

  65. {"22 2","9 0"}

    30

    Returns: 9984

  66. {"13 7","12 6"}

    14

    Returns: 924

  67. {"20 5","22 6","21 6","23 7","23 7","22 6"}

    26

    Returns: 62016

  68. {"0 0"}

    8

    Returns: 128

  69. {"20 12","20 12","20 12","18 12","19 12","9 3","7 1"}

    21

    Returns: 7

  70. {"19 17","3 3"}

    25

    Returns: 3840

  71. {"7 0","7 0"}

    8

    Returns: 1

  72. {"13 12","26 17"}

    30

    Returns: 133848

  73. {"1 0"}

    4

    Returns: 4

  74. {"9 5","17 9"}

    18

    Returns: 8820

  75. {"13 8","13 8"}

    16

    Returns: 5148

  76. {"0 0","0 0"}

    3

    Returns: 4

  77. {"15 9","0 0"}

    26

    Returns: 5125120

  78. {"2 2"}

    3

    Returns: 1

  79. {"12 12","27 13","27 13","27 13","23 13"}

    28

    Returns: 11

  80. {"2 1"}

    4

    Returns: 4

  81. {"15 2","1 0"}

    22

    Returns: 5824

  82. {"6 4","13 6"}

    20

    Returns: 20160

  83. {"5 1","5 1"}

    6

    Returns: 5

  84. {"1 0","2 0"}

    3

    Returns: 1

  85. {"20 17","14 4","10 8","16 3","16 12","24 5","10 8","0 0","15 11","20 7","3 0","0 0","10 5","22 3","8 0","20 10","16 5"}

    25

    Returns: 0

  86. {"6 1","6 4","2 1","5 1","0 0","2 0","6 1","2 2","1 0"}

    7

    Returns: 0

  87. {"1 1","2 2","2 1","1 0","2 1"}

    3

    Returns: 0

  88. {"24 1","19 0","1 1","18 2","2 0","24 5","16 0","10 4","9 5","24 5","19 18","1 1","17 3"}

    29

    Returns: 0

  89. {"6 0","10 7","6 4","8 5","2 0","4 0","1 0","17 2","9 8","3 0","0 0","17 17","16 16","17 16","10 3","15 5","13 2","6 4","0 0","0 0","17 7","1 0","6 2","17 12","8 3","5 4","15 12","3 2","4 1","9 1","2 2","6 4","10 10","5 4","6 0","11 3","17 5","14 4","7 1","9 3","8 6","15 0","15 5","16 3","17 8"}

    19

    Returns: 0

  90. {"15 11","27 17","26 13","20 3","3 2","18 11","6 0","26 6","9 5","15 9","13 2","26 2","19 13","11 8","9 3","14 5","7 4","6 2","17 11","27 23","3 0","1 0","3 1","7 0","7 4","9 7","7 1","12 1","10 7","8 4","23 18","27 6","11 11","0 0","13 10","25 24","13 1","20 9","26 10","28 10","22 14","15 1","9 6","1 0","16 13","14 13","5 1"}

    29

    Returns: 0

  91. {"1 0","14 7","12 6","19 14","15 4","14 1","15 1","5 4"}

    21

    Returns: 0

  92. {"13 9","9 2","0 0","2 2","18 9","2 0","15 10","1 0","14 8","10 10","3 3","15 13","8 5","17 17","3 2","7 4","0 0","16 14","17 6","1 0","7 5","11 9","5 5","12 10","2 2","12 0","15 11","11 10","18 17","1 1","12 8","10 10","0 0","15 2","14 0","10 4","7 3","16 12"}

    19

    Returns: 0

  93. {"1 0","4 1","9 1","3 3","0 0","11 1","0 0","1 0","12 6","4 4","7 7","2 0","12 2","11 2","1 1","5 5","6 2","8 7","1 0","11 11","11 9","0 0","0 0","5 3","9 3","4 4","12 4"}

    13

    Returns: 0

  94. {"1 0","2 2","0 0","5 3","1 1","5 4","2 1","1 0","5 5","3 1","1 1","6 2","4 2","4 1","3 3","5 1","2 2","4 0","2 1","1 0","6 5","3 3","4 0","5 0","0 0","5 1","2 1","3 2","4 3","1 1","1 0","2 0","5 0","0 0"}

    7

    Returns: 0

  95. {"17 15","17 1","15 13","9 1","4 4","21 5","12 8","23 7","20 18","8 0","8 2","14 13","22 9","27 10","20 18","9 1","15 5","1 1","2 0","22 17","19 9","2 1","10 9","6 1","28 27","11 3","16 16","10 3","21 2","13 2","12 3","23 22","0 0"}

    29

    Returns: 0

  96. {"19 14","22 11","11 4","23 3","2 1","19 11","2 2","15 8","15 0","22 2","7 0","16 7","0 0","12 5","13 3"}

    25

    Returns: 0

  97. {"9 6","13 13","12 7","11 3","11 3","7 0"}

    21

    Returns: 0

  98. {"9 9","7 1","0 0","28 18","26 11","15 14","22 1","8 6","3 3","2 1","19 10","27 15","1 1","5 0","29 1","18 8","1 1","26 19","3 1","10 8","14 10","24 15","24 7","18 12","6 5","23 16","17 17","14 9","6 5","29 8","19 13","18 18","22 5","27 21","1 1","5 1","23 15","15 15"}

    30

    Returns: 0

  99. {"2 1","14 7","0 0","9 8","24 18","17 6","20 1","15 1","0 0","14 5","11 5","10 6","17 5","15 11","11 8","5 3","23 12","6 1","11 11","6 5","5 2","14 14","5 5","6 4","15 13","16 7","10 1","16 10","25 24","17 13","10 2","20 16","4 3","11 5","3 0","24 10","13 10","20 11","9 6","2 1"}

    27

    Returns: 0

  100. {"5 2","4 4","4 3","7 2","8 6","2 1","4 2","4 2","6 4","4 4","6 1","8 3","0 0","7 0","5 5","5 5","3 3","1 0","8 0","2 2","4 2","6 5","7 1","2 2","2 2","8 6","8 2","5 2","0 0","4 4","6 3","2 1","5 1","6 4","0 0","2 1","0 0","6 1"}

    9

    Returns: 0

  101. {"1 1","2 0","2 0","1 0","0 0","1 0","2 2"}

    3

    Returns: 0

  102. {"5 0","7 7","2 2","24 11"}

    25

    Returns: 0

  103. {"6 0","10 1","9 9","3 3","12 8","13 5","12 5","0 0","13 11","1 1","4 1","2 1","0 0","17 15","7 1","10 10","16 10","12 5","1 0","16 13","12 1","15 3","13 9","16 0","12 2","6 6","1 1","12 8","15 3","16 2","17 1","3 0","5 1","8 0","4 4","17 1","11 11","14 12","16 13","15 0","7 1","10 9","15 15","17 1","8 7","17 5"}

    18

    Returns: 0

  104. {"1 1","4 1","0 0","0 0","3 3","1 1","3 2"}

    6

    Returns: 0

  105. {"0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0"}

    30

    Returns: 536870912

  106. {"0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0", "0 0"}

    1

    Returns: 1

  107. {"29 29"}

    30

    Returns: 1

  108. {"29 0"}

    30

    Returns: 1

  109. {"28 0"}

    30

    Returns: 2

  110. {"28 28"}

    30

    Returns: 2

  111. {"28 28","28 28"}

    30

    Returns: 2

  112. {"10 0", "10 1" }

    15

    Returns: 0

  113. {"0 0", "1 0", "3 1", "6 3", "10 5", "15 7", "21 10", "28 14", "3 1", "10 5", "28 14", "0 0", "15 7", "10 5" }

    30

    Returns: 504000

  114. {"0 0", "29 0" }

    30

    Returns: 1

  115. {"3 2", "5 0" }

    7

    Returns: 0

  116. {"0 0", "21 12", "20 11", "21 12", "28 7" }

    30

    Returns: 0

  117. {"1 1", "29 14" }

    30

    Returns: 37442160

  118. {"10 0", "20 0", "15 3", "5 3", "3 2", "22 1", "5 3", "25 1" }

    30

    Returns: 0

  119. {"0 0", "29 0", "2 2", "3 3" }

    30

    Returns: 0

  120. {"0 0" }

    30

    Returns: 536870912

  121. {"29 14" }

    30

    Returns: 77558760

  122. {"1 1", "1 1" }

    30

    Returns: 268435456

  123. {"0 0", "1 0", "2 0", "3 0", "4 0", "5 0", "6 0", "7 0", "8 0", "9 0", "10 0", "11 0", "12 0", "13 0" }

    14

    Returns: 1

  124. {"0 0", "0 0", "20 10" }

    30

    Returns: 94595072

  125. {"6 0", "3 0" }

    30

    Returns: 8388608

  126. {"1 1", "2 2", "5 4", "6 3", "7 2", "15 2", "16 3", "25 5", "10 6", "13 4", "27 4" }

    29

    Returns: 0

  127. {"10 1", "9 0", "0 0" }

    30

    Returns: 524288

  128. {"29 15" }

    30

    Returns: 77558760

  129. {"5 2", "8 3", "5 2" }

    10

    Returns: 60

  130. {"10 1", "11 0" }

    30

    Returns: 0

  131. {"29 1", "1 1" }

    30

    Returns: 1

  132. {"0 0", "0 0" }

    30

    Returns: 536870912

  133. {"5 2", "3 2" }

    7

    Returns: 6

  134. {"10 1", "1 1", "2 1" }

    30

    Returns: 524288

  135. {"0 0", "3 1", "4 2", "10 8", "10 9", "16 8" }

    24

    Returns: 0

  136. {"1 0", "29 14" }

    30

    Returns: 40116600

  137. {"29 2", "3 1" }

    30

    Returns: 78

  138. {"29 15", "0 0" }

    30

    Returns: 77558760

  139. {"29 0", "0 0" }

    30

    Returns: 1

  140. {"0 0", "29 15" }

    30

    Returns: 77558760

  141. {"5 1", "3 2", "6 4" }

    8

    Returns: 0

  142. {"10 0", "2 0" }

    20

    Returns: 512

  143. {"9 1", "11 1" }

    20

    Returns: 2304

  144. {"0 0", "4 2" }

    14

    Returns: 3072

  145. {"20 0", "10 10" }

    30

    Returns: 0

  146. {"3 1", "5 2", "9 4", "8 4" }

    11

    Returns: 36

  147. {"25 0", "26 1" }

    30

    Returns: 8

  148. {"1 1", "0 0", "3 3", "2 2" }

    10

    Returns: 64

  149. {"1 1", "0 0" }

    30

    Returns: 268435456

  150. {"5 2", "0 0" }

    7

    Returns: 20

  151. {"1 1", "1 1" }

    2

    Returns: 1

  152. {"29 24", "29 24", "2 1" }

    30

    Returns: 35100

  153. {"25 0", "26 1", "28 3" }

    30

    Returns: 2

  154. {"0 0", "1 1", "29 14" }

    30

    Returns: 37442160

  155. {"10 8", "11 8" }

    13

    Returns: 90

  156. {"1 1", "1 1" }

    7

    Returns: 32

  157. {"1 1", "2 0" }

    20

    Returns: 0

  158. {"25 25", "25 25" }

    30

    Returns: 16

  159. {"0 0", "20 10", "10 5", "5 3" }

    30

    Returns: 12902400

  160. {"0 0", "1 0", "2 1", "3 1", "4 2", "5 2", "6 3" }

    11

    Returns: 16

  161. {"0 0", "29 10", "2 2", "3 3", "5 5" }

    30

    Returns: 42504

  162. {"2 2", "3 1", "4 1" }

    5

    Returns: 0

  163. {"29 10" }

    30

    Returns: 20030010

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: