Problem Statement
Alice and Bob play a game with a pile of stones. Initially, there are n stones in the pile. The players take alternating turns, Alice goes first.
You are given two
In each turn, the current player must remove some stones from the pile. The number of removed stones must be equal to one of the player's allowed moves. If a player cannot take a valid turn, they lose the game.
Assume that both Alice and Bob play the game optimally. Return "Alice" if Alice wins, or "Bob" if Bob wins. In other words, return "Alice" if and only if the first player has a winning strategy for the given n, a, and b.Definition
- Class:
- PartisanGame
- Method:
- getWinner
- Parameters:
- int, int[], int[]
- Returns:
- String
- Method signature:
- String getWinner(int n, int[] a, int[] b)
- (be sure your method is public)
Constraints
- n will be between 0 and 1,000,000,000, inclusive.
- all elements of a will be distinct.
- all elements of b will be distinct.
- all elements of a will be between 1 and 5, inclusive.
- all elements of b will be between 1 and 5, inclusive.
Examples
1
{1, 2, 3, 4}
{1, 2, 5}
Returns: "Alice"
1
{1, 2, 3, 4, 5}
{2}
Returns: "Alice"
2
{4}
{2, 3}
Returns: "Bob"
3
{5}
{1, 4, 5}
Returns: "Bob"
4
{5}
{4, 5}
Returns: "Bob"
5
{1, 2, 3, 4}
{1, 3, 4}
Returns: "Alice"
4
{1, 2, 3, 4, 5}
{1, 3}
Returns: "Alice"
8
{1, 5}
{3, 4}
Returns: "Bob"
20
{1, 3, 4, 5}
{1, 2, 3, 4, 5}
Returns: "Bob"
15
{1, 3}
{1, 4}
Returns: "Bob"
15
{1, 2, 4, 5}
{3, 4}
Returns: "Alice"
894
{3, 4}
{4, 5}
Returns: "Alice"
19135
{3, 4}
{4}
Returns: "Alice"
828191
{2}
{1, 5}
Returns: "Bob"
37
{1, 2, 4}
{3, 5}
Returns: "Alice"
343
{4}
{1, 2, 3, 5}
Returns: "Bob"
1300
{5}
{1, 2, 3, 4}
Returns: "Bob"
18452
{1, 2}
{3, 4, 5}
Returns: "Bob"
380057
{1, 4, 5}
{2, 3}
Returns: "Alice"
158260522
{2, 4}
{4}
Returns: "Alice"
167959139
{1, 2, 3, 4}
{1, 2, 5}
Returns: "Alice"
641009859
{1, 2, 3, 4, 5}
{2}
Returns: "Alice"
524125987
{4}
{2, 3}
Returns: "Bob"
702209411
{5}
{1, 4, 5}
Returns: "Bob"
585325539
{5}
{4, 5}
Returns: "Bob"
941492387
{1, 2, 3, 4, 5}
{1, 3}
Returns: "Alice"
58376259
{1, 2, 3, 4}
{1, 3, 4}
Returns: "Alice"
824608515
{1, 2, 5}
{1, 3, 5}
Returns: "Alice"
2691939
{5}
{1, 5}
Returns: "Bob"
802030518
{1, 5}
{3, 4}
Returns: "Bob"
685146646
{2, 5}
{1, 3, 4}
Returns: "Bob"
863230070
{2, 4}
{1, 4}
Returns: "Alice"
41313494
{2, 3, 4, 5}
{5}
Returns: "Alice"
219396918
{1, 3}
{1, 3, 5}
Returns: "Bob"
102513046
{1, 5}
{1, 3}
Returns: "Bob"
985629174
{1, 4, 5}
{2, 3, 5}
Returns: "Bob"
458679894
{2, 4}
{1, 4}
Returns: "Alice"
341796022
{2, 3, 4, 5}
{3, 4, 5}
Returns: "Alice"
167959139
{1, 2, 3, 4}
{5}
Returns: "Alice"
641009859
{2}
{1, 3, 4, 5}
Returns: "Bob"
524125987
{4}
{1, 2, 3, 5}
Returns: "Bob"
702209411
{5}
{1, 2, 3, 4}
Returns: "Bob"
585325539
{5}
{1, 2, 3, 4}
Returns: "Bob"
941492387
{1, 3}
{2, 4, 5}
Returns: "Bob"
58376259
{1, 2, 3, 4}
{5}
Returns: "Alice"
824608515
{1, 2, 5}
{3, 4}
Returns: "Alice"
2691939
{5}
{1, 2, 3, 4}
Returns: "Bob"
802030518
{1, 5}
{2, 3, 4}
Returns: "Bob"
685146646
{2, 5}
{1, 3, 4}
Returns: "Bob"
863230070
{2, 4}
{1, 3, 5}
Returns: "Bob"
41313494
{2, 3, 4, 5}
{1}
Returns: "Alice"
219396918
{1, 3}
{2, 4, 5}
Returns: "Bob"
102513046
{1, 5}
{2, 3, 4}
Returns: "Bob"
985629174
{1, 4, 5}
{2, 3}
Returns: "Alice"
458679894
{2, 4}
{1, 3, 5}
Returns: "Bob"
341796022
{2, 3, 4, 5}
{1}
Returns: "Alice"
1000000000
{2, 3}
{4, 5}
Returns: "Alice"
7
{3, 4}
{4}
Returns: "Alice"
Alice should take 4 stones from the pile. This will leave a pile of only 3 stones. In that situation, Bob has no valid move. (His only allowed move is 4, but it is not possible to remove 4 stones from a pile of only 3 stones.) Thus, Bob loses the game.
10
{1}
{4, 3, 2}
Returns: "Bob"
One winning strategy for Bob is to always take 4 stones. If Bob follows this strategy, Alice will lose the game during her third turn.
104982
{2, 3, 4, 5}
{2, 5}
Returns: "Alice"
999999999
{4}
{5}
Returns: "Bob"
1000000000
{1,2,3,4,5}
{1,2,3,4,5}
Returns: "Alice"
20
{1 }
{1 }
Returns: "Bob"
10
{2 }
{5 }
Returns: "Alice"
6
{1, 2, 3, 4, 5 }
{1, 2, 3, 4, 5 }
Returns: "Bob"
1000000000
{1, 2, 3, 4 }
{1, 2, 3, 4, 5 }
Returns: "Bob"
1006
{5 }
{5 }
Returns: "Alice"
8
{1, 3, 4 }
{4 }
Returns: "Alice"
504
{2 }
{5 }
Returns: "Bob"
1
{5 }
{4 }
Returns: "Bob"
6
{1, 2 }
{3 }
Returns: "Alice"
100794
{3, 5 }
{1, 5 }
Returns: "Bob"
14403
{3 }
{3, 5 }
Returns: "Bob"
536870912
{1, 2, 5 }
{3, 4, 5 }
Returns: "Alice"
3000
{1, 2 }
{1, 2 }
Returns: "Bob"
999999999
{1, 3 }
{2, 3, 4, 5 }
Returns: "Bob"
999999900
{2 }
{5 }
Returns: "Alice"
121
{3, 4 }
{4 }
Returns: "Alice"
999999990
{1, 2, 3, 4, 5 }
{1, 2, 3, 4, 5 }
Returns: "Bob"
10
{ }
{1 }
Returns: "Bob"
140512
{3, 4 }
{2 }
Returns: "Alice"
0
{1, 2, 3, 4, 5 }
{1, 2, 3, 4, 5 }
Returns: "Bob"
104982
{ }
{2, 5 }
Returns: "Bob"
1000000000
{1, 2, 3, 4, 5 }
{1, 2, 3, 4, 5 }
Returns: "Alice"
1000000000
{1, 2 }
{1, 3 }
Returns: "Alice"
7002
{2 }
{5 }
Returns: "Alice"
144108929
{1 }
{1, 3 }
Returns: "Alice"
433039488
{1, 4, 5 }
{1, 2 }
Returns: "Bob"
999999999
{1 }
{1, 3 }
Returns: "Alice"
999999997
{1, 3 }
{2, 3, 4 }
Returns: "Alice"
1808
{1, 5 }
{1, 4 }
Returns: "Bob"
36288000
{1, 2, 5 }
{3, 4, 5 }
Returns: "Alice"
3
{5 }
{ }
Returns: "Bob"
1
{2, 4, 5 }
{1, 2, 3 }
Returns: "Bob"
605
{5 }
{1, 2, 3, 4, 5 }
Returns: "Bob"
14405
{5 }
{1, 2, 3, 4, 5 }
Returns: "Bob"
2520
{2, 3, 4, 5 }
{2, 5 }
Returns: "Alice"
13
{5 }
{5 }
Returns: "Bob"
123
{4 }
{3 }
Returns: "Alice"
3
{1 }
{1 }
Returns: "Alice"
17724120
{1, 2, 3, 5 }
{1, 2, 4 }
Returns: "Alice"
1200007
{1 }
{1 }
Returns: "Alice"
1000080
{4 }
{3 }
Returns: "Alice"
72
{2, 3 }
{1 }
Returns: "Alice"
987654321
{1, 3, 5 }
{1, 2, 4 }
Returns: "Bob"
162698
{4 }
{3 }
Returns: "Alice"
1234567
{1, 4, 5 }
{1, 3, 4, 5 }
Returns: "Alice"
700000004
{3 }
{4 }
Returns: "Alice"
2162161
{2, 3, 4, 5 }
{5 }
Returns: "Alice"
15001
{2, 3, 4, 5 }
{2, 4 }
Returns: "Alice"
7
{1 }
{2, 3, 5 }
Returns: "Bob"
283274026
{1 }
{2 }
Returns: "Alice"
100002
{3, 4 }
{4 }
Returns: "Alice"