← 返回题目列表

Codeforces · 1527/B1

B1. 回文游戏(简单版)

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

简单版本和困难版本之间的唯一区别是简单版本中给定的字符串 $$$s$$$ 最初是回文,这个条件对于困难版本并不总是成立。

回文是从左到右和从右到左读取相同的字符串。例如,“101101”是回文,而“0101”则不是。

Alice 和 Bob 正在玩一个游戏,字符串 $$$s$$$(在此版本中最初是回文),长度为 $$$n$$$,由字符“0”和“1”组成。两名玩家轮流玩,爱丽丝先玩。

在每一回合中,玩家可以执行以下操作之一:

1. 选择任意 $$$i$$$ ($$$1 \le i \le n$$$),其中 $$$s[i] =$$$ '0' 并将 $$$s[i]$$$ 更改为 '1'。支付1美元。
2. 反转整个字符串,支付 0 美元。仅当字符串当前不是回文且上次操作不是反向时才允许进行此操作。也就是说,如果 Alice 反转了字符串,那么 Bob 就无法在下一步中反转,反之亦然。

反转字符串意味着将其字母从最后一个字母重新排序到第一个字母。例如“01001”反转后就变成了“10010”。

当字符串的每个字符都变为“1”时游戏结束。到目前为止花费最少美元的玩家赢得游戏,如果双方花费相同的美元,则平局。如果两个玩家都发挥最佳,则输出 Alice 获胜、Bob 获胜还是平局。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^3$$$)。

每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,由字符“0”和“1”组成。保证字符串$$$s$$$是回文并且至少包含一个'0'。

请注意,测试用例中 $$$n$$$ 的总和没有限制。

输出

对于每个测试用例,在新行中打印一个单词:

- “ALICE”,如果爱丽丝赢得了比赛,
- “BOB”,如果鲍勃会赢得比赛,
- “平局”,如果比赛以平局结束。

示例

输入 #1

2
4
1001
1
0

输出 #1

BOB
BOB

注意

在示例的第一个测试用例中,

- 在 $$$1$$$-st 移动中,Alice 必须执行 $$$1$$$-st 操作,因为该字符串当前是回文。
- 在 $$$2$$$-nd 移动中,Bob 反转了字符串。
- 在 $$$3$$$-rd 移动中,Alice 必须再次执行 $$$1$$$-st 操作。字符串中的所有字符都是“1”,游戏结束。