Connection Status:
Competition Arena > BlackAndRed

BlackAndRed

SRM 223 · 2004-12-18 · by legakis

SRM 223 · 2004-12-18 · by legakis · Brute Force, Simple Search, Iteration
Class Name: BlackAndRed
Return Type: int
Method Name: cut
Arg Types: (string)
Problem Statement

Problem Statement

You are playing a game with a deck of cards, half red and half black. After your friend thoroughly shuffles the cards, you cut the deck. Your friend then begins to turn the cards over one at a time, starting from the top of the deck. If, at any time, there are more red cards showing than black cards, you lose. If this never occurs by they time all the cards have been turned up, you win.

After losing several times in a row, you get frustrated and decide to cheat. After your friend shuffles the deck, you distract him and then secretly look at the cards, to figure out where you should cut the deck.

"Cutting the deck" means to take a stack of cards off the top of the deck, and place this stack on the bottom.

Given a String deck, representing the cards, return the number of cards you should remove from the top of the deck when you cut. A 'R' indicates a red card, and a 'B' indicates a black card. The first character of deck represents the top card, and the last character represents the bottom card. If there are multiple possibilities, return the smallest number.

Constraints

  • cards will contain between 2 and 50 characters, inclusive.
  • cards will contain only the characters 'R' and 'B'.
  • cards will contain the same number of 'R' and 'B' characters.
Examples
0)
"BRBRBR"
Returns: 0

You could cut the deck at positions 0, 2, or 4 to win.

1)
"RBRBRB"
Returns: 1

If you cut the deck at position 0, the first card dealt will be red and you will lose immediately. However, if you cut the deck at position 1, you will win.

2)
"BBBRRRRB"
Returns: 7

The only way to win is to cut the deck at position 7. After this cut, the deck becomes: "BBBBRRRR".

3)
"BR"
Returns: 0
4)
"RBRBBRRRRBBBRBBRRBRBBRRRBRBBBRBRBRBRBRRB"
Returns: 9

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

Coding Area

Language: C++17 · define a public class BlackAndRed with a public method int cut(string deck) · 21 test cases · 2 s / 256 MB per case

Submitting as anonymous