CatAndRabbit

SRM 558 · 2012-06-05 · by lyrically

SRM 558 · 2012-06-05 · by lyrically · Math

Show categories

Class Name: CatAndRabbit

Return Type: String

Method Name: getWinner

Arg Types: (string)

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 a String 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:

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.

The animal who is unable to take a valid turn loses the game. Return the String "Cat" if Cat will win, "Rabbit" if Rabbit will win, assuming both animals play optimally.

Constraints

tiles will contain between 1 and 50 characters, inclusive.
Each character in tiles will be '.' or '#'.

Statement by TopCoder, Inc. — view the original on the archive.

Examples

"#.."
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.

".#."
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.

"###"
Returns: "Rabbit"

Cat has no legal move at the beginning of the game.

"#..##.#"
Returns: "Cat"

"..."
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