ThueMorseGame | Topcoder Archive

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:

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.

For example, the number 19 written in binary is 10011. This number has three ones in binary, and three is an odd number. Hence, whenever a player produces a pile with exactly 19 stones, they lose the game immediately. You are given the ints 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.

Definition

Class:: ThueMorseGame
Method:: get
Parameters:: int, int
Returns:: String
Method signature:: String get(int n, int m)
(be sure your method is public)

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

```
3
```
```
3
```
```
Returns: "Alice"
```
Here Alice can take three stones from the heap and win.
```
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.
```
387
```
```
22
```
```
Returns: "Alice"
```
```
499999999
```
```
50
```
```
Returns: "Alice"
```
```
499999975
```
```
49
```
```
Returns: "Bob"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.