ThueMorseGame
SRM 701 · 2016-10-02 · by Arterm
SRM 701 · 2016-10-02 · by Arterm · Math, Simple Search, Iteration
Problem Statement
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.
Each turn of the game looks as follows:
int s n and m.
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 and m.
- The current player choses a number X between 1 and m, inclusive. X cannot exceed the current number of stones in the pile.
- The current player removes X stones from the pile.
- If the pile is now empty, the current player wins the game.
- The current player counts the remaining stones in the pile, and writes that count in binary. If that number contains an odd number of ones, the current player loses the game.
Constraints
- n will be between 1 and 500,000,000, inclusive.
- m will be between 1 and 50, inclusive.
- n will have an even number of ones in binary.
Examples
0)
100000000 47 Returns: "Alice"
1)
3 1 Returns: "Bob"
2)
99999957 50 Returns: "Alice"
3)
99999988 49 Returns: "Bob"
4)
99999974 48 Returns: "Bob"
39)
3 3 Returns: "Alice"
Here Alice can take three stones from the heap and win.
40)
3 2 Returns: "Bob"
If Alice can take one or two stones. Either case, remaining number of stones will contain an odd number of ones in binary.
Submissions are judged against all 59 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ThueMorseGame with a public method string get(int n, int m) · 59 test cases · 2 s / 256 MB per case