A14341. Palindrome Game (hard version)
编程题
普及/提高-
知识点
题目描述
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.
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.
- "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.
- 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.
- 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.