Problem Statement
A two-player game is played with N = B-A+1 piles of tokens. The piles are numbered from A to B, inclusive. Initially, pile number i contains exactly 2^i tokens.
(E.g., if A=2 and B=5, there are four piles containing 4, 8, 16, and 32 tokens at the beginning of the game.)
Before the game the players also choose a positive integer K not exceeding N.
The players take alternating turns. During each turn the current player must choose exactly K non-empty piles and then remove exactly one token from each of the chosen piles. The player unable to make a valid move loses the game.
You are given A, B, and K. Determine whether the starting position of this game is winning or losing for the player who plays first.
If the position is losing, return {-2}.
If the position is winning and B <= 7, return any one possible winning first move: an increasing sequence of K pile numbers the first player should choose in the first turn of the game.
If the position is winning and B = 47 and K = 42, also return any one possible winning first move.
In all other cases in which the position is winning, return {-1}.
Definition
- Class:
- PowerfulGame
- Method:
- solve
- Parameters:
- int, int, int
- Returns:
- int[]
- Method signature:
- int[] solve(int A, int B, int K)
- (be sure your method is public)
Notes
- A position is winning for the player whose turn it is if that player has a strategy that guarantees a win, regardless of what plays the opponent makes. Similarly, a position is losing if the opponent has such a strategy.
- It can be shown that each position of this game is either winning or losing, but never both.
- Remember that if you are returning a winning move, the pile numbers must be in increasing order.
Constraints
- 0 <= A <= B <= 100.
- K will be between 1 and the number of piles, inclusive.
Examples
0
6
1
Returns: {4 }
With K=1 the players are simply removing any one token at a time.
4
7
2
Returns: {-2 }
0
8
3
Returns: {-1 }
0
3
2
Returns: {1, 2 }
In this starting position there are two possible winning moves: the first player can choose either {0, 3} or {1, 2}. The first choice will lead to piles with {0, 2, 4, 7} tokens, the second choice produces piles with {1, 1, 3, 8} tokens. If the first player makes any other starting move, the second player will have a way to win the game.
0
0
1
Returns: {0 }
0
1
1
Returns: {0 }
0
1
2
Returns: {0, 1 }
1
1
1
Returns: {-2 }
0
2
1
Returns: {0 }
0
2
2
Returns: {0, 2 }
0
2
3
Returns: {0, 1, 2 }
1
2
1
Returns: {-2 }
1
2
2
Returns: {-2 }
2
2
1
Returns: {-2 }
0
3
1
Returns: {0 }
0
3
2
Returns: {1, 2 }
0
3
3
Returns: {0, 2, 3 }
0
3
4
Returns: {0, 1, 2, 3 }
1
3
1
Returns: {-2 }
1
3
2
Returns: {-2 }
1
3
3
Returns: {-2 }
2
3
1
Returns: {-2 }
2
3
2
Returns: {-2 }
3
3
1
Returns: {-2 }
0
4
1
Returns: {0 }
0
4
2
Returns: {0, 4 }
0
4
3
Returns: {0, 3, 4 }
0
4
4
Returns: {0, 2, 3, 4 }
0
4
5
Returns: {0, 1, 2, 3, 4 }
1
4
1
Returns: {-2 }
1
4
2
Returns: {-2 }
1
4
3
Returns: {-2 }
1
4
4
Returns: {-2 }
2
4
1
Returns: {-2 }
2
4
2
Returns: {-2 }
2
4
3
Returns: {-2 }
3
4
1
Returns: {-2 }
3
4
2
Returns: {-2 }
4
4
1
Returns: {-2 }
0
5
1
Returns: {0 }
0
5
2
Returns: {0, 5 }
0
5
3
Returns: {0, 4, 5 }
0
5
4
Returns: {0, 3, 4, 5 }
0
5
5
Returns: {0, 2, 3, 4, 5 }
0
5
6
Returns: {0, 1, 2, 3, 4, 5 }
1
5
1
Returns: {-2 }
1
5
2
Returns: {-2 }
1
5
3
Returns: {-2 }
1
5
4
Returns: {-2 }
1
5
5
Returns: {-2 }
2
5
1
Returns: {-2 }
2
5
2
Returns: {-2 }
2
5
3
Returns: {-2 }
2
5
4
Returns: {-2 }
3
5
1
Returns: {-2 }
3
5
2
Returns: {-2 }
3
5
3
Returns: {-2 }
4
5
1
Returns: {-2 }
4
5
2
Returns: {-2 }
5
5
1
Returns: {-2 }
0
6
1
Returns: {4 }
0
6
2
Returns: {0, 6 }
0
6
3
Returns: {0, 5, 6 }
0
6
4
Returns: {0, 4, 5, 6 }
0
6
5
Returns: {0, 3, 4, 5, 6 }
0
6
6
Returns: {0, 2, 3, 4, 5, 6 }
0
6
7
Returns: {0, 1, 2, 3, 4, 5, 6 }
1
6
1
Returns: {-2 }
1
6
2
Returns: {-2 }
1
6
3
Returns: {-2 }
1
6
4
Returns: {-2 }
1
6
5
Returns: {-2 }
1
6
6
Returns: {-2 }
2
6
1
Returns: {-2 }
2
6
2
Returns: {-2 }
2
6
3
Returns: {-2 }
2
6
4
Returns: {-2 }
2
6
5
Returns: {-2 }
3
6
1
Returns: {-2 }
3
6
2
Returns: {-2 }
3
6
3
Returns: {-2 }
3
6
4
Returns: {-2 }
4
6
1
Returns: {-2 }
4
6
2
Returns: {-2 }
4
6
3
Returns: {-2 }
5
6
1
Returns: {-2 }
5
6
2
Returns: {-2 }
6
6
1
Returns: {-2 }
0
7
1
Returns: {0 }
0
7
2
Returns: {0, 7 }
0
7
3
Returns: {0, 6, 7 }
0
7
4
Returns: {0, 5, 6, 7 }
0
7
5
Returns: {0, 4, 5, 6, 7 }
0
7
6
Returns: {0, 3, 4, 5, 6, 7 }
0
7
7
Returns: {0, 2, 3, 4, 5, 6, 7 }
0
7
8
Returns: {0, 1, 2, 3, 4, 5, 6, 7 }
1
7
1
Returns: {-2 }
1
7
2
Returns: {-2 }
1
7
3
Returns: {-2 }
1
7
4
Returns: {-2 }
1
7
5
Returns: {-2 }
1
7
6
Returns: {-2 }
1
7
7
Returns: {-2 }
2
7
1
Returns: {-2 }
2
7
2
Returns: {-2 }
2
7
3
Returns: {-2 }
2
7
4
Returns: {-2 }
2
7
5
Returns: {-2 }
2
7
6
Returns: {-2 }
3
7
1
Returns: {-2 }
3
7
2
Returns: {-2 }
3
7
3
Returns: {-2 }
3
7
4
Returns: {-2 }
3
7
5
Returns: {-2 }
4
7
1
Returns: {-2 }
4
7
2
Returns: {-2 }
4
7
3
Returns: {-2 }
4
7
4
Returns: {-2 }
5
7
1
Returns: {-2 }
5
7
2
Returns: {-2 }
5
7
3
Returns: {-2 }
6
7
1
Returns: {-2 }
6
7
2
Returns: {-2 }
7
7
1
Returns: {-2 }
0
54
36
Returns: {-1 }
0
67
66
Returns: {-1 }
26
58
27
Returns: {-2 }
4
93
1
Returns: {-2 }
31
42
6
Returns: {-2 }
55
81
8
Returns: {-2 }
0
75
57
Returns: {-1 }
0
39
23
Returns: {-1 }
44
85
16
Returns: {-2 }
0
13
2
Returns: {-1 }
0
55
33
Returns: {-1 }
33
78
42
Returns: {-2 }
22
38
16
Returns: {-2 }
0
23
22
Returns: {-1 }
0
45
23
Returns: {-1 }
73
77
4
Returns: {-2 }
0
48
17
Returns: {-1 }
29
75
41
Returns: {-2 }
0
35
17
Returns: {-1 }
72
86
8
Returns: {-2 }
3
10
2
Returns: {-2 }
0
43
28
Returns: {-1 }
49
55
5
Returns: {-2 }
0
42
41
Returns: {-1 }
2
49
14
Returns: {-2 }
28
53
6
Returns: {-2 }
26
69
7
Returns: {-2 }
0
26
17
Returns: {-1 }
0
59
29
Returns: {-1 }
0
9
2
Returns: {-1 }
0
56
3
Returns: {-1 }
0
26
7
Returns: {-1 }
0
72
73
Returns: {-1 }
2
81
23
Returns: {-2 }
0
28
21
Returns: {-1 }
10
14
1
Returns: {-2 }
8
57
6
Returns: {-2 }
0
47
16
Returns: {-1 }
69
87
18
Returns: {-2 }
35
83
37
Returns: {-2 }
44
71
4
Returns: {-2 }
0
61
59
Returns: {-1 }
0
47
39
Returns: {-1 }
3
26
15
Returns: {-2 }
59
92
28
Returns: {-2 }
67
81
13
Returns: {-2 }
32
45
13
Returns: {-2 }
0
40
11
Returns: {-1 }
3
68
59
Returns: {-2 }
36
67
13
Returns: {-2 }
0
47
42
Returns: {0, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47 }