Guest User

Untitled

a guest
Oct 19th, 2015
386
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3.  
  4. using namespace std;
  5.  
  6. string intTstr(long long from_)             /// From INT to STR
  7. {
  8.     string ans;
  9.     string source;
  10.     while(from_)
  11.     {
  12.         source.push_back(from_%10+'0');
  13.         from_ /= 10;
  14.     }
  15.  
  16.     for(int i=source.length()-1; i>-1; --i)
  17.     {
  18.         ans.push_back(source[i]);
  19.     }
  20.     return ans;
  21. }
  22.  
  23. int arr[105];
  24. int res[1000005];
  25. string ans[1000005];
  26.  
  27. int main()
  28. {
  29.     int n;
  30.     cin >> n;
  31.  
  32.     for(int i=0; i<n; ++i)
  33.     {
  34.         cin >> arr[i];
  35.     }
  36.  
  37.     int sum;
  38.     cin >> sum;
  39.  
  40.     for(int i=0; i<n; ++i)          /// REPEAT EVERY DENOM. WHILE denom <= sum
  41.     {
  42.         int denom = arr[i];
  43.         int j = 1;
  44.         while(denom <= sum)
  45.         {
  46.             if(res[denom])
  47.             {
  48.                 if(res[denom] > j)
  49.                 {
  50.                     res[denom] = j;
  51.                     ans[denom] = ans[denom-arr[i]] + intTstr(arr[i]);
  52.                 }
  53.             }
  54.             else
  55.             {
  56.                 res[denom] = j;
  57.                 ans[denom] = intTstr(arr[i]);
  58.             }
  59.             denom += arr[i];
  60.         }
  61.     }
  62.  
  63.     for(int i=0; i<n; ++i)             /// COUNT EVERY SUM
  64.     {
  65.         for(int j=sum; j>0; --j)
  66.         {
  67.             if(res[j])
  68.             {
  69.                 if(res[j+arr[i]])
  70.                 {
  71.                     if(res[j+arr[i]] < res[j]+res[arr[i]])
  72.                     {
  73.                         continue;
  74.                     }
  75.                     else
  76.                     {
  77.                         res[j+arr[i]] = res[j] + res[arr[i]];
  78.                         ans[j+arr[i]] = ans[j] + ans[arr[i]];
  79.                     }
  80.                 }
  81.                 else
  82.                 {
  83.                     res[j+arr[i]] = res[j] + res[arr[i]];
  84.                     ans[j+arr[i]] = ans[j] + ans[arr[i]];
  85.                 }
  86.             }
  87.             else
  88.             {
  89.                 continue;
  90.             }
  91.         }
  92.     }
  93.     if(res[sum])
  94.     {
  95.         string result = ans[sum];
  96.         for(int i=0; i<result.length(); ++i)
  97.         {
  98.             cout << result[i];
  99.         }
  100.     }
  101.     else
  102.     {
  103.         cout << "No solution";
  104.     }
  105.    return 0;
  106. }
  107. /* THIS CODE WITHOUT SPACES IN ANSWER, BECAUSE I DELETED THEM AND TRIED TO FIND MISTAKES */
Advertisement
Add Comment
Please, Sign In to add comment