mickypinata

USACO-T032: Zero Sum

Dec 2nd, 2021
512
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: zerosum
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. string str;
  11. int n;
  12. char opr[4] = " +-";
  13.  
  14. void BFcheck(){
  15.     stack<int> stk;
  16.     stk.push(1);
  17.     for(int i = 2; i <= n; ++i){
  18.         char c = str[i - 2];
  19.         if(c == ' '){
  20.             stk.top() = (10 * stk.top() + i);
  21.         } else if(c == '+' || c == '-'){
  22.             int s = stk.top(); stk.pop();
  23.             if(stk.empty()){
  24.                 stk.push(s);
  25.                 stk.push(c);
  26.             } else {
  27.                 int o = stk.top(); stk.pop();
  28.                 int f = stk.top(); stk.pop();
  29.                 int ans = o == '+' ? f + s : f - s;
  30.                 stk.push(ans);
  31.                 stk.push(c);
  32.             }
  33.             stk.push(i);
  34.         }
  35.     }
  36.     if(stk.size() > 1){
  37.         int s = stk.top(); stk.pop();
  38.         int o = stk.top(); stk.pop();
  39.         int f = stk.top(); stk.pop();
  40.         int ans = o == '+' ? f + s : f - s;
  41.         stk.push(ans);
  42.     }
  43.     if(stk.top() == 0){
  44.         cout << '1';
  45.         for(int i = 2; i <= n; ++i){
  46.             cout << str[i - 2] << i;
  47.         }
  48.         cout << '\n';
  49.     }
  50. }
  51.  
  52. void recur(int i, int n){
  53.     if(i == n){
  54.         BFcheck();
  55.         return;
  56.     }
  57.     for(int j = 0; j < 3; ++j){
  58.         str.push_back(opr[j]);
  59.         recur(i + 1, n);
  60.         str.pop_back();
  61.     }
  62. }
  63.  
  64. int main(){
  65.     freopen("zerosum.in", "r", stdin);
  66.     freopen("zerosum.out", "w", stdout);
  67.  
  68.     scanf("%d", &n);
  69.     recur(0, n - 1);
  70.  
  71.     fclose(stdin);
  72.     fclose(stdout);
  73.     return 0;
  74. }
  75.  
RAW Paste Data