시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 101 | 50 | 44 | 47.312% |
Alice: "Hi, Bob! Let's play Nim!"
Bob: "Are you serious? I don't want to play it. I know how to win the game."
Alice: "Right, there is an algorithm to calculate the optimal move using XOR. How about changing the rule so that a player loses a game if he or she makes the XOR to $0$?"
Bob: "It sounds much better now, but I suspect you know the surefire way to win."
Alice: "Do you wanna test me?"
This game is defined as follows.
Your task is to find which player will win if they do the best move.
The input consists of a single test case in the format below.
$N$ $a_{1}$ $\vdots$ $a_{N}$
The first line contains an integer $N$ which is the number of the heaps ($1 \le N \le 10^5$). Each of the following $N$ lines gives the number of stones in each heap ($1 \le a_i \le 10^9$).
Output the winner, Alice or Bob, when they do the best move.
2 1 1
Alice
5 1 2 3 4 5
Bob
10 1 2 3 4 5 6 7 8 9 10
Alice
In the first example, the XOR sum is 0 in the initial state, but the game is going because nobody moves yet. First Alice takes a stone and the XOR sum becomes 1, then Bob takes the last stone and the XOR sum becomes 0. Therefore, Alice will win, and Bob will lose.