CF1527B2.Palindrome Game (hard version)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

The first line contains a single integer $t$ ( $1 \le t \le 10^3$ ). Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 10^3$ ).

The second line of each test case contains the string $s$ of length $n$ , consisting of the characters '0' and '1'. It is guaranteed that the string $s$ contains at least one '0'.

Note that there is no limit on the sum of $n$ over test cases.

输入格式

For each test case print a single word in a new line:

"ALICE", if Alice will win the game,
"BOB", if Bob will win the game,
"DRAW", if the game ends in a draw.

输出格式

In the first test case of example,

in the $1$ -st move, Alice will use the $2$ -nd operation to reverse the string, since doing the $1$ -st operation will result in her loss anyway. This also forces Bob to use the $1$ -st operation.
in the $2$ -nd move, Bob has to perform the $1$ -st operation, since the $2$ -nd operation cannot be performed twice in a row. All characters of the string are '1', game over.

Alice spends $0$ dollars while Bob spends $1$ dollar. Hence, Alice wins.In the second test case of example,

in the $1$ -st move Alice has to perform the $1$ -st operation, since the string is currently a palindrome.
in the $2$ -nd move Bob reverses the string.
in the $3$ -rd move Alice again has to perform the $1$ -st operation. All characters of the string are '1', game over.

Alice spends $2$ dollars while Bob spends $0$ dollars. Hence, Bob wins.

输入输出样例

输入#1
```
3
3
110
2
00
4
1010
```
输出#1
```
ALICE
BOB
ALICE
```

说明/提示

In the first test case of example,

in the $1$ -st move, Alice will use the $2$ -nd operation to reverse the string, since doing the $1$ -st operation will result in her loss anyway. This also forces Bob to use the $1$ -st operation.
in the $2$ -nd move, Bob has to perform the $1$ -st operation, since the $2$ -nd operation cannot be performed twice in a row. All characters of the string are '1', game over.

Alice spends $0$ dollars while Bob spends $1$ dollar. Hence, Alice wins.In the second test case of example,

in the $1$ -st move Alice has to perform the $1$ -st operation, since the string is currently a palindrome.
in the $2$ -nd move Bob reverses the string.
in the $3$ -rd move Alice again has to perform the $1$ -st operation. All characters of the string are '1', game over.

Alice spends $2$ dollars while Bob spends $0$ dollars. Hence, Bob wins.

首页