Statistics

Problem Statement for "CuttingBitString"

Problem Statement

We are in a distant future. After the downfall of mankind, the Earth is now ruled by fairies. The "Turing game Online" website is hot among fairies right now. On this website, everyone can play the programming puzzle "Turing game".


Fairies love powers of 5, that is, the numbers 1, 5, 25, 125, 625, and so on. In the Turing game, the player is given a string of bits (zeros and ones). The ideal situation is when the string is represents a power of 5 in binary, with no leading zeros. If that is not the case, the fairy player tries to cut the given string into pieces, each piece being a binary representation of a power of 5, with no leading zeros. Of course, it may be the case that even this is impossible. In that case, the fairy player becomes depressed, and bad things happen when a fairy gets depressed. You, as one of the surviving humans, are in charge of checking the bit strings to prevent the bad things from happening.


You are given a String S that consists of characters '0' and '1' only. S represents the string given to a player of the Turing game. Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5. If there is no such K, return -1 instead.

Definition

Class:
CuttingBitString
Method:
getmin
Parameters:
String
Returns:
int
Method signature:
int getmin(String S)
(be sure your method is public)

Constraints

  • S will contain between 1 and 50 characters, inclusive.
  • Each character in S will be either '0' or '1'.

Examples

  1. "101101101"

    Returns: 3

    We can split the given string into three "101"s. Note that "101" is 5 in binary.

  2. "1111101"

    Returns: 1

    "1111101" is 5^3.

  3. "00000"

    Returns: -1

    0 is not a power of 5.

  4. "110011011"

    Returns: 3

    Split it into "11001", "101" and "1".

  5. "1000101011"

    Returns: -1

  6. "111011100110101100101110111"

    Returns: 5

  7. "1101100011010111001001101011011100010111011110101"

    Returns: 1

  8. "0101"

    Returns: -1

  9. "1001"

    Returns: -1

  10. "11111111111111111111111111111111111111111111111111"

    Returns: 50

  11. "10111001110011"

    Returns: 4

  12. "10011100011110011100111110100001001110011"

    Returns: 7

  13. "10111110101111000011111010000100111110100001001101"

    Returns: 4

  14. "11101111011011111101110011101101101111011101101111"

    Returns: 22

  15. "11111101111111011111011101"

    Returns: 10

  16. "1011111110111111011111101111111111101111110111"

    Returns: 14

  17. "11111011111101111110111111011111101111110111111011"

    Returns: 8

  18. "11111011111111101111111101111111101111110111111111"

    Returns: 20

  19. "11111011111101111111011111101111111111111101111111"

    Returns: 20

  20. "11001110001"

    Returns: 2

  21. "110011000100101101"

    Returns: 2

  22. "111110100001001"

    Returns: 2

  23. "101111101"

    Returns: 5

  24. "11001110001111101"

    Returns: 6

  25. "0"

    Returns: -1

  26. "1"

    Returns: 1

  27. "00"

    Returns: -1

  28. "10"

    Returns: -1

  29. "01"

    Returns: -1

  30. "11"

    Returns: 2

  31. "000"

    Returns: -1

  32. "100"

    Returns: -1

  33. "010"

    Returns: -1

  34. "110"

    Returns: -1

  35. "001"

    Returns: -1

  36. "101"

    Returns: 1

  37. "011"

    Returns: -1

  38. "111"

    Returns: 3

  39. "00000000000000000000000000000000000000000000000000"

    Returns: -1

  40. "101101101101101101101101101101101101101101101101"

    Returns: 16

  41. "00010111001110100000101101001100010011111111100110"

    Returns: -1

  42. "11101001011110011100110111100111000111000100001010"

    Returns: -1

  43. "01010101001001100110001101101110111100111111001100"

    Returns: -1

  44. "01000000100101011000001001011111111100100100100111"

    Returns: -1

  45. "10001110000011011101010011010001011111010100000001"

    Returns: -1

  46. "11110101100011101001011001110010110000"

    Returns: -1

  47. "0101011001101011010111000100010"

    Returns: -1

  48. "001001011000000011001011100001000111000"

    Returns: -1

  49. "11001111010110010000110011100110011111001101"

    Returns: -1

  50. "0011100"

    Returns: -1

  51. "1"

    Returns: 1

  52. "101"

    Returns: 1

  53. "11001"

    Returns: 1

  54. "1111101"

    Returns: 1

  55. "1001110001"

    Returns: 1

  56. "110000110101"

    Returns: 1

  57. "11110100001001"

    Returns: 1

  58. "10011000100101101"

    Returns: 1

  59. "1011111010111100001"

    Returns: 1

  60. "111011100110101100101"

    Returns: 1

  61. "100101010000001011111001"

    Returns: 1

  62. "10111010010000111011011101"

    Returns: 1

  63. "1110100011010100101001010001"

    Returns: 1

  64. "1001000110000100111001110010101"

    Returns: 1

  65. "101101011110011000100000111101001"

    Returns: 1

  66. "11100011010111111010100100110001101"

    Returns: 1

  67. "10001110000110111100100110111111000001"

    Returns: 1

  68. "1011000110100010101111000010111011000101"

    Returns: 1

  69. "110111100000101101101011001110100111011001"

    Returns: 1

  70. "100010101100011100100011000001001000100111101"

    Returns: 1

  71. "10101101011110001110101111000101101011000110001"

    Returns: 1

  72. "1101100011010111001001101011011100010111011110101"

    Returns: 1

  73. "11110011100111011100111100110110110111100110111001"

    Returns: 16

  74. "101110011100011001110001111110110011100011111101"

    Returns: 7

  75. "11001110011111010000100110110111100111110100001001"

    Returns: 8

  76. "1111010000100111110100001001110000110101"

    Returns: 3

  77. "101111011100110101100101110011011111010111100001"

    Returns: 4

  78. "111010001101010010100101000110011100011"

    Returns: 3

  79. "11110100001001111011100110101100101"

    Returns: 2

  80. "111101000010011001010100000010111110011"

    Returns: 3

  81. "1111101101110100100001110110111011100110011100011"

    Returns: 5

  82. "1001110001"

    Returns: 1

  83. "11011110000010110110101100111010011101100111001"

    Returns: 2

  84. "101110011100110110110110111001110011100110111001"

    Returns: 12

  85. "11111011100111001100111000110011100011011001110001"

    Returns: 7

  86. "1100110011100011111010000100110111110100001001"

    Returns: 5

  87. "111110110111110101111000011001110001"

    Returns: 3

  88. "101111011100110101100101100101010000001011111001"

    Returns: 3

  89. "100110001001011011110100011010100101001010001"

    Returns: 2

  90. "101101011110011000100000111101001101"

    Returns: 2

  91. "111011100110101100101101101"

    Returns: 3

  92. "1011111010111100001"

    Returns: 1

  93. "10111001110111100000101101101011001110100111011001"

    Returns: 3

  94. "10111010010000111011011101100101010000001011111001"

    Returns: 2

  95. "11111111111111111111111111110"

    Returns: -1

  96. "1011111011011111011011111011011111011011111011111"

    Returns: 29

  97. "0011"

    Returns: -1

  98. "00000000000000000000000001111111111111111111111111"

    Returns: -1

  99. "11001000110000100111001110010101"

    Returns: 2

  100. "10101101011110001110101111000101101011000110001101"

    Returns: 2

  101. "1000111000011011110010011011111100000110111001"

    Returns: 3

  102. "1010101"

    Returns: -1

  103. "111110111111011111101101"

    Returns: 4

  104. "1000000000000000000000000000000000000000000000000"

    Returns: -1

  105. "000001111101"

    Returns: -1

  106. "11010110101111000111010111100010110101100011000111"

    Returns: 4

  107. "110111110101"

    Returns: -1

  108. "11111011111010111100001"

    Returns: 5

  109. "11011000110101110010011010110111000101110111101011"

    Returns: 2

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: