NimForK
SRM 419 · 2008-09-24 · by andrewzta
Problem Statement
The game of NimForK is played as follows. There are k players sitting in a circle numbered 1 through k in clockwise order. Starting with player 1, the players take turns making moves in clockwise order. In the center of the circle, there is a pile that initially contains n stones.
When a player takes a turn, he must remove some number of stones from the pile. The number of stones he is allowed to take is dependent on the size of the pile. You are given a
Each player uses the following strategy to determine how many stones he will remove during his turn:
- If there is a move that ensures he will win regardless of how the other players move for the rest of the game, he will make that move. If there are several such moves, he will randomly choose one of them with equal probability. In other words, pretend that the other players are not following the strategy described here, and that it's possible for them to make any valid moves during their turns. If there is a move that will guarantee him to win in that scenario, he will make that move.
- If there is no such move, then assuming that the other players are following this same strategy, he will make a move that gives him a non-zero chance of winning. If there are several such moves, he will randomly choose one of them with equal probability.
- If neither of the above moves are possible, he will randomly choose any valid move with equal probability.
If there are no valid moves possible during a player's turn, but there are still stones left in the pile, the game ends and nobody wins.
Return a
Constraints
- n will be between 1 and 50, inclusive.
- k will be between 2 and 20, inclusive.
- moves will contain exactly n elements.
- Each element of moves will have length between 0 and 50, inclusive.
- Each element of moves will contain a space separated list of integers.
- Each integer in moves[i] will be between 1 and i + 1, inclusive.
- All integers in moves[i] will be distinct.
8
2
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3", "1 2 3", "1 2 3", "1 2 3"}
Returns: {2 }
This is a standard variation of nim where each player is allowed to take 1, 2 or 3 stones. In a game for two players the first player wins if and only if the number of stones in the initial pile is not divisible by 4.
7
2
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3", "1 2 3", "1 2 3"}
Returns: {1 }
Same as the previous example. Here 7 is not divisible by 4, so the first player wins.
5
3
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3"}
Returns: {2, 3 }
When there are three players and five stones, the first player cannot win. However, he decides who would win by taking either 1 stone (in this case the third player would win) or 2 or 3 stones (in this case the second player would win).
6
3
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3", "1 2 3"}
Returns: {1, 3 }
Here the first player cannot force his victory. His options are: take 1 stone - in this case the second player would decide whether the third player, or the first player would win (see previous example); take 2 stones - in this case the third player would win; take 3 stones - in this case the second player would win. He chooses the first option because in this case he can win with non-zero probability.
1
20
{""}
Returns: { }
A delicate case. No player can make a move, so nobody can take the last stone. Therefore nobody can win.
46
15
{"", "1", "", "3", "1 3 4 5", "1 2 4 5", "3 4 5 6", "7", "1 2 3 5 7 8 9", "2 3 5", "1 3 6 8 10 11", "12", "1 2 4 7 9 12 13", "2 3 6 7 8 9 10 11 14", "1 5 12", "4 5 6 7 9", "4 5 8 11 13", "1 2 6 11 13 14 15 16 17", "2 7 9 10 11 12 14 15 16 17", "2 9", "1 2 3 4 7 9 10 12 13 15 16 17 18 19 20", "1 6 8 9 11 12 13 14 15 17 18 19 20", "3 4 5 6 8 10 11 13 14 16 17 20 22 23", "3 5 11 13 16 22 23", "3 6 7 8 9 10 11 12 14 16 17 19 21 22 23 25", "2 3 8 20 21", "2 3 4 7 8 10 11 15 21 25", "1 2 5 7 9 10 11 12 14 18 24 27 28", "9 22", "2 5 8 10 14 21 26 30", "3 4 5 6 7 9 10 11 16 20 22 23 29 30", "7 12 18 19 20 25 29 32", "1 2 3 5 8 9 11 13 16 20 25 26 30", "3 16 21 33", "2 3 4 5 12 14 16 18 19 20 21 22 23 25 26 29 33", "2 4 8 9 10 13 14 17 18 20 23 26 27 30 33 34 35", "4 5 13 23 31 32 34 37", "4 5 7 9 10 14 16 21 25 31 37 38", "3 10 11 12 15 21 22 23 24 27 29 30 34 35 36 37 38", "1 2 5 6 28 29 32 33 38", "11 17 18 20 22 27 30 31 38", "23 37 38", "2 4 5 8 9 17 18 19 21 25 30 31 32 33 36 38 41", "1 4 5 6 12 15 16 19 23 24 25 29 30 32 34 36 39", "14 17 22 32 33 35 39 41 45", "1 2 3 4 5 8 10 14 18 19 21 22 24 28 29 34 36 38 41"}
Returns: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }
{
Submissions are judged against all 124 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NimForK with a public method vector<int> winners(int n, int k, vector<string> moves) · 124 test cases · 2 s / 256 MB per case