# Coin Problem

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