← 返回题目列表

AtCoder · arc170_d

D. 三角卡牌游戏

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

Alice 和 Bob 将玩一个游戏。

最初,Alice 和 Bob 各有 N 卡,带有 iAlice 的第张牌具有整数 上面写着 A_i ,并且 iBob 的第张牌具有整数 B_i 。

游戏进行如下:

  • 准备一块黑板,上面什么也没有写。
  • Alice 吃掉了她的一张牌,并将吃掉的牌上的整数写在黑板上。
  • 接下来,鲍勃吃掉了他的一张牌,并将吃掉的牌中的整数写在黑板上。
  • 最后,爱丽丝又吃掉了一张卡片,并将吃掉的卡片上的整数写在黑板上。

如果可以用黑板上写的三个整数的边长形成一个(非退化)三角形,则爱丽丝获胜;否则,鲍勃获胜。

当两名玩家都表现最佳时确定谁获胜。

解决每个问题 T 给出的测试用例。

约束

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq 10^9
  • 所有输入值均为整数。
  • 总和 N 单个输入中的所有测试用例最多 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个案例均按以下格式给出:

N
A_1 \ldots A_N
B_1 \ldots B_N

输出

打印 T 行。的 i第行 (1 \leq i \leq T) 应包含 Alice 如果爱丽丝赢得了 i第一个测试用例,以及 Bob 如果鲍勃获胜。


示例输入 1

3
3
1 2 3
4 5 6
4
6 1 5 10
2 2 4 5
10
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

示例输出 1

Bob
Alice
Alice

例如,在第一个测试用例中,游戏可以按如下方式进行:

  • 爱丽丝吃掉了卡片 上面写着 2 并写着 黑板上的 2 。
  • 鲍勃吃掉了卡片 4 并写着 黑板上的 4 。
  • 爱丽丝吃掉了卡片 上面写着 1 并写着 黑板上的 1 。
  • 黑板上写的数字是 2, 4, 1。不存在有边长的三角形 2, 4, 1,所以鲍勃获胜。

对于这个测试用例,上述过程对于玩家来说不一定是最佳的,但可以证明如果两个玩家都表现最佳,Bob 将获胜。