#agc056d. [agc056_d]Subset Sum Game
[agc056_d]Subset Sum Game
Problem Statement
There are integers written on a blackboard. The -th integer is . Here, is even. Additionally, integers and are given.
Alice and Bob will play a game. They alternately take turns, with Alice going first. In each turn, the player chooses a number written on the blackboard and erases it.
The game will end in turns. Then, let be the sum of the integers erased by Alice. If , Alice wins; otherwise, Bob wins. Find which player will win when both players play optimally.
Constraints
- is even.
- $0 \\leq L \\leq R \\leq \\sum_{1 \\leq i \\leq N} A_i$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
If Alice wins, print Alice
; if Bob wins, print Bob
.
Sample Input 1
4 5 6
3 1 4 5
Sample Output 1
Alice
In this game, Alice will always win. Below is a possible progression of the game.
- Alice erases .
- Bob erases .
- Alice erases .
- Bob erases .
Here, the sum of the integers erased by Alice is . Since , Alice wins.
Sample Input 2
2 2 3
4 1
Sample Output 2
Bob
Sample Input 3
30 655 688
42 95 9 13 91 27 99 56 64 15 3 11 5 16 85 3 62 100 64 79 1 70 8 69 70 28 78 4 33 12
Sample Output 3
Bob
Sample Input 4
30 792 826
81 60 86 57 5 20 26 13 39 64 89 58 43 98 50 79 58 21 27 68 46 47 45 85 88 5 82 90 74 57
Sample Output 4
Alice