← 返回题目列表

Codeforces · 2104/C

C. 卡牌游戏

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

Alice 和 Bob 正在玩游戏。他们有 $$$n$$$ 卡片,编号从 $$$1$$$ 到 $$$n$$$。游戏开始时,这些卡牌中的一部分交给Alice,其余的交给Bob。

编号为 $$$i$$$ 的牌击败编号为 $$$j$$$ 的牌当且仅当 $$$i \gt j$$$, ,但有一个例外:卡 $$$1$$$ 击败卡 $$$n$$$。

只要每个玩家至少拥有一张牌,游戏就会继续。在每个回合中,都会发生以下情况:

  1. Alice 选择她的一张牌并将其面朝上放在桌子上;
  2. 鲍勃看到爱丽丝的牌,选择了他的一张牌并将其面朝上放在桌子上;
  3. 如果 Alice 的牌击败了 Bob 的牌,则两张牌都被 Alice 拿走。否则,两张牌都会被鲍勃拿走。

玩家可以使用他们在前一个回合中获得的一张牌。

回合开始时没有牌的玩家输。如果两名玩家都发挥最佳,确定谁会获胜。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 卡的数量;
  • 第二行包含 $$$n$$$ 个字符,每个字符 A or B。如果第 $$$i$$$ 个字符是 A,则卡号 $$$i$$$ 最初被赋予给 Alice;否则,将其交给 Bob。

对输入的附加约束:在每个测试用例中,最初至少给 Alice 一张卡,最初给 Bob 至少一张卡。

输出

对于每个测试用例,输出 爱丽丝 如果 Alice 以最佳玩法获胜,或者 鲍勃 如果鲍勃获胜。可以证明,如果两个玩家都发挥最佳,游戏肯定会在有限的回合中以其中一个玩家获胜而结束。

示例

输入
复制

8
2
AB
2
BA
4
ABAB
4
BABA
3
BAA
5
AAAAB
5
BAAAB
6
BBBAAA

输出
复制

Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice

注意

在第一个测试用例中,Alice 只有一张卡,Bob 只有一张卡。由于爱丽丝的牌击败了鲍勃的牌,因此她在第一回合后获胜。

在第二个测试用例中,Alice 只有一张卡,Bob 只有一张卡。由于鲍勃的牌击败了爱丽丝的牌,因此他在第一回合后获胜。

在第三个测试用例中,有两种可能的游戏场景:

  • 如果 Alice 在第一回合打出 $$$1$$$ 牌,Bob 可以用 $$$2$$$ 牌回应并拿走两张牌。然后,Alice 必须在第二回合打出 $$$3$$$ 牌,而 Bob 将通过打出 $$$4$$$ 牌来回应。然后,他赢了;
  • 如果 Alice 在第一回合打出 $$$3$$$ 牌,Bob 可以用 $$$4$$$ 牌回应并拿走两张牌。然后,Alice 必须打出 $$$1$$$ 牌,而 Bob 可以用 $$$2$$$ 牌或 $$$3$$$ 牌来回应。然后,他赢了。

在第四个测试用例中,有两种可能的游戏场景:

  • 如果 Alice 在第一回合打出 $$$2$$$ 牌,Bob 可以用 $$$3$$$ 牌回应并拿走两张牌。然后,爱丽丝必须在第二回合打出$$$4$$$ 牌,鲍勃将通过打出$$$1$$$ 牌来回应。然后,他赢了;
  • 如果 Alice 在第一回合打出 $$$4$$$ 牌,Bob 可以用 $$$1$$$ 牌回应并拿走两张牌。然后,Alice 必须打出 $$$2$$$ 牌,而 Bob 可以用 $$$3$$$ 牌或 $$$4$$$ 牌来回应。然后,他赢了。