#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;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vLyBHZXQgbWluaW1hbCBudW1iZXIgb2YgY29pbnMgdXNlZCB0byBnaXZlIG91dCBhbW91bnQgdXNpbmcgZ3JlZWR5IGFsZ29yaXRobQovLy8gXHBhcmFtIGFtb3VudCAtIGFtb3VudCB0byBnaXZlIG91dAovLy8gXHBhcmFtIGNvaW5zIC0gYXJyYXkgb2YgYXZhaWxhYmxlIGNvaW5zLCBzb3J0ZWQgaW4gZGVzY2VuZGluZyBvcmRlcgovLy8gXHJldHVybiBtaW5pbXVtIG51bWJlciBvZiBjb2lucyBmcm9tIGFycmF5IGNvaW5zIHVzZWQgdG8gZ2l2ZSBvdXQgYW1vdW50CmludCBjaGFuZ2VHcmVlZHkoaW50IGFtb3VudCwgaW50IGNvaW5zW10pIHsKICAgIGludCByZXN1bHQgPSAwOwogICAgaW50IGkgPSAwOwoKICAgIHdoaWxlIChhbW91bnQgPiAwKSB7CiAgICAgICAgcmVzdWx0ICs9IGFtb3VudCAvIGNvaW5zW2ldOwogICAgICAgIGFtb3VudCAlPSBjb2luc1tpXTsKICAgICAgICBpKys7CiAgICB9CgogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgYW1vdW50LCByZXN1bHQ7CiAgICBpbnQgY29pbnNbOF0gPSB7MjAwLCAxMDAsIDUwLCAyMCwgMTAsIDUsIDIsIDF9OwogICAgYW1vdW50ID0gNTg5OwogICAgCiAgICByZXN1bHQgPSBjaGFuZ2VHcmVlZHkoYW1vdW50LCBjb2lucyk7CgogICAgY291dCA8PCAiQWxnb3J5dG0gemFjaGxhbm55IiA8PCBlbmRsOwogICAgY291dCA8PCAiS3dvdGEgIiA8PCBhbW91bnQgPDwgIiBtb3plIHpvc3RhYyB3eWRhbmEgcHJ6eSB1enljaXUgIiA8PCByZXN1bHQgPDwgIiBtb25ldC9iYW5rbm90b3cuIiA8PCBlbmRsOwoKICAgIHJldHVybiAwOwp9