Advertisement
paulomiranda98

Untitled

May 4th, 2021
982
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define all(x) x.begin(),x.end()
  5. #define endl '\n'
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. const int INF = 0x3f3f3f3f;
  12. const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  13. const int MOD = 1000000007;
  14. const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
  15. const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};
  16.  
  17. int main() {
  18.   ios_base::sync_with_stdio(false); cin.tie(NULL);
  19.  
  20.   int t;
  21.   cin >> t;
  22.   while(t--){
  23.     ll hpA, hpB, atkA, atkB;
  24.     cin >> hpA >> hpB >> atkA >> atkB;
  25.  
  26.     int mx = 0;
  27.     ll total = 0;
  28.     while(total < hpA + hpB){
  29.       mx++;
  30.       total += mx;
  31.     }
  32.     pair<ll, string> ans(INFLL, string(mx, 'B'));
  33.     {// Kill A first
  34.       string opS(mx, 'B');
  35.       ll op = 0;
  36.       ll sum = 0;
  37.       int i=1;
  38.  
  39.       //Add 'A' while is needed
  40.       for(; sum < hpA; i++){
  41.         sum += i;
  42.         opS[i-1] = 'A';
  43.         op += atkA + atkB;
  44.       }
  45.       if(total-sum < hpB){
  46.         for(int j=i-1; j>=1; j--){
  47.           if(opS[j] == 'A' and sum-j >= hpA and total-sum+j >= hpB){
  48.             opS[j - 1] = 'B';
  49.             break;
  50.           }
  51.         }
  52.       }
  53.       for(; i<=mx; i++){
  54.         op += atkB;
  55.       }
  56.       ans = min(ans, {op, opS});
  57.     }
  58.     { // Kill first B
  59.       string opS(mx, 'A');
  60.       ll op = 0;
  61.       ll sum = 0;
  62.       int i=1;
  63.       for(; sum < hpB; i++){
  64.         sum += i;
  65.         opS[i-1] = 'B';
  66.         op += atkA + atkB;
  67.       }
  68.       int last = -1;
  69.       for(int j=1; j<i; j++){
  70.         if(sum-j >= hpB){
  71.           opS[j-1] = 'A';
  72.           sum -= j;
  73.           last = j;
  74.         }
  75.       }
  76.       if(total-sum < hpA){
  77.         assert(last != -1);
  78.         opS[last - 1] = 'B';
  79.         sum += last;
  80.         ll x = hpA - (total - sum);
  81.         opS[x - 1] = 'A';
  82.       }
  83.       for(; i<=mx; i++){
  84.         op += atkA;
  85.       }
  86.       ans = min(ans, {op, opS});
  87.     }
  88.     cout << ans.F << " " << ans.S << endl;
  89.   }
  90.   return 0;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement