← 返回题目列表

Codeforces · 1894/A

A. 秘密运动

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

让我们考虑一个有两个玩家 A 和 B 参与的游戏。这个游戏的特点是两个正整数$$$X$$$和$$$Y$$$。

比赛由几局组成,每局由几场比赛组成。在每场比赛中,只有一名玩家(A 或 B)获胜。当其中一名玩家在该盘的比赛中达到 $$$X$$$ 获胜时,该盘就结束了。该选手被宣布为该盘比赛的获胜者。玩家们进行盘赛,直到其中一人达到 $$$Y$$$ 在盘中获胜。之后,游戏结束,该玩家被宣布为整场游戏的获胜者。

您刚刚观看了一场比赛,但没有注意到谁被宣布为获胜者。您记得在游戏过程中,进行了 $$$n$$$ 次比赛,并且您知道哪个玩家赢得了每次比赛。但是,您不知道 $$$X$$$ 和 $$$Y$$$ 的值。根据现有信息,确定谁赢得了整场比赛 - A 或 B。如果没有足够的信息来确定获胜者,您还应该报告。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 20)$$$ - 游戏期间玩的次数。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由字符$$$\texttt{A}$$$和$$$\texttt{B}$$$组成。如果 $$$s_i = \texttt{A}$$$,则意味着玩家 A 赢得了第 $$$i$$$ 场比赛。如果 $$$s_i = \texttt{B}$$$,则意味着玩家 B 赢得了第 $$$i$$$ 场比赛。

对于 $$$X$$$ 和 $$$Y$$$ 的某些值,保证给定的游戏序列对应于至少一个有效的游戏场景。

输出

对于每个测试用例,输出:

- $$$\texttt{A}$$$ — 如果玩家 A 保证成为游戏的获胜者。
- $$$\texttt{B}$$$ — 如果玩家 B 保证成为游戏的获胜者。
- $$$\texttt{?}$$$ — 如果无法确定游戏的获胜者。

示例

输入 #1

7
5
ABBAA
3
BBB
7
BBAAABA
20
AAAAAAAABBBAABBBBBAB
1
A
13
AAAABABBABBAB
7
BBBAAAA

输出 #1

A
B
A
B
A
B
A

注意

在第一个测试用例中,可以使用参数 $$$X = 3$$$、$$$Y = 1$$$ 来玩游戏。这场比赛由 $$$1$$$ 盘组成,其中玩家 A 获胜,因为他们赢得了前 $$$3$$$ 局。在这种情况下,玩家 A 是胜利者。该游戏也可以使用参数 $$$X = 1$$$、$$$Y = 3$$$ 进行。可以证明,不存在玩家 B 获胜的 $$$X$$$ 和 $$$Y$$$ 值。

在第二个测试用例中,玩家 B 赢得了所有比赛。很容易证明,在这种情况下,玩家 B 一定会成为游戏的获胜者。

在第四个测试用例中,可以使用参数 $$$X = 3$$$、$$$Y = 3$$$ 来玩游戏:

- 在第一盘中,进行了 $$$3$$$ 比赛:AAA。选手 A 被宣布为该盘比赛的获胜者。
- 在第二盘中,进行了 $$$3$$$ 比赛:AAA。选手 A 被宣布为该盘比赛的获胜者。
- 在第三盘中,进行了 $$$5$$$ 比赛:AABBB。选手 B 被宣布为该盘比赛的获胜者。
- 在第四盘中,进行了 $$$5$$$ 比赛:AABBB。选手 B 被宣布为该盘比赛的获胜者。
- 第五盘中,进行了 $$$4$$$ 比赛:BBAB。选手 B 被宣布为该盘比赛的获胜者。

总共,玩家 B 是第一个赢得 $$$3$$$ 盘的玩家。他们被宣布为比赛的获胜者。