Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define L(i, m, n) for(int i(m);i < n;i++)
- #define pb push_back
- #define D(X) cout<<" "<<#X": "<<X<<endl;
- #define in(x) cin >> x
- #define SZ(X) int(X.size())
- #define clr(A, V) L(i, 0, 111) A[i]=V
- #define ff first
- #define ss second
- #define RF(X) freopen(X, "r", stdin)
- #define WF(X) freopen(X, "w", stdout)
- using namespace std;
- typedef long long ll;
- typedef pair<ll,ll> pll;
- typedef vector<int> vi;
- typedef vector<vi> vii;
- typedef pair<int,int> pii;
- typedef vector<pii> vpii;
- typedef pair<int, string> pis;
- typedef vector<string> vs;
- typedef pair<pair<int, int>, pair<int, int > > piiii;
- const int offset =32000;
- bool valid(int n){
- return n>-32000&&n<32000;
- }
- char op[109];
- int vis[109][65000]; /**memset-1**/
- int a[109];
- int n, target;
- bool dp(int index, int sum){
- // printf("index == %d, sum == %d\n", index, sum);
- if(index==n)return sum==target;
- if(vis[index][sum+offset]!=-1)return vis[index][sum+offset];
- bool plus=0, minus=0, divides=0, multiplies=0;
- if(valid(sum+a[index])){
- plus=dp(index+1, sum+a[index]);
- if(plus){
- op[index]='+';
- return vis[index][sum+offset]=1;
- }
- }
- if(valid(sum-a[index])){
- minus=dp(index+1, sum-a[index]);
- if(minus){
- op[index]='-';
- return vis[index][sum+offset]=1;
- }
- }
- if(valid(sum*a[index])){
- multiplies=dp(index+1, sum*a[index]);
- if(minus){
- op[index]='*';
- return vis[index][sum+offset]=1;
- }
- }
- if(sum % a[index] == 0 && valid(sum/a[index])){
- divides=dp(index+1, sum/a[index]);
- if(divides){
- op[index]='/';
- return vis[index][sum+offset]=1;
- }
- }
- return vis[index][sum+offset]=0;
- }
- int main(){
- // RF("in.txt");
- WF("out.txt");
- int t;in(t);
- while(t--){
- memset(vis, -1, sizeof(vis));
- memset(a, 0, sizeof(a));
- L(i,0,109) op[i]=' ';
- in(n);
- L(i,0,n)in(a[i]);in(target);
- if(!dp(1,a[0]))
- cout << "NO EXPRESSION\n";
- else{
- L(i,0,n){
- cout << a[i];
- if(i!=n-1)
- cout << op[i+1];
- }
- cout <<"="<<target<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement