Connection Status:
Competition Arena > SplitStoneGame

SplitStoneGame

SRM 619 · 2013-12-22 · by hyy5159

SRM 619 · 2013-12-22 · by hyy5159 · Dynamic Programming
Class Name: SplitStoneGame
Return Type: String
Method Name: winOrLose
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Shiny likes to play games. Her favorite games are games with pebbles (small stones). Today, she is playing such a game with her friend Lucy.


Initially, there are N piles of stones. You are given a int[] number with N elements. Each element of number is the number of stones in one of the piles.


The players take alternating turns. Shiny plays first. In each turn, the current player must:

  1. Choose a pile X that has at least two stones.
  2. Split the chosen pile X into two non-empty parts A and B. (The parts can have arbitrary sizes, as long as both are non-empty.)
  3. Choose two piles Y and Z. (Y and Z must be different non-empty piles other than X.)
  4. Add all stones from A to the pile Y, and all stones from B to the pile Z.


For example, if the current piles are {1, 2, 50}, the current player could:

  1. Choose the pile with 50 stones as X.
  2. Split it into two parts with 25 stones each.
  3. Choose the other two piles (the ones with 1 and 2 stones) to be Y and Z.
  4. Add all stones from A to the pile Y, and all stones from B to the pile Z. At the end of the turn, there are two piles of stones: one with 26 and one with 27 stones.


The player who cannot make a valid move loses the game. Assume that both players play the game optimally. Return the String "WIN" (quotes for clarity) if Shiny wins the game, and "LOSE" if she does not.

Constraints

  • number will contain between 1 and 50 elements, inclusive.
  • Each element of number will be between 1 and 50, inclusive.
Examples
0)
{1, 1, 1}
Returns: "LOSE"

Shiny can't choose a pile X that has at least two stones, so she loses.

1)
{2, 2}
Returns: "LOSE"

After Shiny chooses one of the piles as X and splits it into two piles with one stone each, she is unable to choose Y and Z, because there is only one pile left to choose from at the moment. Thus, she cannot make a valid move and therefore she loses the game.

2)
{1, 1, 2}
Returns: "WIN"

Shiny can choose the last pile as X, split it into 1+1 stone, and add those stones to the other two piles. This is a valid move that produces two piles with two stones each, and it is now Lucy's turn. As we saw in Example 1, Lucy now has no valid move left, thus she loses the game and Shiny is the winner.

3)
{1, 2, 3, 4, 3, 2, 2, 4, 3, 1, 4, 4, 1, 2, 4, 4, 1, 4, 3, 1, 4, 2, 1}
Returns: "WIN"
4)
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 9, 1, 3, 1, 1, 1, 1, 1}
Returns: "LOSE"

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

Coding Area

Language: C++17 · define a public class SplitStoneGame with a public method string winOrLose(vector<int> number) · 121 test cases · 2 s / 256 MB per case

Submitting as anonymous