A16797 | $Battle of Arrays$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Alice 和 Bob 正在进行一个回合制游戏。最开始，Alice 拥有一个长度为 $n$ 的正整数数组 $a$，Bob 拥有一个长度为 $m$ 的正整数数组 $b$。两位玩家轮流操作，Alice 先手。 在每位玩家的回合中，必须从自己的数组中选择一个元素 $x$，以及从对方数组中选择一个最大元素 $y$，然后进行如下操作： - 如果 $y \leq x$：则 $y$ 被销毁（即从对方数组中移除）。 - 如果 $y > x$：则 $y$ 被减少 $x$（即 $y$ 变为 $y - x$）。 若某位玩家在自己的回合操作后，对方的数组变为空，则该玩家获胜。 假设双方都采取最优策略，判断谁会赢得游戏。

每个输入包含多组测试用例。第一行为测试用例数 $t$（$1 \leq t \leq 10^5$）。 每组测试用例的第一行为两个整数 $n$ 和 $m$（$1 \leq n,m \leq 10^5$），分别表示 Alice 和 Bob 数组的长度。 第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示 Alice 的数组。 第三行为 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$1 \leq b_i \leq 10^9$），表示 Bob 的数组。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，$m$ 的总和也不超过 $10^5$。

对于每个测试用例，如果按照最优策略，输出游戏的获胜者名称：“Alice” 或 “Bob”。

输入 #1

输出 #1

Alice
Bob

C++ 编辑器

输入

输出