여러 더미에서 돌을 가져가되 더미 크기의 XOR을 0으로 만든 사람이 지는 게임에서 최선의 플레이를 할 때 승자를 판정한다.
어려움8게임 이론수학비트 연산아직 제출이 없습니다시간 제한2초메모리 제한512 MBAlice: "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≤N≤105). Each of the following N lines gives the number of stones in each heap (1≤a_i≤109).
Output the winner, Alice or Bob, when they do the best move.
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.