Connection Status:
Competition Arena > StoneGameStrategist

StoneGameStrategist

SRM 309 · 2006-06-28 · by _efer_

SRM 309 · 2006-06-28 · by _efer_ · Math
Class Name: StoneGameStrategist
Return Type: String
Method Name: play
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You and a friend are playing a game in which you take turns removing stones from piles. Initially, every pile has at least as many stones as the pile to its left. This property must be maintained throughout the game. On each turn, you remove one or more stones from a single pile. You and your friend alternate turns until it is no longer possible to make a valid move. The last player to have made a move wins the game. Note that if you remove all the stones from a pile, it is still considered a pile.

You are said to have made a "winning move" if after making that move, you can eventually win no matter what your friend does. You are given a int[] piles representing the number of stones in each pile from left to right. It is your turn to move. Find a winning move and return it as a String formatted as "TAKE s STONES FROM PILE k" (quotes for clarity only), where s and k (a 0-based index) are each integers with no leading zeros. If there are multiple winning moves, choose the one that minimizes s. If there is still a tie, choose the one that minimizes k. If no winning move is possible, return the String "YOU LOSE" (quotes for clarity only).

Constraints

  • piles will contain between 1 and 50 elements, inclusive.
  • Each element of piles will be between 1 and 1000, inclusive.
  • piles will be sorted in non-descending order.
Examples
0)
{6,6}
Returns: "YOU LOSE"

You can't win this game. Your friend will force you to take stones from the first pile at each turn, and then mirror your move by taking the same number of stones from the second pile.

1)
{6,12}
Returns: "TAKE 6 STONES FROM PILE 1"

If you take 6 stones from the second pile, you can follow the strategy outlined above.

2)
{3,6,6}
Returns: "TAKE 3 STONES FROM PILE 0"
3)
{3,5,9,11,16}
Returns: "TAKE 2 STONES FROM PILE 0"
4)
{2,5,7,11,13,18}
Returns: "TAKE 2 STONES FROM PILE 1"

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

Coding Area

Language: C++17 · define a public class StoneGameStrategist with a public method string play(vector<int> piles) · 149 test cases · 2 s / 256 MB per case

Submitting as anonymous