B - Edible Card Game
Assam
2
s
1024
MB
200
点
問題文
AliceとBobがあるカードゲームで対戦します。
最初、お互いに $N$ 枚ずつカードを持っており、Aliceの $i$ 枚目のカードには整数 $A_i$ が、Bobの $i$ 枚目のカードには整数 $B_i$ がそれぞれ書かれています。
このカードゲームでは、以下の操作をお互いの手札が $0$ 枚になるか、勝者が決まるまで行います。
- AliceとBobがそれぞれ自身の持っているカードを $1$ 枚選んで同時に場に出す。
- Aliceの出したカードに書かれた数字がBobの出したカードに書かれた数字より大きい場合、Aliceを勝者としてゲームを終了する。
- Bobの出したカードに書かれた数字がAliceの出したカードに書かれた数字より大きい場合、Bobを勝者としてゲームを終了する。
- 2.,3. のどちらにも該当しなかった場合、出したカードを食べる。(食べたカードは二度と使えない) その後、1.に戻る。
お互いに勝ちを目指し最適に行動するとき、勝者はどちらとなるでしょうか？あるいは、勝者は決まらないでしょうか？
制約
- $1\leq N \leq 1000$
- $1\leq A_i,B_i \leq 9$
- 入力は全て整数
入力
$N$
$A_1 \space A_2 \space \ldots \space A_N$
$B_1 \space B_2 \space \ldots \space B_N$
出力
Aliceが勝者となる場合はAlice、Bobが勝者となる場合はBob、勝者が決まらない場合はDrawと出力してください。
入力例 1
3
3 5 7
4 6 8
出力例 1
Bob
最初にAliceがどのカードを出しても、Bobが 8 の書かれたカードを出すことによって勝つことができます。
入力例 2
9
9 9 8 2 4 4 3 5 3
9 9 8 2 4 4 3 5 3
出力例 2
Draw
両者が勝ちを目指して最適に行動した場合、勝者は決まりません。
入力例 3
10
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8
出力例 3
Alice
両者が勝ちを目指して最適に行動した場合、Aliceの勝ちとなります。