Statistics

Problem Statement for "EllysCheckers"

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.

Definition

Class:
EllysCheckers
Method:
getWinner
Parameters:
String
Returns:
String
Method signature:
String getWinner(String board)
(be sure your method is public)

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

  1. ".o..."

    Returns: "YES"

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

  2. "..o..o"

    Returns: "YES"

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

  3. ".o...ooo..oo.."

    Returns: "NO"

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

  4. "......o.ooo.o......"

    Returns: "YES"

  5. ".o..o...o....o.....o"

    Returns: "NO"

  6. "......."

    Returns: "NO"

  7. "."

    Returns: "NO"

  8. "o"

    Returns: "NO"

  9. "oooooooooooooooooooo"

    Returns: "NO"

  10. "ooo.ooo.ooo.ooo.ooo."

    Returns: "NO"

  11. "o..ooo"

    Returns: "NO"

  12. "oooo...oo"

    Returns: "YES"

  13. "oo.o......."

    Returns: "NO"

  14. ".ooooo"

    Returns: "NO"

  15. "oooooo..oo.oo..ooooo"

    Returns: "YES"

  16. ".o.o...oooooo..."

    Returns: "YES"

  17. ".o..o....."

    Returns: "YES"

  18. "ooooo"

    Returns: "NO"

  19. ".o."

    Returns: "YES"

  20. "..o.........."

    Returns: "NO"

  21. "o.o.o.oooo."

    Returns: "NO"

  22. "oo....o.....ooo"

    Returns: "NO"

  23. "...oo..oooo.oooo..o"

    Returns: "YES"

  24. "ooooooooooo.oo.o"

    Returns: "YES"

  25. "....o.........."

    Returns: "NO"

  26. "o......."

    Returns: "YES"

  27. "o.o"

    Returns: "NO"

  28. "oo"

    Returns: "YES"

  29. "..o...oo.o"

    Returns: "NO"

  30. "...oo.."

    Returns: "YES"

  31. "o."

    Returns: "YES"

  32. "....o."

    Returns: "YES"

  33. "...ooo.o"

    Returns: "YES"

  34. "oooooo.oo.o"

    Returns: "NO"

  35. "oooooooooooooooo"

    Returns: "NO"

  36. ".o..oo.o"

    Returns: "YES"

  37. "ooo.oo.o"

    Returns: "YES"

  38. "..oooo...o.ooo"

    Returns: "YES"

  39. "........oo..o......"

    Returns: "YES"

  40. "o......o.."

    Returns: "YES"

  41. "..oooo.o...oo.o..o"

    Returns: "NO"

  42. "oo.o.o.ooo..o.o.o"

    Returns: "YES"

  43. ".......o........o.."

    Returns: "YES"

  44. "o...."

    Returns: "NO"

  45. "oooooooooooo"

    Returns: "NO"

  46. "o.oooooooooooooooooo"

    Returns: "NO"

  47. "......o.."

    Returns: "NO"

  48. "oooooooooo.oooo.oo"

    Returns: "NO"

  49. "oo..ooo.o...oooo.."

    Returns: "NO"

  50. "ooooooooo"

    Returns: "NO"

  51. "oo.ooo"

    Returns: "NO"

  52. ".o.oo.oooooo.o.."

    Returns: "NO"

  53. ".o..o...o...o."

    Returns: "YES"

  54. ".o"

    Returns: "NO"

  55. ".o..ooo.o"

    Returns: "NO"

  56. ".......o...oo..."

    Returns: "YES"

  57. ".o.o"

    Returns: "NO"

  58. "o.oo..ooo..o...o"

    Returns: "NO"

  59. "ooooooo"

    Returns: "YES"

  60. "...........o.o.."

    Returns: "NO"

  61. ".o.o..oo"

    Returns: "YES"

  62. "oooooooo"

    Returns: "NO"

  63. ".o.oo.oooooo"

    Returns: "NO"

  64. "......oo.o......."

    Returns: "NO"

  65. "oooo.ooooo.o"

    Returns: "NO"

  66. "o....o.......o.oo"

    Returns: "YES"

  67. ".......oo."

    Returns: "YES"

  68. "o...oo.oo"

    Returns: "NO"

  69. "ooooooooooo"

    Returns: "YES"

  70. "oooooo"

    Returns: "YES"

  71. "........o..."

    Returns: "YES"

  72. "..o"

    Returns: "NO"

  73. "o.oo....o.o"

    Returns: "YES"

  74. ".o................."

    Returns: "YES"

  75. "ooo"

    Returns: "YES"

  76. ".o.oo.ooo.o."

    Returns: "NO"

  77. ".......o."

    Returns: "YES"

  78. "...o...ooo..o.."

    Returns: "YES"

  79. ".....o......"

    Returns: "NO"

  80. "oooooooooo"

    Returns: "YES"

  81. ".oo"

    Returns: "YES"

  82. ".oo.oo.oooo..o.o.."

    Returns: "NO"

  83. ".oooooooooo.ooo.oo.o"

    Returns: "NO"

  84. "..ooooo"

    Returns: "NO"

  85. "oooooooooooo...oo.oo"

    Returns: "NO"

  86. "o.ooooooo.ooooooo"

    Returns: "NO"

  87. "....o...o.."

    Returns: "NO"

  88. "oo."

    Returns: "YES"

  89. "..o.o......."

    Returns: "NO"

  90. "o.oo....o..o.o...o.."

    Returns: "YES"

  91. "....oo.oo.....o"

    Returns: "NO"

  92. "..oo.o"

    Returns: "YES"

  93. ".o..o...o....oo....o"

    Returns: "YES"

  94. "oooo..ooo..oo..oo..o"

    Returns: "NO"

  95. "ooooooooooooooooooo."

    Returns: "NO"

  96. ".o...oooo..oo.."

    Returns: "NO"

  97. "oooooooooooooooooo"

    Returns: "YES"

  98. ".o.."

    Returns: "NO"

  99. "ooooooooooooooooooo"

    Returns: "YES"

  100. "o.o....ooo.o.o..o."

    Returns: "NO"

  101. "o.."

    Returns: "NO"

  102. "o.oo.o.o..o..o..o..."

    Returns: "NO"

  103. "o.oo..o.o..o.o..o.o."

    Returns: "NO"

  104. "oooo.oooo.oooo.oooo."

    Returns: "NO"

  105. "ooooo.."

    Returns: "NO"

  106. ".."

    Returns: "NO"

  107. "ooooooo.oooooooooooo"

    Returns: "NO"

  108. ".o.o...ooo..oo.."

    Returns: "NO"

  109. "oooooo.ooooooooooooo"

    Returns: "YES"

  110. "ooo."

    Returns: "NO"

  111. "o.o."

    Returns: "NO"

  112. "oooo."

    Returns: "NO"

  113. "oo..o...ooo."

    Returns: "NO"

  114. "oooooo............"

    Returns: "YES"

  115. "o.o.o."

    Returns: "YES"

  116. "oo..o.o.ooo.o..o"

    Returns: "NO"

  117. "o..."

    Returns: "YES"

  118. "..o.."

    Returns: "NO"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: