Statistics

Problem Statement for "GameOfLifeDivOne"

Problem Statement

Cat Taro and Rabbit Hanako invented a new variation of "Game Of Life".

N cells are arranged around a circle. The cells are numbered from 0 to N-1. For each i between 0 and N-2, inclusive, the i-th cell and the (i+1)-th cell are adjacent to each other. The (N-1)-th cell and the 0-th cell are adjacent to each other. Each cell has exactly two adjacent cells. Each cell has a state: "live" or "die".

Taro and Hanako can decide the states of the cells at time 0. For time t > 0, the states are determined as follows:
  • Consider three cells: the i-th cell and the two cells that are adjacent to the i-th cell.
  • If at least two of the three cells are "live" at time t-1, the state of the i-th cell at time t will be "live".
  • If at least two of the three cells are "die" at time t-1, the state of the i-th cell at time t will be "die".
You are given a String init. The number of cells in the game (N) is equal to the number of characters in init. The i-th character of init represents the state they assign to the i-th cell at time 0. '1' means "live", '0' means "die", and '?' means undecided. Return the number of ways they can assign states to the undecided cells such that at least K cells will be in the "live" state at time T.

Definition

Class:
GameOfLifeDivOne
Method:
theCount
Parameters:
String, int, int
Returns:
long
Method signature:
long theCount(String init, int T, int K)
(be sure your method is public)

Constraints

  • init will contain between 3 and 50 characters, inclusive.
  • Each character in init will be '0' (zero), '1' (one) or '?'.
  • T will be between 0 and 1,000, inclusive.
  • K will be between 0 and the number of characters in init, inclusive.

