OrderedNim
SRM 450 · 2009-10-17 · by Rydberg
SRM 450 · 2009-10-17 · by Rydberg · Simple Math
Problem Statement
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 aint[] 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).
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
Constraints
- layout will contain between 1 and 50 elements, inclusive.
- Each element of layout will be between 1 and 1000000000, inclusive.
Examples
0)
{5}
Returns: "Alice"
Alice takes all 5 stones and wins.
1)
{1,2}
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)
{2,1}
Returns: "Alice"
3)
{10,9,8,7,6,5,4,3,2,1}
Returns: "Alice"
4)
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000};
Returns: "Alice"
Submissions are judged against all 227 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class OrderedNim with a public method string winner(vector<int> layout) · 227 test cases · 2 s / 256 MB per case