No.3460 Chocolate Divide Game
Problem Statement
There is a chocolate bar of length $N$ and width $1$. Alice and Bob play a game using this chocolate bar.
Alice moves first and Bob moves second, and they alternately perform the following operation.
- Split the current chocolate bar of length $k$ into two chocolate bars of lengths $a,b$. ($a,b$ are positive integers satisfying $a+b=k$.)
- Of the two chocolate bars after the split, eat the smaller one and give the larger one to the opponent. If $a=b$, eat one of them and give the other.
A player whose turn comes when the chocolate bar has length $1$ loses.
Determine which player has a winning strategy when both players act optimally.
You are given $T$ test cases; solve each of them.
Constraints
- $1 \leq T \leq 2 \times 10^{5}$
- $2 \le N \le 10^{18}$
- All input values are integers.
Input
The input is given from standard input in the following format.
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
Each test case is given in the following format.
$N$
Output
Print Alice if Alice has a winning strategy, and Bob if Bob has a winning strategy. Print a newline at the end.
Sample
Sample 1
Input
1 7
Output
Bob
Here is one example of how the game may proceed.
- Alice splits the chocolate bar of length $7$ into two pieces of lengths $5,2$ and eats the piece of length $2$.
- Bob splits the chocolate bar of length $5$ into two pieces of lengths $3,2$ and eats the piece of length $2$.
- Alice splits the chocolate bar of length $3$ into two pieces of lengths $2,1$ and eats the piece of length $1$.
- Bob splits the chocolate bar of length $2$ into two pieces of lengths $1,1$ and eats a piece of length $1$ (only one of them).
- Alice's turn comes when the chocolate bar has length $1$, so she loses.
Note that this example does not necessarily result from both players acting optimally. When both players act optimally, Bob has a winning strategy.
Sample 2
Input
2 10 15
Output
Alice Bob
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
sepa38
くらげ