← 返回题目列表

Codeforces · 2190/A

A. 排序游戏

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

Alice 和 Bob 在长度为 $$$n$$$ 的二进制字符串 $$$s$$$(仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串)上玩游戏。爱丽丝先行动,玩家轮流行动。

在一个回合中,玩家选择一系列索引 $$$i_1, i_2, \ldots, i_m$$$ ($$$1 \le i_1 \lt i_2 \lt \ldots \lt i_m \le n$$$),使得这些位置的字符形成一个 非增加 序列(即 $$$s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_m}$$$)。然后玩家重新排列这些位置上的角色以进行排序 非递减 订单。

正式地,让所选字符由 $$$z$$$ 零和 $$$o$$$ 组成(其中 $$$z + o = m$$$)。该移动将位置 $$$i_1、i_2、\ldots、i_m$$$ 处的字符替换为一系列 $$$z$$$ 零,后跟 $$$o$$$ 1。当且仅当严格执行时,移动才是有效的 修改 字符串 $$$s$$$ (这意味着 $$$z \ge 1$$$ 和 $$$o \ge 1$$$)。

无法做出有效动作的玩家失败。

假设两名玩家都发挥最佳,确定获胜者。如果爱丽丝获胜,则输出有效的第一步,这是获胜策略的一部分。

输入

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

每个测试用例的第一行由一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 组成 - 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一到三行:

  • 如果 Bob 以最佳发挥获胜,则打印一行包含“鲍勃".
  • 否则,打印三行。在第一行打印“爱丽丝"。在第二行打印一个整数 $$$m$$$ ($$$2 \le m \le n$$$),在第三行打印 $$$m$$$ 不同的整数 $$$i_1, i_2, \ldots, i_m$$$ ($$$1 \le i_1 \lt i_2 \lt \ldots \lt i_m \le n$$$) —为爱丽丝的第一步选择的指数。

您打印的索引序列必须根据语句中描述的规则形成有效的移动。索引必须打印在 递增顺序。如果有多个获胜动作,您可以输出其中任何一个。

示例

输入
复制

3
3
000
2
10
3
101

输出
复制

Bob
Alice
2
1 2
Alice
2
1 2

注意

在第一个例子中,没有办法在 $$$s$$$ 发生变化后采取行动,所以 Bob 立即获胜。

在第三个例子中,Alice 可以选择一个子序列 $$$[1, 2]$$$ 并对其进行排序,之后 $$$s$$$ 将变成 $$$\mathtt{011}$$$。此后,鲍勃无法采取行动,因此爱丽丝获胜。