Letter Picking (Codeforces 1728D)
Tags: Others, games

Alice and Bob are playing a game. Initially, they are given a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $$$s$$$, removes it from $$$s$$$ and prepends (adds to the beginning) it to their own string.The game ends when the string $$$s$$$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if there exists such position $$$i$$$ that $$$a_j = b_j$$$ for all $$$j < i$$$ and $$$a_i < b_i$$$.What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.Each testcase consists of a single line — a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string $$$s$$$ is even.The total length of the strings over all testcases doesn't exceed $$$2000$$$.

Output: For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

Note: One of the possible games Alice and Bob can play in the first testcase:   Alice picks the first letter in $$$s$$$: $$$s=$$$"orces", $$$a=$$$"f", $$$b=$$$"";  Bob picks the last letter in $$$s$$$: $$$s=$$$"orce", $$$a=$$$"f", $$$b=$$$"s";  Alice picks the last letter in $$$s$$$: $$$s=$$$"orc", $$$a=$$$"ef", $$$b=$$$"s";  Bob picks the first letter in $$$s$$$: $$$s=$$$"rc", $$$a=$$$"ef", $$$b=$$$"os";  Alice picks the last letter in $$$s$$$: $$$s=$$$"r", $$$a=$$$"cef", $$$b=$$$"os";  Bob picks the remaining letter in $$$s$$$: $$$s=$$$"", $$$a=$$$"cef", $$$b=$$$"ros". Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

Sample Inputs:
2
forces
abba

Sample Outputs:
Alice
Draw

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    s = input()[:-1]
    n = len(s)
    (l, r) = (0, n - 1)
    while l < r:
        if s[l] == s[r]:
            l += 1
            r -= 1
        else:
            break
    s = s[l:r + 1]
    res = 'Draw'
    for i in range(1, len(s), 2):
        if s[i] != s[i - 1]:
            res = 'Alice'
            break
    print(res)

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    s = input()[:-1]
    n = len(s)
    (l, r) = (0, n - 1)
    while l < r:
        if s[l] == s[r]:
            l += 1
            r -= 1
        else:
            break
    s = s[l:r + 1]
    res = 'Draw'
    for i in range(1, len(s), 2):
        if s[i] != s[i - 1]:
            res = 'Alice'
            break
    print(res)

Solution (Python):
""""""
N = int(input())
for _ in range(N):
    S = input()
    ans = 'Draw'
    f = 0
    while len(S) != 0 and S[0] == S[-1]:
        S = S[1:-1]
    for i in range(len(S) // 2):
        if ord(S[2 * i]) != ord(S[2 * i + 1]):
            ans = 'Alice'
            print(ans)
            f = 1
            break
    if f == 0:
        print('Draw')