// Osman Zakir
// 10 / 9 / 2016
// Introduction to Computer Science
// Problem Set 1, greedy.c
// Prompt the user for the amount of change owed, then implement greedy algorithm to determine
// the least amount of coins possible that can be given back to the user/customer.  Remember to always use
// the biggest value coins possible first.
#include <cs50.h>
#include <stdio.h>
#include <math.h>

int main(void)
{
    float change = 0;
    do
    {
        printf("O hai! How much change is owed?\n");
        change = GetFloat();
    }
    while (change <= 0);

    double change_in_cents = round(change);
    int num_coins_owed = 0;

    while (change_in_cents - 25 != 0)
    {
        num_coins_owed++;
        change_in_cents -= 25;
    }
    while (change_in_cents - 10 != 0)
    {
        num_coins_owed++;
        change_in_cents -= 10;
    }
    while (change_in_cents - 5 != 0)
    {
        num_coins_owed++;
        change_in_cents -= 5;
    }
    while (change_in_cents - 1 != 0)
    {
        num_coins_owed++;
        change_in_cents -= 1;
    }

    printf("%d\n", (int)num_coins_owed);
}