From 310f312a04cf292a4b29d45b1bdb13077d9a1cf7 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sun, 22 Jan 2023 21:01:09 +0100 Subject: adds --- Year_2/Algorithms/resto.cc | 54 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) create mode 100644 Year_2/Algorithms/resto.cc (limited to 'Year_2/Algorithms') diff --git a/Year_2/Algorithms/resto.cc b/Year_2/Algorithms/resto.cc new file mode 100644 index 0000000..53fd6f6 --- /dev/null +++ b/Year_2/Algorithms/resto.cc @@ -0,0 +1,54 @@ +#include +#include +#include +#include +#define INF 9999999 + +using namespace std; + +int +change(vector& coins, int sum) +{ + int n = coins.size(); + + int* table = new int[sum+1]; + memset(table, sum, 0); + + table[0] = 0; + for (int i = 1; i < sum+1; ++i) { + table[i] = INF; + for (int j = 0; j < n; ++j) { + if (coins[j] <= i) + table[i] = min(table[i], 1+table[i-coins[j]]); + } + } + + int result = table[sum]; + delete[] table; + + return result; +} + +int +main(int argc, char** argv) +{ + int ts = (argc > 1) ? stoi(argv[1]) : 100; + int s, n; + ifstream fin("input.txt"); + ofstream fout("output.txt"); + + for (int i = 0; i < ts; ++i) { + fin >> s >> n; + vector v(n); + for (int j = 0; j < n; ++j) { + fin >> v[j]; + } + + fout << change(v, s) << endl; + } + + + fin.close(); + fout.close(); + return 0; +} -- cgit v1.2.3-18-g5258