Connection Status:
Competition Arena > TheXGame

TheXGame

SRM 304 · 2006-05-27 · by dgoodman

SRM 304 · 2006-05-27 · by dgoodman · Brute Force, Math
Class Name: TheXGame
Return Type: int
Method Name: firstMove
Arg Types: (string)
Problem Statement

Problem Statement

The X game is a two person game. The board is just a sequence of boxes, some of which are randomly marked with an X before the game begins. The two players alternate turns. On each turn the player whose turn it is marks 1 or more previously unmarked boxes. All her marks on the turn must be adjacent (with no wrap-around at the ends) to each other. The game continues until all the boxes are marked.

The number of points scored by a player on his turn is equal to the number of boxes he marked on that turn times a multiplier. The multiplier gets bigger and bigger as the game goes on:

  • first turn Player 1 multiplier=0
  • second turn Player 2 multiplier=1
  • third turn Player 1 multiplier=2
  • fourth turn Player 2 multiplier=4
  • fifth turn Player 1 multiplier=8
  • ... etc.
A players wins the game if the sum of the points scored on all her turns is strictly greater than her opponent's sum. Create a class TheXGame that contains a method firstMove that is given a String board indicating how many boxes there are, and which ones are marked with X before the game begins. The method returns the smallest number of Xs that the first player can mark on her first turn (somewhere on the board) that will allow her to win the game if she plays optimally thereafter. If no first move puts the first player into a winning position, the method returns -1.

Constraints

  • board will contain between 1 and 50 characters, inclusive.
  • Each character in board will be 'X' or '-'.
  • board will contain at least one '-'.
Examples
0)
"X---X-X-"
Returns: 1

There are 8 boxes, 3 of them marked with X before the game begins. The first player can win by marking the third box. After that each player will only be able to mark one box one each turn, and the scoring will be: P1: 0*1; P2: 1*1; P1: 2*1; P2: 4*1; P1: 8*1 and player 1 wins with a score of 10 versus player 2's score of 5.

1)
"----"
Returns: 2

The first player can win by marking the middle two spaces. After that, each player will mark one on each turn so player 1 wins by a score of 2 to 1. If the first player just marked one of the middle spaces, then the second player would mark 2 and the first player would mark 1 leaving the game tied (2 to 2).

2)
"--XXX"
Returns: -1

The first player cannot win by marking both of them, since her first turn multiplier is 0!

3)
"--------X-----X----X"
Returns: 3
4)
"X-----X-------X---------X-----------"
Returns: -1

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

Coding Area

Language: C++17 · define a public class TheXGame with a public method int firstMove(string board) · 31 test cases · 2 s / 256 MB per case

Submitting as anonymous