Return to the Top of Page, First Page, or Novice Problem Set.
The Icy Cold Cola Company has many cola machines scattered throughout Petticoat Junction. These are all new machines that accept coins, dollar bills and five dollar bills. Unfortunately, the original programmer who wrote the code for returning change was very lazy. His algorithm always returns change in nickels (imagine buying the small Icy Cold Cola bottle for fifteen cents and getting $4.85 change in nickels). Since the introduction of the new cola machine, sales have plumetted. A survey discovered that customers did not like carrying around a lot of change (because of the weight).
The Icy Cold Cola Company has hired you to write a new change making program. The program must calculate how to make change so that the customer gets the correct amount of change with the least amount of weight (after all, the customers were upset about the weight of the coins). You also may not give more than fifteen of a single coin in change.
The Icy Cold Cola Company sells drinks for $0.15, $0.55, $0.95 and $1.15. You will be given two values: the amount of the sale and the amount of money the customer deposited (will not exceed $5.00). You stop making change when the amount of the sale is -1. All amounts will be given in pennies. You are allowed to make change in nickels, dimes, and quarters. Nickels weigh 0.18 ounces. Dimes weigh 0.1 ounces. Quarters weigh .27 ounces.
Sample Input Data:
15
75
115
500
55
100
-1
Sample Output:
60 cents as 6 dimes
385 cents as 11 quarters 11 dimes
45 cents as 1 quarters 2 dimes
NOTE: Spacing around numbers is not critical.
Return to the Top of Page, First Page, or Novice Problem Set.
Return to the Top of Page, First Page, or Novice Problem Set.
Source Code for a Solution to this Problem
#include <stdio.h>
#define MAXCOINS 15
#define QUARTER_WEIGHT 0.27
#define DIME_WEIGHT 0.10
#define NICKEL_WEIGHT 0.18
int min(int a, int b)
{
if (a < b)
return a;
else
return b;
}; /* end of min function */
void main () {
int cost; /* cost of sale */
int amt; /* money deposited */
int change; /* change to return */
double weight; /* best weight */
int q; /* quarters (best number) */
int d; /* dimes (best number) */
int n; /* nickels (best number) */
double cwt; /* current weight */
int cq; /* quarters (current number) */
int cd; /* dimes (current number) */
int cn; /* nickels (current number) */
scanf("%d", &cost); /* priming read */
while (0 < cost)
{ /* loop while input available */
scanf("%d", &amt);
change = amt - cost;
weight = 99999; q = 0; d = 0; n = 0;
q = min(MAXCOINS, (change / 25));
d = min(MAXCOINS, (change - (q * 25)) / 10);
n = (change - (q *25) - (d * 10)) / 5;
weight = (q * QUARTER_WEIGHT) + (d * DIME_WEIGHT) + (n * NICKEL_WEIGHT);
cq = q; cd = d; cn = n; cwt = weight;
while ((cq > 0) && ((5 + (10 * MAXCOINS)) >= (change - (cq * 25))))
{
cq--;
cd = min(MAXCOINS, ((change - (cq * 25)) / 10));
cn = min(MAXCOINS, ((change - (cq * 25) - (cd * 10)) / 5));
cwt = (cq * QUARTER_WEIGHT) + (cd * DIME_WEIGHT) + (cn * NICKEL_WEIGHT);
if (cwt < weight)
{
q = cq;
d = cd;
n = cn;
weight = cwt;
}
}
/* debug printf("%d - %d = %d (%d %d %d - %f)\n", amt, cost, change, q, d, n, weight); */
printf("%d cents as ",change);
if (q > 0)
printf("%d quarters\t", q);
if (d > 0)
printf("%d dimes\t", d);
if (n > 0)
printf("%d nickels\t", n);
printf("\n");
scanf("%d", &cost); /* rad at bottom of loop */
} /* loop while input available */
}
Return to the Top of Page, First Page, or Novice Problem Set.
15 75 115 500 55 100 -1
Return to the Top of Page, First Page, or Novice Problem Set.
60 cents as 6 dimes 385 cents as 11 quarters 11 dimes 45 cents as 1 quarters 2 dimes
Return to the Top of Page, First Page, or Novice Problem Set.
15 75 115 500 55 100 15 500 55 500 95 500 115 500 70 85 -1
Return to the Top of Page, First Page, or Novice Problem Set.
60 cents as 6 dimes 385 cents as 11 quarters 11 dimes 45 cents as 1 quarters 2 dimes 485 cents as 15 quarters 11 dimes 445 cents as 13 quarters 12 dimes 405 cents as 11 quarters 13 dimes 385 cents as 11 quarters 11 dimes 15 cents as 1 dimes 1 nickels
Return to the Top of Page, First Page, or Novice Problem Set.
55 500 55 400 55 455 15 15 115 120 115 500 45 500 -1
Return to the Top of Page, First Page, or Novice Problem Set.
445 cents as 13 quarters 12 dimes 345 cents as 9 quarters 12 dimes 400 cents as 10 quarters 15 dimes 0 cents as 5 cents as 1 nickels 385 cents as 11 quarters 11 dimes 455 cents as 13 quarters 13 dimes
Return to the Top of Page, First Page, or Novice Problem Set.
Return to the LSU High School Programming Contest Homepage