/*
 * US coins Change .C   -- ECS 122A   CM from PR
 *
 * Program to count minimum number of US coins 1, 10, 25
 * coins to make change.
 *
 * 
 *
 */

#include <iostream.h>

const c1 = 1, c2 = 10, c3=25 ;   // Values of the three kinds of coins
const huge = 0x7fffffff;

int min(int a, int b, int c=huge, int d=huge) // works on 2-4 inputs
{
 int r = a<b? a:b;
 int s = c<d? c:d;
 return r<s? r:s;
}

int NCoins(int n)   // returns smallest number of coins to make n cents
{
 if (n==c1 || n==c2 || n==c3 ) return 1;
 if (n<1) return huge;
 return 1+min(NCoins(n-c1),NCoins(n-c2),NCoins(n-c3));
}

int main()
{
 int cents;

 cout << "How many cents? ";
 cin >> cents;
 cout << "Can make " << cents << " using " << NCoins(cents) << " coins\n";
 
 return 0;
}