Statistics

Problem Statement for "FourLamps"

Problem Statement

Fox Ciel has n lamps. The lamps are arranged in a row from the left to the right, and they are numbered 0 through n-1 in that order. You are given a String init with n characters that describes the initial state of the lamps: init[i] is '1' if lamp i is initially turned on, or '0' if it is initially turned off.

You are also given an int k. Below we describe an operation. Ciel can use that operation at most k times. Compute and return the number of different final states she can obtain. (Two states of lamps are different if there is a lamp that is on in one state but off in the other. The initial state is always one of the possible final states.)

The operation looks as follows:
  1. Ciel chooses four consecutive lamps such that either exactly one of them is on, or exactly one of them is off. (If there is no such group of lamps, Ciel cannot perform any more operations.)
  2. Ciel divides all lamps into a left part and a right part so that the division point is in the middle of the four lamps chosen in the previous step. In other words, if the four chosen lamps are x, x+1, x+2, x+3, the left part is {0, 1, ..., x+1} and the right part is {x+2, ..., n-2, n-1}.
  3. Ciel chooses either the left part or the right part.
  4. Ciel toggles all lamps in the chosen part. (Toggling a lamp means switching it to the opposite state.)

Definition

Class:
FourLamps
Method:
count
Parameters:
String, int
Returns:
long
Method signature:
long count(String init, int k)
(be sure your method is public)

Constraints

  • init will contain between 4 and 50 characters, inclusive.
  • Each character in init will be '0' or '1'.
  • k will be between 1 and 1,000,000,000, inclusive.

