Statistics

Problem Statement for "GearsDiv2"

Problem Statement

Goose Tattarrattat has a machine that contains N gears (cogwheels). The gears are numbered 0 through N-1. Currently, the gears are arranged into a cycle: for each i, gear i meshes with gears i-1 and i+1 (counting modulo N). In particular, gear 0 meshes with gear N-1.


Let X and Y be two meshing gears. Note that if X is turning, Y must clearly be turning in the opposite direction (clockwise vs. counter-clockwise).


For each of the N gears we have a desired direction of turning. You are given this information encoded as a String Directions. Character i of Directions is 'R' if we want gear i to turn to the right (clockwise), and it is 'L' if we want it to turn to the left.


Of course, it may be impossible to satisfy all the desired directions of turning. Return the minimal number of gears that have to be removed from the machine so that all remaining gears can turn in the desired directions at the same time.

Definition

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

Notes

  • Removing a gear creates a gap between the other gears. For example, after removing the gear 7, gears 6 and 8 will not mesh.

Constraints

  • Directions will contain between 3 and 50 characters, inclusive.
  • Each character of Directions will be 'R' or 'L'.

Examples

  1. "LRRR"

    Returns: 1

    Once we remove gear 2, the other three are free to turn in the desired directions.

  2. "RRR"

    Returns: 2

    Gear 0 meshes with gear 2.

  3. "LRLR"

    Returns: 0

  4. "LRLLRRLLLRRRLLLL"

    Returns: 6

  5. "LRLLRLRLRLLLRLRRLLLLLLLLLLRLRLRLRRRRRLRRLRLRL"

    Returns: 12

  6. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: 25

  7. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: 25

  8. "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: 24

  9. "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: 24

  10. "LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR"

    Returns: 0

  11. "RLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR"

    Returns: 1

  12. "RLL"

    Returns: 1

  13. "LRRR"

    Returns: 1

  14. "LLLRR"

    Returns: 2

  15. "RRLLRR"

    Returns: 3

  16. "LLRLRRR"

    Returns: 2

  17. "LRRRLLRL"

    Returns: 3

  18. "LRLRRRLRL"

    Returns: 2

  19. "LRRLRLLLRL"

    Returns: 3

  20. "RRRRLLLRLLR"

    Returns: 4

  21. "RRLLRRRLRLLL"

    Returns: 4

  22. "LRRRLRLLLRLRL"

    Returns: 3

  23. "LLRLRLRRRLLRRL"

    Returns: 4

  24. "RLLLLLRRRLLLRRR"

    Returns: 6

  25. "LLLRLRRRRLRRRRLR"

    Returns: 5

  26. "RRRRLLLRRLLLRLLRR"

    Returns: 7

  27. "RLRLRRLLRRLRRRRLRR"

    Returns: 6

  28. "LRRLLRLLRLRLRLRLRRR"

    Returns: 4

  29. "RRLLLRRLRRLLLLRRLLRR"

    Returns: 9

  30. "LRLLLRRRRLRLLLRRRLLLL"

    Returns: 7

  31. "LLRLRLLRRLRRRLLRLRRRRR"

    Returns: 7

  32. "RLRLRLLLLLLLRRLLRLLLLRR"

    Returns: 8

  33. "LRLLRLRLRRLRRRLRRRLLRRRL"

    Returns: 7

  34. "LLRLLRRLLLRRLLRLLLLLRLRLR"

    Returns: 8

  35. "LLLLRRRRRRLRRLRRRRRLLLRRRL"

    Returns: 10

  36. "LLRLLRRRRRLRRRRLRRLLRRLRRLR"

    Returns: 10

  37. "LLLLRRRLLRLLRLLLRRLLRRRLRRLL"

    Returns: 11

  38. "RLLLLLRLRLRLLLLRRRLLLRRRLRRRR"

    Returns: 9

  39. "LLRRRLLLLRRRRRRRLLLLLRLRLLRLRL"

    Returns: 10

  40. "RLRRRRLLRLLRRLRRLRRRRLRLRRLLRLL"

    Returns: 11

  41. "RRRRLRLRRRLLLLLLRRRLLLRRLRLRLLLR"

    Returns: 10

  42. "LLRRRLLLRLLLLRRLLRLLLRLRLLRRLLLLR"

    Returns: 12

  43. "LRLLRLRRRLLLRRLRLLRLRRRRRRLLRRLLRL"

    Returns: 12

  44. "RLRLRRLRLLRLLRLRRLLRLRRLLRRRLRRRLLR"

    Returns: 11

  45. "RRLLLRLLLRRLRLRRRLRLRLRRRRRRLRLRLRLL"

    Returns: 9

  46. "LRLRLLRLRRLRLLLRLLLRLRLRRLRLRLLRRLRRR"

    Returns: 8

  47. "LLRLLLRRLRLRRLLLLLLRLLLRRLLRLLRRLLLLRL"

    Returns: 14

  48. "RLLLRRLRRLRLRLLLRRRLRLLLRRLRLLRLRLLRRRR"

    Returns: 11

  49. "LRRLLLRRRLLRLLRLRLLRRLLRLLLLRRRLRRLRRLRL"

    Returns: 14

  50. "LRLRRRLRRRRRRRRLLRRLLLLRLRLRRRRRRLRRLLRLR"

    Returns: 14

  51. "LRRRLLLLLLLRLRLRLLRLLRRLRRLRLRLRRRLRLLRLRL"

    Returns: 11

  52. "LLRLLLLRRRRRLLLRLRLLLRLLRLLRRLLLRLRRRLRRLRL"

    Returns: 13

  53. "RRRLLRRLRLRRRRLRRRRLLLRRLRRRRRLRLLRLRLLRLRRL"

    Returns: 14

  54. "RRLLRRLRRLRRLRRLLLLLLRLRRRRLLLLRLLRLRLLRLLRRR"

    Returns: 17

  55. "LRRRRRRLLRLRRRRLRRLLLLRRLLLRRLRRLLLRLLRLLRLLRR"

    Returns: 18

  56. "RLRLLRLRRRLRLLLRRRRLLLLLRLRLRLRRLRRLLLRLRLRRLLL"

    Returns: 12

  57. "LRLLRRRRLLRRRLLLLRRRRLRRLLRLLLLRLLRRLLLRLLRRRLLR"

    Returns: 19

  58. "RRRRLLLRLLRLLRRLRRRLLLLRRLRLRLRLRLLLRLRLRRLLRLLLL"

    Returns: 15

  59. "LLRLLRRLRRLRRLLLRRLRRLLRRRRLLLLLLLRRLLLRLRRLRRLRRR"

    Returns: 19

  60. "RRRRRRRLRRRRRRRLRLRLLRLRLRLRRLRLRLLLRLRLLRLLRRLRRR"

    Returns: 14

  61. "LRRLLLRRLRRLLRRLRLLRRLLLRLRRRRLRLLLLRLRLRLLRLLLLRR"

    Returns: 17

  62. "LLRL"

    Returns: 1

  63. "RRLLRRLRLRRLLLRLLLRLRLLLRLRLLRLRLLRLLRLLRLRLRLLR"

    Returns: 12

  64. "LLRLRLRLLRRRLLRLRLRRLRLRLRLRRLRLLRLRRLRLRLRLLRLRRL"

    Returns: 10

  65. "LLLLLLLLLLLLLLLRLRRRRLLLLLLLLLLLLLLLLLRLRLL"

    Returns: 18

  66. "RRLRLR"

    Returns: 1

  67. "RRLRLRLRLLRLRLRLRRLRLRLLLRLRLLRLLRRLRRRLLRRLLLR"

    Returns: 11

  68. "RRLLLRLR"

    Returns: 2

  69. "RRLR"

    Returns: 1

  70. "RLRLLRLLLRRRLRLRLRRRLRLRLRLLRLRLLLLLRRLRLLLLRLLLLR"

    Returns: 13

  71. "LLLLLLL"

    Returns: 4

  72. "LLRLLRRLLLRRRLLL"

    Returns: 6

  73. "LRLRLRRLLRLRLLLRLRL"

    Returns: 4

  74. "LLRLRLRRRLLRLRLRRRLRLRLRLRRLRRRLRRRRLLLLRRLRLRLLL"

    Returns: 12

  75. "LRLRL"

    Returns: 1

  76. "LLRLLRL"

    Returns: 2

  77. "RRRRRRRLRRRRRRRLRLRLLRLRLRLRRLRRRRRRRRRRRRRR"

    Returns: 15

  78. "RRRRRRLRRLRRR"

    Returns: 5

  79. "RLLRR"

    Returns: 2

  80. "LRLRLRRLLRLRLLLRLRLLLLLLLLLLLLLLLLLLLLLLRRLRLLLRL"

    Returns: 17

  81. "LLRLRL"

    Returns: 1

  82. "RRLRRR"

    Returns: 2

  83. "LLRRRL"

    Returns: 2

  84. "LRLL"

    Returns: 1

  85. "RRRRRRRRRRRRRRRRRRRRRR"

    Returns: 11

  86. "LRLRLRLLRLRRRL"

    Returns: 3

  87. "LLLLRRRRL"

    Returns: 4

  88. "LRRL"

    Returns: 2

  89. "RRRR"

    Returns: 2

  90. "RRRRLR"

    Returns: 2

  91. "LLRRL"

    Returns: 2

  92. "RRRRLLR"

    Returns: 3

  93. "LLLLRL"

    Returns: 2

  94. "LLRRLRRLLLLRRRRL"

    Returns: 7

  95. "LLR"

    Returns: 1

  96. "LRR"

    Returns: 1

  97. "LLRLRRLLLRL"

    Returns: 3

  98. "RRRRRRRLRRRRRRRLRLRLLRLRLRLRRLRLRLLLRLRLLLLLLLLRRR"

    Returns: 15

  99. "LLLLLLLLLLLLLLLRRRRRRRRRRRRRRRRRR"

    Returns: 16

  100. "RRLLR"

    Returns: 2

  101. "LRRRRRRL"

    Returns: 4

  102. "RLR"

    Returns: 1

  103. "LRL"

    Returns: 1

  104. "RRRLRR"

    Returns: 2

  105. "LRLRR"

    Returns: 1

  106. "RLRRRL"

    Returns: 1

  107. "LLLLLLLLLLLLLLLLLLLRRRRRRRRRRRRLLLLLLLLLLRR"

    Returns: 21

  108. "LRLRLRLRL"

    Returns: 1

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: