Problem Statement |
| | Roxor is a 2-player game that is played with several piles of stones, numbered 0, 1, ..., n-1. To make a move, a player chooses three piles with numbers i, j, and k such that i < j, j <= k, and pile i has at least one stone in it. The player then removes one stone from pile i, and adds one stone to piles j and k. Note that j may equal k, and that two stones are added for each stone removed. Players make moves alternately until it is no longer possible to make a valid move. This will always happen eventually, and the last player to have moved is then declared the winner. See example 0 below for a description of an entire game.
You are said to have made a "winning move" in Roxor, if after making that move, you can eventually win no matter what the opponent does. Note that a winning move does not necessarily end the game immediately, but if you make only winning moves, you will win eventually.
For this task, you will be given a int[] piles, representing the number of stones in each pile within a game of Roxor. You must find i, j, k with i < j and j <= k such that removing one stone from pile i and adding one stone to piles j and k is a winning move. If there are multiple winning moves, you should choose one that minimizes i. If there is more than one of these, you should choose one that minimizes j. If there is still a tie, choose the one that minimizes k.
If there is at least one winning move, you should return {i, j, k} as described above. Otherwise, return {}.
|
| |
Definition |
| | | Class: | Roxor | | Method: | play | | Parameters: | int[] | | Returns: | int[] | | Method signature: | int[] play(int[] piles) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | piles will contain between 2 and 15 elements inclusive. |
| - | Each element of piles will be between 0 and 1000 inclusive. |
| - | At least one element of piles other than the last element will be larger than 0. |
| |
Examples |
| 0) | |
| | | Returns: { 2, 4, 5 } | You have 7 legal moves in this position:
{2, 3, 3}, {2, 3, 4}, {2, 3, 5}, {2, 4, 4}, {2, 4, 5}, {2, 5, 5}, and {4, 5, 5}.
If you make the move, {2, 4, 5}, the piles become {0, 0, 0, 0, 2, 101}.
Your opponent then has to make the move, {4, 5, 5}, which makes the piles become {0, 0, 0, 0, 1, 103}.
Finally, you can make the move, {4, 5, 5}, so the piles become {0, 0, 0, 0, 0, 105}.
Your opponent now has no legal moves, so you have won. Thus, {2, 4, 5} is a winning move. |
|
|
| 1) | |
| | {1000, 1000, 1000, 1000, 1000} |
| Returns: { } | | Your opponent can always beat you from this position by simply copying your moves. This will ensure that there is always an even number of stones in each pile at the beginning of your turn. As such, you will never take the last stone from any pile, and therefore, you cannot win. |
|
|
| 2) | |
| | |
| 3) | |
| | {14, 301, 391, 410, 511, 681, 58, 259, 981, 81, 5, 42, 251, 401, 120} |
| Returns: { 2, 5, 14 } | |
|