Examples

  1. "0001"

    2

    Returns: 4

    As there are only four lamps, there is only one group of four consecutive lamps. If these four lamps satisfy the constraint, the left part will be lamps {0,1} and the right part will be lamps {2,3}. If Ciel performs zero operations, the only possible final state is the initial state "0001". If Ciel performs one operation, she can either toggle the left part or the right part. Toggling the left part produces the state "1101", toggling the right part produces the state "0010". Note that both states produced by the first operation still have the property that enables us to do the next operation: exactly one of the four lamps is off in "1101", and exactly one of them is on in "0010". What states can we reach by performing two operations? Toggling the left part and then the left part again will bring us back to "0001". Toggling the right part twice has the same effect. Toggling the left part and then the right part produces the final state "1110". Toggling the right half and then the left half leads to that state as well. In total there are four possible final states: "0001", "1101", "0010", "1110".

  2. "0001"

    1000000000

    Returns: 4

    In the previous scenario increasing k to 10^9 does not change the answer. The following operations won't produce any new states of the lamps.

  3. "1010"

    100

    Returns: 1

    This time Ciel cannot make any operation because there are no four consecutive lamps with the required property. Thus, the only possible final state is the initial state.

  4. "000111"

    3

    Returns: 12

    These are the states we can get: "000111" "110111" "001000" "111011" "000100" "111000" "001111" "110000" "001011" "110100" "000011" "111100"

  5. "00000010000"

    5

    Returns: 58

  6. "10101100101010001011000100101000100001101"

    58

    Returns: 100256132848

    Watch for overflow.

  7. "0010"

    1

    Returns: 3

  8. "000111"

    1

    Returns: 5

  9. "1101111111111101101111111011111111"

    459

    Returns: 21036600

  10. "0001000011011000001"

    31

    Returns: 48552

  11. "1111111111"

    11

    Returns: 1

  12. "1111"

    4

    Returns: 1

  13. "111010011110101010011"

    204

    Returns: 151164

  14. "11110011111"

    53

    Returns: 252

  15. "0000000000000000000010000000000000000000100000"

    839

    Returns: 271502

  16. "111110111111"

    48

    Returns: 90

  17. "110010101100"

    3

    Returns: 36

  18. "1111111111111111110111111111111111101110101"

    373654854

    Returns: 1498796

  19. "10100"

    945101462

    Returns: 6

  20. "11111110111111111110101101010111111111011"

    13818199

    Returns: 123047496

  21. "11111111101111110011110111111111111111111111111"

    305

    Returns: 431106390

  22. "1111011"

    5

    Returns: 20

  23. "111110111111111101111111111111111"

    1

    Returns: 17

  24. "000010011011110000001"

    676411108

    Returns: 184756

  25. "001000001100000000000010010"

    166

    Returns: 4085950

  26. "001000"

    9

    Returns: 12

  27. "01010000010000000000010010110000010000010000110"

    279

    Returns: 1293252810256

  28. "110110100011110010111110"

    58

    Returns: 1410314

  29. "111100011"

    32

    Returns: 70

  30. "110000010010000000000001010"

    391762884

    Returns: 961400

  31. "1010101000110001101001000010010011"

    317

    Returns: 1131445440

  32. "000000000000000000"

    1

    Returns: 1

  33. "0111"

    1

    Returns: 3

  34. "1110000"

    100027819

    Returns: 20

  35. "0000000000100000000000000100100000011000000000"

    1

    Returns: 25

  36. "11010011110"

    21

    Returns: 252

  37. "000000000000000000000000010000000000000"

    552

    Returns: 1332

  38. "111111111111111110111"

    101

    Returns: 342

  39. "010000000010001001000010001000100001011000"

    507

    Returns: 177464757600

  40. "110111011100011011111111011010100111011101000"

    155

    Returns: 1919878174380

  41. "1111011111111011111111111111111111111111111111"

    233

    Returns: 271502

  42. "1111111110111101111111110"

    1

    Returns: 19

  43. "1001101010001111000000010000011010001101110100110"

    946

    Returns: 32247603683100

  44. "00000000001000100000001001"

    743903527

    Returns: 692208

  45. "010100110000010010000000000110"

    18

    Returns: 4462986

  46. "111011111111111111111110111111111111111"

    192

    Returns: 132090

  47. "00000000000000000100000000"

    141731695

    Returns: 552

  48. "000000100"

    31

    Returns: 42

  49. "001000100100"

    7

    Returns: 366

  50. "00001000000110"

    1

    Returns: 11

  51. "1011111111111001110001"

    140

    Returns: 251940

  52. "0110010001000110000000100001010"

    295079411

    Returns: 155117520

  53. "001000000100000001001001000"

    28

    Returns: 4588960

  54. "1110001110011000111111000"

    46

    Returns: 1591564

  55. "11111111101110111111001101101111111111011111"

    690

    Returns: 105720458160

  56. "1000100011011100"

    916127298

    Returns: 4004

  57. "011111010111000001011011010111110101111000011001"

    793

    Returns: 11216466014292

  58. "0111111111111101"

    53

    Returns: 182

  59. "1111111"

    19

    Returns: 1

  60. "0000000000000000100001000000001"

    111

    Returns: 237510

  61. "11111100111111110110"

    160

    Returns: 63648

  62. "01100010000000000000000000010000000"

    286

    Returns: 8544096

  63. "000100000000000000000"

    24

    Returns: 310

  64. "110011100000011010000"

    617487767

    Returns: 184756

  65. "111111111111111111111110111111111111111111111111"

    1042

    Returns: 2070

  66. "11001010000011010101111000111000100111100100"

    133

    Returns: 1016140151536

  67. "111110111111111111111111111111111111111"

    93

    Returns: 1332

  68. "0110100000010111000010"

    178

    Returns: 251940

  69. "11111111"

    14

    Returns: 1

  70. "111111111111110111111111111111111111111"

    122

    Returns: 1332

  71. "00010110000000000011"

    128

    Returns: 37128

  72. "101111110111111011101111111111011111111111001110"

    1

    Returns: 43

  73. "0100111000101111"

    54

    Returns: 6864

  74. "1111111111101111111101111111111111111111"

    194030428

    Returns: 147630

  75. "1100000010000110110000"

    54

    Returns: 369512

  76. "11111111111111111111111111111111111"

    377290146

    Returns: 1

  77. "000000101000100001000001001000000000010000001"

    893

    Returns: 73153696336

  78. "000011110"

    6

    Returns: 66

  79. "1111111111111011111111111110111111111111111"

    474

    Returns: 202540

  80. "0000110110000"

    12

    Returns: 892

  81. "000110011000"

    1

    Returns: 5

  82. "000010000000000000000100100000000100000"

    707

    Returns: 77216040

  83. "11111110111111011110"

    1

    Returns: 19

  84. "1111011101111011111111"

    1

    Returns: 25

  85. "11111111111111110011100111111111101111101111"

    1

    Returns: 25

  86. "100000000000001100100000"

    131

    Returns: 341088

  87. "110111111011111111"

    128

    Returns: 3640

  88. "0000000000100000010010"

    190

    Returns: 31008

  89. "1000000001000"

    83

    Returns: 330

  90. "00000000000001"

    42

    Returns: 24

  91. "100011111001111000101111110001110101101010100"

    1

    Returns: 41

  92. "0000110101010110011001001011101010000100000"

    907

    Returns: 404225281200

  93. "0000000000010001000010000000000010110011101100010"

    1

    Returns: 45

  94. "101111111111011111111111111111111111111"

    563

    Returns: 15540

  95. "1001"

    1

    Returns: 1

  96. "000111000010010100110"

    180

    Returns: 151164

  97. "0001011010010101010010"

    91

    Returns: 155040

  98. "100000000000000"

    44

    Returns: 26

  99. "101100100000101110000010100111001111"

    61

    Returns: 4425699846

  100. "000110000000000000100111111000101111100010111001"

    921

    Returns: 8308493343920

  101. "011001101111001111011101111011011100111110100111"

    839

    Returns: 8308493343920

  102. "111100"

    11

    Returns: 12

  103. "1111111110111101101111111111111"

    1

    Returns: 21

  104. "1111111110111110111011111111101"

    299

    Returns: 3121560

  105. "001100101001010100"

    65

    Returns: 25740

  106. "0111010101110"

    30

    Returns: 660

  107. "0000000000000000000000010"

    242816223

    Returns: 46

  108. "10110111111011111111111101111111111111111011111111"

    775

    Returns: 3354213280

  109. "11001100110011001100110000000000000000000000000000"

    1000000000

    Returns: 54771314563296

  110. "11001100110011001100110000000000000000000000000000"

    554

    Returns: 54771314560872

  111. "11001100110011001100110000000000000000000000000000"

    555

    Returns: 54771314561466

  112. "00101100101010001011000100101000100001101"

    58

    Returns: 118691951548

  113. "0001"

    1

    Returns: 3

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: