CoinFlip

SRM 119 · 2002-11-07 · by axchma

Class Name: CoinFlip

Return Type: int

Method Name: decide

Arg Types: (string)

Problem Statement

Harry and Sally want to rent a movie. Harry wants to watch "The Terminator", and Sally wants to watch "When Harry Met Sally". They decide to flip a coin. Unfortunately, they have only one coin, which is bent, so they think that it is not a fair coin (the chances of heads and tails may not be equal).

I advise them to use the following procedure, which makes the probability of either outcome equal: Flip the coin twice. If it flips heads the first time and tails the second time, then they watch "The Terminator"; if it flips tails the first time and heads the second time, then they watch "When Harry Met Sally". If it flips the same (heads or tails) both times, they repeat the procedure (they flip twice again).

Your task is, given a String representing the sequence of flip results, return the number of the flip (the flips are 1-indexed) after which they can choose a movie according to the protocol described above. If they can't choose return -1.

Constraints

flips has between 0 and 50 characters inclusive
each character of flips is either an 'H', representing heads, or a 'T', representing tails.

Examples

""
Returns: -1

"HHTH"
Returns: 4

"TTHHTHHHTH"
Returns: 6

"TTHH"
Returns: -1

"TT"
Returns: -1

Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CoinFlip with a public method int decide(string flips) · 44 test cases · 2 s / 256 MB per case