#2797. String game

String game

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

字符串游戏是一款有趣的两人游戏,游戏分为以下几个步骤:

1.\red{1. }两个人分成两方, A\red{A }B\red{B ,}每人得到一个字符串。 A\red{A }的字符串为X\red{X,} B\red{B }的字符串为Y\red{Y,}这两 者都将在输入中给出。

2.A\red{2. A }在字符串X\red{X}中选择超过0\red{0}个字符组成字符串x\red{x}并告诉 B\red{B }

3.B\red{3. B }在字符串Y\red{Y}中选择超过0\red{0}个字符组成字符串y\red{y,}并与x\red{x}连接得到新的字符串Z\red{Z}

4.\red{4. }B\red{B }重新排列字符串Z\red{Z}

5.\red{5. }如果Z\red{Z}是回文串,B\red{B }获胜,否则 A\red{A }获胜。

现在两个玩家都在用最优策略玩游戏,问哪一方会赢。即是否存在一种 A\red{A }选择字符串x\red{x}的方案,使 B\red{B }无 论怎么选都无法使Z\red{Z}回文,存在即 A\red{A }获胜,否则 B\red{B }获胜。

输入格式

这个问题有多个测试数据。

第一行包含一个数字T\red{T,}它表示数据组的数量。

接下来T×2\red{T\times 2}行,每两行为一个测试数据:

第一行包含一个字符串X\red{X,}它表示 A\red{A }方得到的字符串;

第二行包含一个字符串Y\red{Y,}它代表 B\red{B }方得到的字符串。

输出格式

一共T\red{T}行,每行代表一个测试数据的结果,分别是 A\red{A }或者 B\red{B }A\red{A }代表 A\red{A }获胜, B\red{B }代表 B\red{B }获胜。

样例

输入样例1

2
adda
daad
abcd
wxyz

输出样例1

B
A

输入样例2

2
abcd
abc
aaab
aa

输出样例2

A
B

提示

样例说明

对于样例一见下表:

x\red{x} y\red{y} Z\red{Z}
a\red{a } a\red{a } aa\red{aa}
d\red{d } d\red{d } dd\red{dd}
ad\red{ad } a\red{a } ada\red{ada}
dd\red{dd } dd\red{dd} dddd\red{dddd}
da\red{da } d\red{d } dad\red{dad}
aa\red{aa } aa\red{aa} aaaa\red{aaaa}
dad\red{dad } a\red{a } daad\red{daad}
daa\red{daa } d\red{d }
aaa\red{aaa } a\red{a } aaaa\red{aaaa}
ddd\red{ddd } d\red{d } dddd\red{dddd}
daad\red{daad } addda\red{addda}

无论 A\red{A }选择什么, B\red{B }总能形成回文串。

对于样例二,只要 A\red{A }选择 a\red{a ,} B\red{B }就不能选择一个字符串来形成回文串。

数据范围

对于10%\red{10\%}的数据,保证:1<=X,Y\red{1<=|X|,|Y|}(长度)<=10\red{<=10 }

对于50%\red{50\%}的数据,保证:1<=X,Y<=2×103\red{1<=|X|,|Y|<=2\times 10^3}

对于100%\red{100\%}的数据,保证:1<=T<=10\red{1<=T<=10,}1<=X,Y<=106\red{1<=|X|,|Y|<=10^6}

X,Y\red{X,Y}由小写字母组成。

普及组测试7

未参加
状态
已结束
规则
IOI
题目
4
开始于
2022-8-20 18:00
结束于
2022-8-20 21:00
持续时间
3 小时
主持人
参赛人数
18