# coins

Jul 14th, 2019
206
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. vector<string> split_string(string);
6.
7. // Complete the getWays function below.
8. long getWays(long n, vector<long> coins) {
9.    vector<long>ways(n + 1);
10.
11.     ways[0] = 1;
12.
13.     for(long i = 0;i < coins.size();i++)
14.     {
15.         for(long j = 0;j < ways.size();j++)
16.         {
17.             if(coins[i] <= j)
18.             {
19.                 ways[j] += ways[(j - coins[i])];
20.             }
21.         }
22.     }
23.
24.     return ways[n];
25. }
26.
27. int main()
28. {
29.     ofstream fout(getenv("OUTPUT_PATH"));
30.
31.     string nm_temp;
32.     getline(cin, nm_temp);
33.
34.     vector<string> nm = split_string(nm_temp);
35.
36.     int n = stoi(nm[0]);
37.
38.     int m = stoi(nm[1]);
39.
40.     string c_temp_temp;
41.     getline(cin, c_temp_temp);
42.
43.     vector<string> c_temp = split_string(c_temp_temp);
44.
45.     vector<long> c(m);
46.
47.     for (int i = 0; i < m; i++) {
48.         long c_item = stol(c_temp[i]);
49.
50.         c[i] = c_item;
51.     }
52.
53.     // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
54.
55.     long ways = getWays(n, c);
57.     fout.close();
58.
59.     return 0;
60. }
61.
62. vector<string> split_string(string input_string) {
63.     string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
64.         return x == y and x == ' ';
65.     });
66.
67.     input_string.erase(new_end, input_string.end());
68.
69.     while (input_string[input_string.length() - 1] == ' ') {
70.         input_string.pop_back();
71.     }
72.
73.     vector<string> splits;
74.     char delimiter = ' ';
75.
76.     size_t i = 0;
77.     size_t pos = input_string.find(delimiter);
78.
79.     while (pos != string::npos) {
80.         splits.push_back(input_string.substr(i, pos - i));
81.
82.         i = pos + 1;
83.         pos = input_string.find(delimiter, i);
84.     }
85.
86.     splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
87.
88.     return splits;
89. }