diff options
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 177 |
1 files changed, 19 insertions, 158 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index d3330a1..070cf04 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,171 +1,32 @@ #include <iostream> -#include <vector> -#include <cmath> -#include <iomanip> -#include <algorithm> -#include <cfloat> +#include <climits> //#include <gtest/gtest.h> -using std::vector; -using std::min; - -struct Point { - int x, y; - bool operator==(const Point &p1) { - return (x == p1.x && y == p1.y); - } -}; - -bool sortPointXDimension(Point i, Point j) { - if (i.x == j.x) { - return i.y < j.y; - } - return i.x < j.x; -} - -bool sortPointYDimension(Point i, Point j) { - if (i.y == j.y) { - return i.x < j.x; - } - return i.y < j.y; -} - -float distance(Point p1, Point p2) { - return pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2); -} - -float baseCaseMinDistance(vector<Point> &ptsVector, int low, int high) { - if (high - low == 1) - return distance(ptsVector[low], ptsVector[high]); - if (high - low == 2) { - float f1 = distance(ptsVector[low], ptsVector[low + 1]); - float f2 = distance(ptsVector[low], ptsVector[high]); - float f3 = distance(ptsVector[high], ptsVector[low + 1]); - return min(f1, min(f2, f3)); - } - float f1 = distance(ptsVector[low], ptsVector[low + 1]); - float f2 = distance(ptsVector[low], ptsVector[low + 2]); - float f3 = distance(ptsVector[low], ptsVector[high]); - float f4 = distance(ptsVector[low + 1], ptsVector[low + 2]); - float f5 = distance(ptsVector[low + 1], ptsVector[high]); - float f6 = distance(ptsVector[low + 2], ptsVector[high]); - return min(f1, min(f2, min(f3, min(f4, min(f5, f6))))); -} - -float dPrimeDistance(vector<Point> &shadedPoints) { - float minDistance = FLT_MAX; - float tempDistance; - for (int i = 0; i < shadedPoints.size(); i++) { - for (int j = 1; j <= 5; j++) { - if (i + j < shadedPoints.size()) { - tempDistance = distance(shadedPoints[i], shadedPoints[i + j]); - minDistance = min(tempDistance, minDistance); +int getChange(int money) { + // denominations: 1, 3, 4 + int denominations[3] = { 1, 3, 4 }; + int minNumCoins[money + 1] = { }; + for (int m = 1; m < money + 1; m++) { + minNumCoins[m] = INT_MAX; + for (int i = 0; i < 3; i++) { + if (m >= denominations[i]) { + int numCoins = minNumCoins[m - denominations[i]] + 1; + if (numCoins < minNumCoins[m]) { + minNumCoins[m] = numCoins; + } } } } - return minDistance; + return minNumCoins[money]; } -float minimalDistance(vector<Point> &ptsVector, int low, int high) { - if (high - low <= 3) { - return baseCaseMinDistance(ptsVector, low, high); - } - int mid = low + (high - low) / 2; - long midX = ptsVector[mid].x; - float f1 = minimalDistance(ptsVector, low, mid - 1); - float f2 = minimalDistance(ptsVector, mid, high); - float f = min(f1, f2); - vector<Point> shadedPoints; - for (int i = low; i <= high; i++) { - if (abs(ptsVector[i].x - midX) <= f) - shadedPoints.push_back(ptsVector[i]); - } - - std::sort(shadedPoints.begin(), shadedPoints.end(), sortPointYDimension); - - float fPrime = dPrimeDistance(shadedPoints); - - return min(f, fPrime); -} -float minimalDistance(vector<int> &x, vector<int> &y) { - vector<Point> ptsVector(x.size()); - Point tempP; - - for (int i = 0; i < x.size(); i++) { - tempP = {x[i],y[i]}; - ptsVector[i] = tempP; - } - - std::sort(ptsVector.begin(), ptsVector.end(), sortPointXDimension); - return sqrt(minimalDistance(ptsVector, 0, ptsVector.size() - 1)); -} //TEST(SortPoint, Sort1) { -// vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 }; -// vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 }; -// vector<Point> p; -// Point tempP; -// -// for (int i = 0; i < x.size(); ++i) { -// tempP = {x[i],y[i]}; -// p.push_back(tempP); -// }; -// -// std::sort(p.begin(), p.end(), sortPointXDimension); -// -// ASSERT_EQ(p[0].x, -4); -// ASSERT_EQ(p[0].y, 0); -// -// std::sort(p.begin(), p.end(), sortPointYDimension); -// ASSERT_EQ(p[0].y, -4); -// ASSERT_EQ(p[0].x, -3); -// ASSERT_EQ(p[10].y, 4); -// ASSERT_EQ(p[10].x, 4); -//} -// -//TEST(PointDistance, Test1) { -// vector<int> x = { 0, 0 }; -// vector<int> y = { 3, 4 }; -// -// float f = minimalDistance(x, y); -// ASSERT_FLOAT_EQ(f, 5); -//} -// -//TEST(ClosestDistance, Test1) { -// vector<int> x = { 0, 3 }; -// vector<int> y = { 0, 4 }; -// float result = 5.0; -// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); -//} -// -//TEST(ClosestDistance, Test2) { -// vector<int> x = { 0, 3, 5 }; -// vector<int> y = { 0, 4, 6 }; -// float result = 2.828427; -// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); -//} -// -//TEST(ClosestDistance, Test3) { -// vector<int> x = { 7, 1, 4, 7 }; -// vector<int> y = { 7, 100, 8, 7 }; -// float result = 0.0; -// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); -//} -// -//TEST(ClosestDistance, Test4) { -// vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 }; -// vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 }; -// float result = 1.4142135; -// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); +// ASSERT_EQ(2, getChange(2)); +// ASSERT_EQ(9, getChange(34)); //} int main() { - size_t n; - std::cin >> n; - vector<int> x(n); - vector<int> y(n); - for (size_t i = 0; i < n; i++) { - std::cin >> x[i] >> y[i]; - } - std::cout << std::fixed; - std::cout << std::setprecision(9) << minimalDistance(x, y) << "\n"; + int m; + std::cin >> m; + std::cout << getChange(m) << '\n'; } |