Connection Status:
Competition Arena > EllysCheckers

EllysCheckers

SRM 534 · 2011-11-22 · by espr1t

SRM 534 · 2011-11-22 · by espr1t · Dynamic Programming, Simple Search, Iteration
Class Name: EllysCheckers
Return Type: String
Method Name: getWinner
Arg Types: (string)
Problem Statement

Problem Statement

Elly and Kriss play a game. The game is played on a single row that consists of N cells; we will call it the board. The cells of the board are numbered 0 through N-1, from the left to the right. Each cell of the board is either empty or occupied by a single checker. The girls take alternating turns, until one of them cannot make a move. The girl who is unable to make a move loses the game.

In each move the current player selects a cell containing a checker and performs one of the following two types of moves:
  • A step, in which the checker is moved one cell to the right. The step can only be made if the target cell is empty.
  • A jump, in which the checker jumps three cells to the right. The jump can only be made if the target cell is empty and the cells it jumped over contain two other checkers.
Once a checker reaches the rightmost cell, it disappears immediately and no longer plays any role in the game.

The initial layout of the board will be given as a String board. The i-th character of board will be '.' (a period) if the i-th cell is empty at the beginning, and it will be 'o' (lowercase letter o) if the i-th cell initially contains a checker. Assume that both girls play optimally. Return "YES" (quotes for clarity) if the first player wins the game and "NO" otherwise.

Notes

  • If there is a checker on the rightmost cell in the beginning of the game, it disappears instantly (before the first move is made), as if it were never there.
  • The rules of the game ensure that each cell contains at most one checker at any time, and that no checker can jump beyond the last cell.

Constraints

  • board will contain between 1 and 20 characters, inclusive.
  • Each character of board will be either '.' or 'o'.
Examples
0)
".o..."
Returns: "YES"

With only one checker it is pretty obvious who will win.

1)
"..o..o"
Returns: "YES"

Don't forget to ignore checkers on the rightmost cell.

2)
".o...ooo..oo.."
Returns: "NO"

Here one can jump the checker from cell 5 to cell 8.

3)
"......o.ooo.o......"
Returns: "YES"
4)
".o..o...o....o.....o"
Returns: "NO"

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

Coding Area

Language: C++17 · define a public class EllysCheckers with a public method string getWinner(string board) · 118 test cases · 2 s / 256 MB per case

Submitting as anonymous