https://codeforces.com/contest/1527/problem/B1
시간 1초, 메모리 256MB
input :
- t (1≤t≤103)
- n (1≤n≤103)
- string
sof lengthn
output :
- 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.
각 테스트 케이스에서 아래의 단어 중 하나를 출력한다.
Alic가 이겼을 경우 "ALICE", Bob이 이겼을 경우 "BOB", 비겼을 경우 "DRAW"를 출력하시오.
조건 :
-
Both players take alternate turns with Alice going first.
플레이어들은 번갈아 가면서 플레이 합니다. 선공은 Alice가 가져갑니다. -
Choose any
i(1≤i≤n), where s[i]= '0' and change s[i] to '1'. Pay 1 dollar.
1달러를 지불 하고i지점의 값을 1로 교체합니다.
-
Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse.
문자열을 뒤집습니다. 이 조건은 문자열이 palindrome이 아닐 때에만 사용할 수 있습니다. 그리고 상대의 행동이reverse가 아니여야 합니다.
문제에 입력되는 문자열은 기본적으로 팰린드롬이다. 처음 접근에는 그냥 팰린드롬이 아니면 뒤집게 하면 되는게 아닌가? 싶었다. 그러나 최적의 플레이를 하려면 맨 처음 Alice가 1을 놓고 나서 Bob도 1을 놔야 한다. 어디에? Alice가 놓았던 자리의 정확한 반대편에.
그리고 나서 마지막 한 칸이 남았을 때 그 턴에 행동을 하는 사람이 뒤집는 것이다. 이렇게 하는 것이 최적의 방법이다.
예외적인 케이스로는 팰린드롬인데 중간에 위치한 값이 0인 경우이다. 이 때에는 문자열의 길이가 홀수 였을 것이다.
직접 막 확인하려고 하기 전에 어떤 행동이 최적의 수인지를 우선적으로 생각해야 한다.
그래서 어쨌든 간에 Alice가 우선 선공을 한다. 입력된 문자열을 2가지 경우로 나눌 수 있는데
1. 0의 개수가 홀수
2. 0의 개수가 짝수
인 경우로 나눌 수 있다.
홀수인 경우
이 말은 문자열의 길이가 홀수이고 중간에 위치한 문자가 0이라는 것이다.
예를 들어
10001의 경우
Alice : 10101 (여전히 팰린드롬이도록 만든다.)
Bob : 11101
Alice : 10111 (reverse를 해서 본인이 이길 수 있도록 한다.)
Bob : 11111
-> Alice 승
그렇기에 홀수라면 Alice가 승리할 수 밖에 없다.
예외의 경우로 중간에 위치한 원소만 0인 경우에는 Alice가 패배한다.
1번 조건을 행동하자 마자 더 이상 게임이 지속되지 않기 때문이다.
짝수인 경우
0000
Alice : 1000
Bob : 1001
Alice : 1101
Bob : 1011 (reverse를 해서 본인이 이길 수 있도록 한다.)
Alice : 1111
이렇게 수행을 할 것이기에 Bob이 승리한다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
data = sys.stdin.readline().rstrip()
cnt = 0
for item in data:
if item == '0':
cnt += 1
if cnt == 1 or cnt % 2 == 0:
print("BOB")
else:
print("ALICE") 
