2818：Making Change

题目描述

Grocery stores have long struggled with how to avoid long checkout lines that leave customers frustrated. The "10 item or less" express line has been a common technique, but many stores a now trying to do even better by featuring self-service checkout lines. Such a system needs to have a mechanism to give correct change to the customer at the end of the transaction.
Write a program that, given the amount of change in the machine, can determine the quantities of each type of coins to return to the customer while minimizing the total number of coins dispersed.

输入解释

Input consists of one or more lines, each of the form:
Q D N P C
where Q is the number of quarters in the dispenser, D is the number of dimes, N the number of nickels, P the number of pennies, and C is the number of cents (0. . . 99) owed to the customer.
End of the input is signaled by a line of 5 zeros.

输出解释

For each line of input data, your program should output either:
Dispense # quarters, # dimes, # nickels, and # pennies.
or
Cannot dispense the desired amount.
if it is not possible to dispense the exact amount.

输入样例

5 9 9 9 37
0 9 9 9 37
10 10 10 0 37
1 3 0 10 30
1 3 6 10 30
0 0 0 0 0

输出样例

Dispense 1 quarters, 1 dimes, 0 nickels, and 2 pennies.
Dispense 0 quarters, 3 dimes, 1 nickels, and 2 pennies.
Cannot dispense the desired amount.
Dispense 0 quarters, 3 dimes, 0 nickels, and 0 pennies.
Dispense 1 quarters, 0 dimes, 1 nickels, and 0 pennies.

该题目是Virtual Judge题目，来自北京大学POJ

题目来源 Mid-Atlantic 2005, Practice Problem

源链接： POJ-2818

最后修改于 2020-10-29T06:45:05+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
1000	65536