Advertisement
Guest User

uva 10400

a guest
Jul 22nd, 2014
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define addition 1
  4. #define subtract 2
  5. #define multiply 3
  6. #define division 4
  7. int dp[110][64010];
  8.  
  9. int n ;
  10. int  arr[110];
  11. void call( int index ,  int total , int prevTotal)
  12. {
  13.  
  14. //cout<<index<<" "<<total<<" "<<prevTotal<<endl;
  15.     int convertedTotal;
  16.     if(total<0)
  17.         convertedTotal = 32000-total;
  18.     else
  19.         convertedTotal = total;
  20.  
  21.     if(dp[index][convertedTotal]!=-1)
  22.     {
  23.         return;
  24.     }
  25.  
  26.     if(index==n)
  27.     {
  28.         dp[index][convertedTotal] = prevTotal;
  29.         return;
  30.     }
  31.  
  32.     if(total+arr[index]<=32000 || total+arr[index]>=-32000)
  33.         call(index+1, total+arr[index], total);
  34.     if(total-arr[index]<=32000 || total-arr[index]>=-32000)
  35.         call(index+1, total-arr[index], total);
  36.     if(arr[index]!=0 && total!=0)
  37.     {
  38.         if( abs(total) <=   32000/abs(arr[index]) )
  39.             call(index+1, total*arr[index], total);
  40.     }
  41.     if(arr[index]!=0 && total!=0  )
  42.     {
  43.         if( total%arr[index]==0 && (total/arr[index]<=32000 || total/arr[index]>=-32000))
  44.             call(index+1, total/arr[index], total);
  45.     }
  46.     dp[index][convertedTotal] = prevTotal;
  47.  
  48.     return ;
  49.  
  50. }
  51. int main()
  52. {
  53.  
  54.     //freopen("input.txt","r",stdin);
  55.  
  56.     int test;
  57.     cin>>test;
  58.     while(test--)
  59.     {
  60.  
  61.         memset(dp, -1 , sizeof dp);
  62.  
  63.         int num;
  64.         cin>>n;
  65.         for(int i =0; i<n; i++)
  66.             cin>>arr[i];
  67.         cin>>num;
  68.         int i =n;
  69.         int target=num;
  70.         if(n==1)
  71.         {
  72.             if(arr[0]==num)
  73.             printf("%d=%d\n",num,num);
  74.             else
  75.             printf("NO EXPRESSION\n");
  76.         }
  77.         else{
  78.         call(0,0,0);
  79.  
  80.         stack<int>ans;
  81.  
  82.         dp[0][0]=-1;
  83.         if(num<0)
  84.         {
  85.             num = 32000-num;
  86.         }
  87.         while(dp[i][num]!=-1)
  88.         {
  89.             int cmp = dp[i][num];
  90.  
  91.             if(i==1)
  92.                 break;
  93.  
  94.             if(num>32000)
  95.                 num = -(num-32000);
  96.  
  97.             if(cmp-arr[i-1]==num)
  98.             {
  99.                 ans.push(subtract);
  100.             }
  101.             else if(cmp+arr[i-1]==num)
  102.             {
  103.                 ans.push(addition);
  104.             }
  105.             else if(arr[i-1]*cmp==num)
  106.             {
  107.                 ans.push(multiply);
  108.             }
  109.             else
  110.             {
  111.                 if(arr[i-1]!=0 )
  112.                     if(cmp/arr[i-1]==num && cmp%arr[i-1]==0)
  113.                     {
  114.                         ans.push(division);
  115.                     }
  116.             }
  117.  
  118.             num = cmp;
  119.             if(num<0)
  120.                 num=32000-num;
  121.             i--;
  122.         }
  123.         i=0;
  124.         if(ans.empty()==false)
  125.         {
  126.             while(ans.empty()!=true)
  127.             {
  128.                 int sign = ans.top();
  129.                 cout<<arr[i++];
  130.  
  131.                 if(sign==1)
  132.                     cout<<"+";
  133.                 else if(sign==2)
  134.                     cout<<"-";
  135.                 else if(sign==3)
  136.                     cout<<"*";
  137.                 else
  138.                     cout<<"/";
  139.  
  140.                 ans.pop();
  141.             }
  142.  
  143.             cout<<arr[i++]<<"="<<target<<"\n";
  144.         }
  145.         else
  146.         {
  147.             cout<<"NO EXPRESSION"<<endl;
  148.         }
  149. //return 0;
  150.         }
  151.     }
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement