Advertisement
Insyder01

Untitled

Apr 24th, 2017
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define L(i, m, n) for(int i(m);i < n;i++)
  3. #define pb push_back
  4. #define D(X) cout<<"  "<<#X": "<<X<<endl;
  5. #define in(x) cin >> x
  6. #define SZ(X) int(X.size())
  7. #define clr(A, V) L(i, 0, 111) A[i]=V
  8. #define ff first
  9. #define ss second
  10. #define RF(X) freopen(X, "r", stdin)
  11. #define WF(X) freopen(X, "w", stdout)
  12. using namespace std;
  13. typedef long long ll;
  14. typedef pair<ll,ll> pll;
  15. typedef vector<int> vi;
  16. typedef vector<vi> vii;
  17. typedef pair<int,int> pii;
  18. typedef vector<pii> vpii;
  19. typedef pair<int, string> pis;
  20. typedef vector<string> vs;
  21. typedef pair<pair<int, int>, pair<int, int > > piiii;
  22. const int offset =32000;
  23. bool valid(int n){
  24.     return n>-32000&&n<32000;
  25. }
  26. char op[109];
  27. int vis[109][65000]; /**memset-1**/
  28. int a[109];
  29. int n, target;
  30. bool dp(int index, int sum){
  31. //    printf("index == %d, sum == %d\n", index, sum);
  32.     if(index==n)return sum==target;
  33.     if(vis[index][sum+offset]!=-1)return vis[index][sum+offset];
  34.     bool plus=0, minus=0, divides=0, multiplies=0;
  35.     if(valid(sum+a[index])){
  36.         plus=dp(index+1, sum+a[index]);
  37.         if(plus){
  38.             op[index]='+';
  39.             return vis[index][sum+offset]=1;
  40.         }
  41.     }
  42.     if(valid(sum-a[index])){
  43.         minus=dp(index+1, sum-a[index]);
  44.         if(minus){
  45.             op[index]='-';
  46.             return vis[index][sum+offset]=1;
  47.         }
  48.     }
  49.     if(valid(sum*a[index])){
  50.         multiplies=dp(index+1, sum*a[index]);
  51.         if(minus){
  52.             op[index]='*';
  53.             return vis[index][sum+offset]=1;
  54.         }
  55.     }
  56.     if(sum % a[index] == 0 && valid(sum/a[index])){
  57.         divides=dp(index+1, sum/a[index]);
  58.         if(divides){
  59.             op[index]='/';
  60.             return vis[index][sum+offset]=1;
  61.         }
  62.     }
  63.  
  64.     return vis[index][sum+offset]=0;
  65. }
  66. int main(){
  67. //    RF("in.txt");
  68.     WF("out.txt");
  69.     int t;in(t);
  70.     while(t--){
  71.         memset(vis, -1, sizeof(vis));
  72.         memset(a, 0, sizeof(a));
  73.         L(i,0,109) op[i]=' ';
  74.         in(n);
  75.         L(i,0,n)in(a[i]);in(target);
  76.         if(!dp(1,a[0]))
  77.             cout << "NO EXPRESSION\n";
  78.         else{
  79.             L(i,0,n){
  80.                 cout << a[i];
  81.                 if(i!=n-1)
  82.                     cout << op[i+1];
  83.  
  84.             }
  85.             cout <<"="<<target<<endl;
  86.         }
  87.     }
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement