Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- string intTstr(long long from_) /// From INT to STR
- {
- string ans;
- string source;
- while(from_)
- {
- source.push_back(from_%10+'0');
- from_ /= 10;
- }
- for(int i=source.length()-1; i>-1; --i)
- {
- ans.push_back(source[i]);
- }
- return ans;
- }
- int arr[105];
- int res[1000005];
- string ans[1000005];
- int main()
- {
- int n;
- cin >> n;
- for(int i=0; i<n; ++i)
- {
- cin >> arr[i];
- }
- int sum;
- cin >> sum;
- for(int i=0; i<n; ++i) /// REPEAT EVERY DENOM. WHILE denom <= sum
- {
- int denom = arr[i];
- int j = 1;
- while(denom <= sum)
- {
- if(res[denom])
- {
- if(res[denom] > j)
- {
- res[denom] = j;
- ans[denom] = ans[denom-arr[i]] + intTstr(arr[i]);
- }
- }
- else
- {
- res[denom] = j;
- ans[denom] = intTstr(arr[i]);
- }
- denom += arr[i];
- }
- }
- for(int i=0; i<n; ++i) /// COUNT EVERY SUM
- {
- for(int j=sum; j>0; --j)
- {
- if(res[j])
- {
- if(res[j+arr[i]])
- {
- if(res[j+arr[i]] < res[j]+res[arr[i]])
- {
- continue;
- }
- else
- {
- res[j+arr[i]] = res[j] + res[arr[i]];
- ans[j+arr[i]] = ans[j] + ans[arr[i]];
- }
- }
- else
- {
- res[j+arr[i]] = res[j] + res[arr[i]];
- ans[j+arr[i]] = ans[j] + ans[arr[i]];
- }
- }
- else
- {
- continue;
- }
- }
- }
- if(res[sum])
- {
- string result = ans[sum];
- for(int i=0; i<result.length(); ++i)
- {
- cout << result[i];
- }
- }
- else
- {
- cout << "No solution";
- }
- return 0;
- }
- /* THIS CODE WITHOUT SPACES IN ANSWER, BECAUSE I DELETED THEM AND TRIED TO FIND MISTAKES */
Advertisement
Add Comment
Please, Sign In to add comment