fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string toString(__int128 x) {
  5.     if(x == 0) return "0";
  6.     bool neg = false;
  7.     if(x < 0) { neg = true; x = -x; }
  8.     string s;
  9.     while(x > 0) {
  10.         int digit = (int)(x % 10);
  11.         s.push_back('0' + digit);
  12.         x /= 10;
  13.     }
  14.     if(neg) s.push_back('-');
  15.     reverse(s.begin(), s.end());
  16.     return s;
  17. }
  18.  
  19. // Structure representing one pair of gates.
  20. struct GatePair {
  21.     char opL, opR; // either '+' or 'x'
  22.     int a, b;
  23. };
  24.  
  25. int main(){
  26.     ios::sync_with_stdio(false);
  27.     cin.tie(nullptr);
  28.  
  29.     int t; 
  30.     cin >> t;
  31.     while(t--){
  32.         int n; 
  33.         cin >> n;
  34.         vector<GatePair> pairs(n);
  35.         for (int i = 0; i < n; i++){
  36.             cin >> pairs[i].opL >> pairs[i].a >> pairs[i].opR >> pairs[i].b;
  37.         }
  38.  
  39.         // dp after all pairs: dp(L, R) = L + R  -> coefficients: A = 1, B = 1, C = 0.
  40.         __int128 A = 1, B = 1, C = 0;
  41.  
  42.         // Process gate pairs in reverse.
  43.         for (int i = n-1; i >= 0; i--){
  44.             char opL = pairs[i].opL, opR = pairs[i].opR;
  45.             int paramL = pairs[i].a, paramR = pairs[i].b;
  46.  
  47.             __int128 nA, nB, nC;
  48.             bool leftBetter = (A >= B); // decision: bonus allocation will weight the lane with higher sensitivity.
  49.  
  50.             if(opL == '+' && opR == '+'){
  51.                 // Both additions: bonus_total = paramL + paramR (a constant)
  52.                 if(leftBetter){
  53.                     nA = A;
  54.                     nB = B;
  55.                     nC = C + A * (paramL + paramR);
  56.                 } else {
  57.                     nA = A;
  58.                     nB = B;
  59.                     nC = C + B * (paramL + paramR);
  60.                 }
  61.             } else if(opL == 'x' && opR == '+'){
  62.                 // Left multiplication and right addition.
  63.                 // bonus_total = (paramL - 1)*L + paramR.
  64.                 if(leftBetter){
  65.                     nA = A * paramL;
  66.                     nB = B;
  67.                     nC = C + A * paramR;
  68.                 } else {
  69.                     nA = A + B * (paramL - 1);
  70.                     nB = B;
  71.                     nC = C + B * paramR;
  72.                 }
  73.             } else if(opL == '+' && opR == 'x'){
  74.                 // Left addition and right multiplication.
  75.                 // bonus_total = paramL + (paramR - 1)*R.
  76.                 if(leftBetter){
  77.                     nA = A;
  78.                     nB = B + A * (paramR - 1);
  79.                     nC = C + A * paramL;
  80.                 } else {
  81.                     nA = A;
  82.                     nB = B * paramR;
  83.                     nC = C + B * paramL;
  84.                 }
  85.             } 
  86.             else if(opL == 'x' && opR == 'x'){
  87.  
  88.                 if(leftBetter){
  89.                     nA = A * paramL;
  90.                     nB = B + A * (paramR - 1);
  91.                     nC = C;
  92.                 } else {
  93.                     nA = A + B * (paramL - 1);
  94.                     nB = B * paramR;
  95.                     nC = C;
  96.                 }
  97.             }
  98.             A = nA; B = nB; C = nC;
  99.         }
  100.  
  101.         long long ans = A + B + C;
  102.         cout << ans << "\n";
  103.     }
  104.     return 0;
  105. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
4
3
+ 4 x 2
x 3 x 3
+ 7 + 4
4
+ 9 x 2
x 2 x 3
+ 9 + 10
x 2 + 1
4
x 2 + 1
+ 9 + 10
x 2 x 3
+ 9 x 2
5
x 3 x 3
x 2 x 2
+ 21 + 2
x 2 x 3
+ 41 x 3
stdout
copy 
32
98
144
351
https://ideone.com/fsQIzq
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!