Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define addition 1
- #define subtract 2
- #define multiply 3
- #define division 4
- int dp[110][64010];
- int n ;
- int arr[110];
- void call( int index , int total , int prevTotal)
- {
- //cout<<index<<" "<<total<<" "<<prevTotal<<endl;
- int convertedTotal;
- if(total<0)
- convertedTotal = 32000-total;
- else
- convertedTotal = total;
- if(dp[index][convertedTotal]!=-1)
- {
- return;
- }
- if(index==n)
- {
- dp[index][convertedTotal] = prevTotal;
- return;
- }
- if(total+arr[index]<=32000 || total+arr[index]>=-32000)
- call(index+1, total+arr[index], total);
- if(total-arr[index]<=32000 || total-arr[index]>=-32000)
- call(index+1, total-arr[index], total);
- if(arr[index]!=0 && total!=0)
- {
- if( abs(total) <= 32000/abs(arr[index]) )
- call(index+1, total*arr[index], total);
- }
- if(arr[index]!=0 && total!=0 )
- {
- if( total%arr[index]==0 && (total/arr[index]<=32000 || total/arr[index]>=-32000))
- call(index+1, total/arr[index], total);
- }
- dp[index][convertedTotal] = prevTotal;
- return ;
- }
- int main()
- {
- //freopen("input.txt","r",stdin);
- int test;
- cin>>test;
- while(test--)
- {
- memset(dp, -1 , sizeof dp);
- int num;
- cin>>n;
- for(int i =0; i<n; i++)
- cin>>arr[i];
- cin>>num;
- int i =n;
- int target=num;
- if(n==1)
- {
- if(arr[0]==num)
- printf("%d=%d\n",num,num);
- else
- printf("NO EXPRESSION\n");
- }
- else{
- call(0,0,0);
- stack<int>ans;
- dp[0][0]=-1;
- if(num<0)
- {
- num = 32000-num;
- }
- while(dp[i][num]!=-1)
- {
- int cmp = dp[i][num];
- if(i==1)
- break;
- if(num>32000)
- num = -(num-32000);
- if(cmp-arr[i-1]==num)
- {
- ans.push(subtract);
- }
- else if(cmp+arr[i-1]==num)
- {
- ans.push(addition);
- }
- else if(arr[i-1]*cmp==num)
- {
- ans.push(multiply);
- }
- else
- {
- if(arr[i-1]!=0 )
- if(cmp/arr[i-1]==num && cmp%arr[i-1]==0)
- {
- ans.push(division);
- }
- }
- num = cmp;
- if(num<0)
- num=32000-num;
- i--;
- }
- i=0;
- if(ans.empty()==false)
- {
- while(ans.empty()!=true)
- {
- int sign = ans.top();
- cout<<arr[i++];
- if(sign==1)
- cout<<"+";
- else if(sign==2)
- cout<<"-";
- else if(sign==3)
- cout<<"*";
- else
- cout<<"/";
- ans.pop();
- }
- cout<<arr[i++]<<"="<<target<<"\n";
- }
- else
- {
- cout<<"NO EXPRESSION"<<endl;
- }
- //return 0;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement