GearsDiv2
SRM 589 · 2013-06-25 · by snuke
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
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.
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'.
"LRRR" Returns: 1
Once we remove gear 2, the other three are free to turn in the desired directions.
"RRR" Returns: 2
Gear 0 meshes with gear 2.
"LRLR" Returns: 0
"LRLLRRLLLRRRLLLL" Returns: 6
"LRLLRLRLRLLLRLRRLLLLLLLLLLRLRLRLRRRRRLRRLRLRL" Returns: 12
Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GearsDiv2 with a public method int getmin(string Directions) · 108 test cases · 2 s / 256 MB per case