RowAndManyCoins
SRM 522 · 2011-05-25 · by lyrically
SRM 522 · 2011-05-25 · by lyrically · Greedy
Problem Statement
Problem Statement
Alice and Bob play the following game.
The game board consists of some cells in a row.
Each cell is marked either 'A' or 'B'.
At the beginning, there are no coins placed on the board – all the cells are empty.
Alice and Bob take alternating turns.
Alice plays first.
In each turn, the current player chooses some contiguous empty cells and places a coin onto each of the chosen cells.
The player must always choose at least one cell.
The player must never choose all empty cells.
In other words, after each turn there must be at least one empty cell.
The following picture shows two examples of placing coins:
The game ends when there is only one cell left without a coin. If that cell is marked 'A', Alice wins. Otherwise, Bob wins. You are given aString cells representing the row of cells.
Assuming that both players aim to win and play optimally, return a String containing the name of the winner.
The following picture shows two examples of placing coins:
The game ends when there is only one cell left without a coin. If that cell is marked 'A', Alice wins. Otherwise, Bob wins. You are given a
Constraints
- cells will contain between 2 and 50 characters, inclusive.
- Each character in cells will be either 'A' or 'B'.
Examples
0)
"ABBB" Returns: "Alice"
Alice can win by placing coins on three cells marked 'B' in her first turn.
1)
"BBBB" Returns: "Bob"
2)
"BA" Returns: "Alice"
3)
"BABBABBB" Returns: "Bob"
4)
"ABABBBABAABBAA" Returns: "Alice"
Submissions are judged against all 102 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RowAndManyCoins with a public method string getWinner(string cells) · 102 test cases · 2 s / 256 MB per case