Examples

  1. "0?1"

    1

    1

    Returns: 1

    There are two ways to replace '?' with '0' and '1': "001" and "011". If the state is "001" at time 0, the state will be "000" at time 1. No cell is in the "live" state. If the state is "011" at time 0, the state will be "111" at time 1. 3 cells are in the "live" state. Only the second one satisfies the condition, so the answer is 1.

  2. "?????????"

    0

    1

    Returns: 511

    There are 512 ways to replace '?' cells with '0' or '1'. All of them except "000000000" satisfy the condition.

  3. "??0???????"

    58

    6

    Returns: 151

  4. "?????????1"

    47

    3

    Returns: 453

  5. "??01??110?"

    100

    3

    Returns: 29

  6. "??????????????????????????????????????????????????"

    1000

    0

    Returns: 1125899906842624

  7. "010101"

    10

    4

    Returns: 0

  8. "10101"

    2

    5

    Returns: 1

  9. "?????????1???0???1??1??????0??????0??0????1???????"

    12

    40

    Returns: 31577324313

  10. "???"

    1

    0

    Returns: 8

  11. "??????????"

    99

    3

    Returns: 823

  12. "???"

    0

    2

    Returns: 4

  13. "???"

    0

    1

    Returns: 7

  14. "???"

    1000

    3

    Returns: 4

  15. "???"

    1000

    3

    Returns: 4

  16. "???"

    607

    1

    Returns: 4

  17. "???"

    298

    0

    Returns: 8

  18. "???"

    17

    0

    Returns: 8

  19. "???"

    8

    3

    Returns: 4

  20. "???"

    1

    3

    Returns: 4

  21. "???"

    7

    3

    Returns: 4

  22. "?????????????????????????????????????????????????"

    0

    23

    Returns: 403023636746956

  23. "?????????????????????????????????????????????????"

    0

    5

    Returns: 562949953189786

  24. "?????????????????????????????????????????????????"

    1000

    26

    Returns: 247145497139164

  25. "?????????????????????????????????????????????????"

    1000

    8

    Returns: 561082903169202

  26. "?????????????????????????????????????????????????"

    862

    13

    Returns: 545777839940362

  27. "?????????????????????????????????????????????????"

    895

    37

    Returns: 17172113480950

  28. "?????????????????????????????????????????????????"

    2

    22

    Returns: 385287847999258

  29. "?????????????????????????????????????????????????"

    20

    28

    Returns: 181542024838938

  30. "?????????????????????????????????????????????????"

    17

    6

    Returns: 562358668473190

  31. "?????????????????????????????????????????????????"

    16

    45

    Returns: 303377597195

  32. "??????????????????????????????????????????????????"

    0

    3

    Returns: 1125899906841348

  33. "??????????????????????????????????????????????????"

    0

    15

    Returns: 1124435014542268

  34. "??????????????????????????????????????????????????"

    1000

    5

    Returns: 1125396592633103

  35. "??????????????????????????????????????????????????"

    1000

    31

    Returns: 226224770913436

  36. "??????????????????????????????????????????????????"

    786

    0

    Returns: 1125899906842624

  37. "??????????????????????????????????????????????????"

    236

    6

    Returns: 1124912962780553

  38. "??????????????????????????????????????????????????"

    2

    22

    Returns: 799951559419648

  39. "??????????????????????????????????????????????????"

    21

    21

    Returns: 848229259540648

  40. "??????????????????????????????????????????????????"

    9

    37

    Returns: 42829121309326

  41. "??????????????????????????????????????????????????"

    11

    32

    Returns: 180812122173236

  42. "?????1??111???????11??????????11?????1???????????1"

    0

    10

    Returns: 1099511627776

  43. "?11?111111111111??1?111?1111?1111111?11111?1111?11"

    0

    18

    Returns: 1024

  44. "???0??0???0??0??????????0??????????????0??????0???"

    160

    13

    Returns: 7601054837275

  45. "?1?111111??1??11????11111?11?1?11?111?11111111???1"

    273

    28

    Returns: 262144

  46. "??1???111??11??11??1??1?1???11??1??11????11??1????"

    16

    27

    Returns: 2141616800

  47. "??????????11?11?1?111??1??1?1?1???1???111?1?????11"

    21

    23

    Returns: 2147154784

  48. "??0000?????0??0000000?00???00?000000?000?00?0000?0"

    5

    20

    Returns: 0

  49. "0000000000000000?00?000?00000000000000000000000000"

    15

    7

    Returns: 0

  50. "???????????????????????????????1??????0???????0???"

    0

    32

    Returns: 2813768603466

  51. "??????1???????????10???????0??????????????1???1??0"

    0

    9

    Returns: 8796092885510

  52. "0??1010?01?10?0?01?10?01??010?01?1010?01?1???10101"

    408

    36

    Returns: 10519

  53. "0?0?0???0???0??1??????????010??1???10?0????101????"

    677

    47

    Returns: 943319

  54. "0?????01?101?10?0?010??101??010?0?0?????0?01???101"

    11

    46

    Returns: 7097

  55. "?1????0??1????????0???01????01??0101??0?0??1?1???1"

    24

    1

    Returns: 8589662593

  56. "?????10?0?0?0101???1???1?1?1??0??101?1?????1??01??"

    10

    40

    Returns: 45611576

  57. "??0??????1???1??????????????010???0??1????????????"

    3

    29

    Returns: 1172949674850

  58. "?111001010??100???10????00?11??1?010?011??0??10??0"

    0

    13

    Returns: 2097152

  59. "0101010101001?101010???1010010101010101010101?1011"

    0

    40

    Returns: 0

  60. "????1???10?0?1????1????1??????1????01????????0?0??"

    740

    40

    Returns: 4873914135

  61. "0100010110101?0101001010110101101010?010?010101?11"

    499

    42

    Returns: 0

  62. "?000?0??000???0??1?1110?0??????????0?00???0?000?0?"

    15

    31

    Returns: 40153

  63. "???????????10??01????01???00???0??????????????0??0"

    5

    18

    Returns: 381708923992

  64. "111111111111000111111011?1111100111111111100000011"

    21

    39

    Returns: 2

  65. "????????????????????????????????1?????????????????"

    20

    25

    Returns: 327634393915761

  66. "????11?????1??0?????0????????????0?00???00????????"

    0

    9

    Returns: 1099510867677

  67. "????0????????0????????????1???????????????????????"

    0

    48

    Returns: 1

  68. "1??01?01?1010010100101?1010???01?1?1?1?10??1?10?01"

    619

    36

    Returns: 3616

  69. "00?0?101??11?0100?0?101011100111??1?0???0000?110?0"

    231

    18

    Returns: 31436

  70. "11111000000011011001011110010001101001001111110111"

    2

    3

    Returns: 1

  71. "010?01??0?00???010????10??0101?1?1?100?010??101010"

    19

    16

    Returns: 296602

  72. "????????????????????????????????????????1?????????"

    2

    15

    Returns: 544202858929478

  73. "01??11111??1??0?110110011??011?01001?1??1?010?????"

    3

    45

    Returns: 432

  74. "???101???0?0?1??111?0?0???????1111?0?0?1100110??00"

    0

    30

    Returns: 1271626

  75. "?????????0???0?0??0?????10??????????00????????????"

    0

    28

    Returns: 194458630304

  76. "??001?01??1?1??0????0?????010??1??1?1???110?01?1?1"

    572

    40

    Returns: 7097773

  77. "101??1010?101101?001?111001?1?0?01011??00?01??0?10"

    486

    45

    Returns: 0

  78. "1011010010101011110?101101010101010101010101001010"

    13

    5

    Returns: 2

  79. "01???1?01?10?0010010?101?1010100?00101?0?010?010?1"

    5

    39

    Returns: 0

  80. "001?100??111?0101?101?1011??001??11?10???0??001?0?"

    25

    3

    Returns: 262144

  81. "?01?110??1?01010101010?0101010?010?1?10??1010??110"

    11

    28

    Returns: 2460

  82. "???????1???"

    0

    6

    Returns: 638

  83. "?0?0??0?00????00???????00?0????????"

    0

    5

    Returns: 33539156

  84. "?????1?111?11????1???111?1?11????1?11??1??????11?"

    385

    26

    Returns: 1073260960

  85. "1111111111111111?111111111111111?111111"

    867

    22

    Returns: 4

  86. "1?1?11111?1??1??1?????"

    11

    1

    Returns: 4096

  87. "?00?0?00000000?000000?0000?0000000??00"

    5

    24

    Returns: 0

  88. "1?1111?1111?111?111111111"

    6

    1

    Returns: 16

  89. "?111111111111?11111111111"

    12

    0

    Returns: 4

  90. "01????01010?0??1"

    0

    2

    Returns: 128

  91. "010?0??1????0?0101010?01?10101?1"

    0

    13

    Returns: 1981

  92. "1010101010101010?010?010101010101010101010101"

    589

    39

    Returns: 1

  93. "?101?1?101??????01??01?????10???????0???????0??"

    24

    12

    Returns: 4227743764

  94. "0?01010?0?01?1?101010101?101?10"

    15

    27

    Returns: 0

  95. "????0???0?0"

    2

    4

    Returns: 101

  96. "??01??0?0101?1?1??01010?0??101010?010?01?1?1"

    16

    28

    Returns: 11285

  97. "????????????0?????????0????????????"

    4

    14

    Returns: 5714341674

  98. "00?0101?101010????10101010??11?1?100?0101010101010"

    0

    19

    Returns: 2048

  99. "?????0?0??0?????0?11??0?"

    0

    5

    Returns: 130918

  100. "??00"

    146

    0

    Returns: 4

  101. "????0??1?"

    87

    9

    Returns: 16

  102. "1?1?11?11?1?0?1?1?1??11?????0??0?0????0?1???1"

    5

    21

    Returns: 66180976

  103. "?????????0"

    3

    10

    Returns: 29

  104. "0??0?000?00000000???0?00?100????0?0000?00?1110??00"

    6

    48

    Returns: 0

  105. "0?0?????1??10???0?00?10??00??10??0??001?0101???"

    7

    15

    Returns: 22159325

  106. "010101?10101?01010101010101010"

    0

    1

    Returns: 4

  107. "????0??????1??0"

    0

    10

    Returns: 299

  108. "1??11111?11???11?11?1?1110?111?111110???1??1???11"

    811

    25

    Returns: 524288

  109. "??????????1?????1???????????????????"

    890

    4

    Returns: 17160197364

  110. "001"

    0

    0

    Returns: 1

  111. "?01?11?011000?0?01?0111?0????1111101?0?1?0000000"

    3

    13

    Returns: 16384

  112. "1??0?0?0?0??0???1???????10???????01?0?"

    4

    17

    Returns: 27382912

  113. "1?1111?01"

    0

    9

    Returns: 0

  114. "10?????111010"

    0

    12

    Returns: 0

  115. "00?0?1?111001??000?001010??01??111??1?0?1110????"

    0

    4

    Returns: 262144

  116. "0010100010101010?00?0101?100?0"

    339

    29

    Returns: 0

  117. "111000??1??001?00?00000?1?"

    263

    25

    Returns: 0

  118. "010101?1?1??010"

    1

    10

    Returns: 2

  119. "?1010?10?01010101010101010100101011010101010100100"

    19

    20

    Returns: 2

  120. "?1????????"

    4

    0

    Returns: 512

  121. "10100?????10??????10"

    0

    16

    Returns: 0

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: