#include <iostream>

using namespace std;

/// Get minimal number of coins used to give out amount using greedy algorithm
/// \param amount - amount to give out
/// \param coins - array of available coins, sorted in descending order
/// \return minimum number of coins from array coins used to give out amount
int changeGreedy(int amount, int coins[]) {
    int result = 0;
    int i = 0;

    while (amount > 0) {
        result += amount / coins[i];
        amount %= coins[i];
        i++;
    }

    return result;
}

int main() {
    int amount, result;
    int coins[8] = {200, 100, 50, 20, 10, 5, 2, 1};
    amount = 589;
    
    result = changeGreedy(amount, coins);

    cout << "Algorytm zachlanny" << endl;
    cout << "Kwota " << amount << " moze zostac wydana przy uzyciu " << result << " monet/banknotow." << endl;

    return 0;
}