D. Letter Picking.cpp

#include <bits/stdc++.h>

using namespace std;

int t;
string s;

int cache[2005][2005];

int dp(int l, int r){
    if(l > r) return 2;
    if(cache[l][r]) return cache[l][r];

    int res1, res2, res3, res4;
    res1 = dp(l + 2, r);
    res2 = res3 = dp(l + 1, r - 1);
    res4 = dp(l, r - 2);

    if(res1 == 2){
        if(s[l] < s[l + 1]) res1 = 3;
        if(s[l] > s[l + 1]) res1 = 1;
    }

    if(res2 == 2){
        if(s[l] < s[r]) res2 = 3;
        if(s[l] > s[r]) res2 = 1;
    }

    if(res3 == 2){
        if(s[r] < s[l]) res3 = 3;
        if(s[r] > s[l]) res3 = 1;
    }

    if(res4 == 2){
        if(s[r] < s[r - 1]) res4 = 3;
        if(s[r] > s[r - 1]) res4 = 1;
    }

    return cache[l][r] = max(min(res1, res2), min(res3, res4));
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    cin >> t;
    while(t--){
        cin >> s;
        int n = (int)s.size();
        for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) cache[i][j] = 0;

        int ans = dp(0, n - 1);
        if(ans == 1) cout << "Bob\n";
        else if(ans == 2) cout << "Draw\n";
        else cout << "Alice\n";
    }
}