CatAndRabbit
SRM 558 · 2012-06-05 · by lyrically
SRM 558 · 2012-06-05 · by lyrically · Math
Problem Statement
Problem Statement
Cat and Rabbit are going to play the following game.
There are some tiles in a row. Each of the tiles is colored white or black. You are given aString tiles, describing the initial arrangement of tiles.
The characters '.' and '#' represent a white tile and a black tile, respectively.
Cat and Rabbit take alternating turns. Cat plays first. In each turn, the following actions must be performed:String "Cat" if Cat will win, "Rabbit" if Rabbit will win, assuming both animals play optimally.
There are some tiles in a row. Each of the tiles is colored white or black. You are given a
Cat and Rabbit take alternating turns. Cat plays first. In each turn, the following actions must be performed:
- First, the player must select a black tile and step on it.
- Then, the player must make some steps (as many as they want, but at least one). In each step, the player must select an adjacent white tile, move to that tile, and change its color to black.
Constraints
- tiles will contain between 1 and 50 characters, inclusive.
- Each character in tiles will be '.' or '#'.
Examples
0)
"#.." Returns: "Cat"
In the first turn, Cat will select the leftmost tile and can move to the right twice. Then Rabbit has no legal move and loses.
1)
".#." Returns: "Rabbit"
In the first turn, Cat must select the middle tile. Then, Cat can decide whether to step to the left or to the right. In the second turn, Rabbit will select the middle tile and then step in the opposite direction.
2)
"###" Returns: "Rabbit"
Cat has no legal move at the beginning of the game.
3)
"#..##.#" Returns: "Cat"
4)
"..." Returns: "Rabbit"
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CatAndRabbit with a public method string getWinner(string tiles) · 103 test cases · 2 s / 256 MB per case