Advertisement
Guest User

Untitled

a guest
Jan 7th, 2024
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int A = 26;
  6.  
  7. void solve() {
  8.     int n;
  9.     cin >> n;
  10.     vector<int> cnt(A);
  11.     for (int i = 0; i < n; i++) {
  12.         char cc;
  13.         cin >> cc;
  14.         int x = cc - 'a';
  15.         cnt[x]++;
  16.     }
  17.     vector<pair<int, int>> dp(A);
  18.     dp[A - 1] = {cnt[A - 1], 0};
  19.     for (int a = A - 2; a >= 0; a--) {
  20.         dp[a] = {cnt[a], 0};
  21.         int mx = -cnt[a];
  22.         for (int j = a + 1; j < A; j++) {
  23.             auto [x, y] = dp[j];
  24.             int curx = cnt[a] + y;
  25.             int cury = x;
  26.             if (cury - curx > mx) {
  27.                 mx = cury - curx;
  28.                 dp[a] = {curx, cury};
  29.             }
  30.         }
  31.     }
  32.     auto [alice, bob] = dp[0];
  33.     if (alice == bob) {
  34.         cout << "Draw" << '\n';
  35.     } else if (alice > bob) {
  36.         cout << "Alice" << '\n';
  37.     } else {
  38.         cout << "Bob" << '\n';
  39.     }
  40. }
  41.  
  42. int main() {
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0);
  45.    
  46.     int tc = 1;
  47.     cin >> tc;
  48.     for (int t = 1; t <= tc; t++) {
  49.         solve();
  50.     }
  51.    
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement