#P18296. Glass Stepping Stones

Glass Stepping Stones

Glass Stepping Stones

Alice 和 Bob 在一个只含大写字母 L 和 R 的字符串上进行游戏。Alice 先手,两人交替操作,每次从当前字符串中删除任意一个字符;被删除字符两侧的部分直接连接。

每次操作后,按以下规则判断游戏是否结束:

  • 如果字符串中不存在连续子串 LR,则 Alice 获胜。
  • 如果字符串中不存在连续子串 RL,则 Bob 获胜。
  • 如果上述两个条件同时成立,则平局。

游戏开始前也要进行同样的判断。 例如,初始字符串含有 RL、但没有 LR,那么 Alice 已经获胜,双方都不执行操作。

双方均采取最优策略:优先争取自己获胜;无法获胜时争取平局。请判断游戏的最终结果,并给出 Alice 任意一个能保持这个结果的最优首步。

输入格式

第一行包含整数 TT(1≤T≤1061\le T\le 10^6),表示测试用例数。

接下来 TT 行,每行给出一个只由 L 和 R 组成的字符串 ss,满足 1≤∣s∣≤1061\le |s|\le 10^6。

所有测试用例的字符串长度之和不超过 10610^6。 字符 L、R 的 ASCII 码分别为 76、82。

输出格式

每个测试用例输出一行,包含最终结果 Alice、Bob 或 Draw,以及一个整数 pp。结果单词不区分大小写。

如果游戏在第一次操作前已经结束,必须输出 p=0p=0。否则,1≤p≤∣s∣1\le p\le |s|,表示 Alice 第一次应删除原字符串中从左到右第 pp 个字符。

首步最优,是指执行它之后双方继续最优操作,得到的游戏结果与原局面双方最优操作的结果相同。若有多个最优首步,可以输出任意一个;不要求与样例或标程的首步相同。

样例

输入:

16
LRRRRLRRLRRRLLLRRL
L
R
RRRRRRRRR
LLLLLLLLLLLLLLL
LRLL
RLRR
RLRL
LLLLRRR
RL
LR
LRLR
LRLLR
LRLRL
LLLLLLLLLLRRRRRRRRLLLLLLRRRR
LLLLLLLLLLRRRRRRRRLLLLLLLLLLLRRRR

输出:

Draw 10
Draw 0
Draw 0
Draw 0
Draw 0
Alice 1
Draw 2
Alice 2
Bob 0
Alice 0
Bob 0
Bob 2
Draw 5
Alice 1
Bob 2
Draw 30