Problem Statement |
| | Nim is a game in which two players take turns removing stones from heaps. On each turn, a player must choose a single heap and remove one or more stones from that heap. The player who takes the last stone wins.
Alice and Bob are bored with playing Nim over and over again, so they've decided to create a new variation called Ordered Nim. Ordered Nim differs from regular Nim in the following way. The heaps are numbered 0 through n-1 (where n is the number of heaps), and a player can only remove stones from a heap if all the lower-numbered heaps are empty.
You are given a int[] layout, where the i-th element (0-indexed) is the number of stones in heap i at the beginning of the game. Alice will take the first turn. Determine who will win the game, assuming both players play optimally. Return "Alice" if Alice will win, or "Bob" if Bob will win (all quotes for clarity). |
| |
Definition |
| | | Class: | OrderedNim | | Method: | winner | | Parameters: | int[] | | Returns: | String | | Method signature: | String winner(int[] layout) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | layout will contain between 1 and 50 elements, inclusive. |
| - | Each element of layout will be between 1 and 1000000000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: "Alice" | | Alice takes all 5 stones and wins. |
|
|
| 1) | |
| | | Returns: "Bob" | | According to the rules of the game, Alice is not allowed to take stones from heap 1 because heap 0 is not empty. Her only option is to take the one stone from heap 0. Heap 0 will then be empty, so Bob can take both stones from heap 1 to win the game. |
|
|
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |