Advertisement
Insyder01

Untitled

Apr 24th, 2017
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 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 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 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 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 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