Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1600 点
問題文
黒板に N 個の整数が書かれており,そのうち i 番目の整数は A_i です. なお,N は偶数です. また,整数 L,R が与えられます.
Alice と Bob がゲームをします. 二人は Alice からはじめて交互に手番をプレイします. 各手番では,プレイヤーは黒板に書かれている数を一つ選んで消します.
N ターン後にゲームが終了します. ここで,Alice が消した整数の総和を s とします. L \leq s \leq R であれば Alice の勝利,そうでなければ Bob の勝利です. 両者が最適に行動した時,どちらが勝つか求めてください.
制約
- 2 \leq N \leq 5000
- N は偶数
- 1 \leq A_i \leq 10^9
- 0 \leq L \leq R \leq \sum_{1 \leq i \leq N} A_i
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N L R A_1 A_2 \cdots A_N
出力
Alice が勝つ場合は Alice
,Bob が勝つ場合は Bob
と出力せよ.
入力例 1
4 5 6 3 1 4 5
出力例 1
Alice
このゲームでは Alice が必ず勝ちます. ゲームの進行の一例を以下に示します.
- Alice が 1 を消す.
- Bob が 4 を消す.
- Alice が 5 を消す.
- Bob が 3 を消す.
この時,Alice が消した整数の総和は 6 であり,L \leq 6 \leq R なので,Alice の勝利です.
入力例 2
2 2 3 4 1
出力例 2
Bob
入力例 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
出力例 3
Bob
入力例 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
出力例 4
Alice
Score : 1600 points
Problem Statement
There are N integers written on a blackboard. The i-th integer is A_i. Here, N is even. Additionally, integers L and R 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 N turns. Then, let s be the sum of the integers erased by Alice. If L \leq s \leq R, Alice wins; otherwise, Bob wins. Find which player will win when both players play optimally.
Constraints
- 2 \leq N \leq 5000
- N is even.
- 1 \leq A_i \leq 10^9
- 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:
N L R A_1 A_2 \cdots A_N
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 1.
- Bob erases 4.
- Alice erases 5.
- Bob erases 3.
Here, the sum of the integers erased by Alice is 6. Since L \leq 6 \leq R, 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