Not an official ACM page
[Problem F | 1993 East-Central Regional problem set | My ACM problem archive | my home page]

1993 East-Central Regionals of the ACM International Collegiate Programming Contest

Problem E

Stamping Out Stamps

The mail clerk for Sirius Cybernetics just received a new postal scale which will display the cost (in cents) to send a given parcel. The postal scale is medium duty, and will only handle parcels requiring up to $29.99 in postage. She has requested you to write a program that will convert the postage into the number of stamps needed to cover the required postage such that the cost is minimized.

The mailroom stocks up to ten di erent types of stamps, and only ten stamps will fit on any given parcel.

Your program would read in a list of stamp values stocked by the mailroom (all separated by single spaces) followed by a sequence of amounts to convert (one amount per line). If it is impossible to reach the given amount exactly, you are to exceed the amount by as little as possible. If there are many sets of stamps that cover the amount for the same cost, you should pick the set with the least number of stamps. Output should consist of the given stamp values on a single line followed by a blank line, then, for each amount given, the amount that needs to be covered on a single line, followed by the stamps needed for the coverage on the next line, followed by a blank line. (So the last line of stamp values in the output is followed by one blank line.) As usual, all numbers are separated by single spaces. If no solution exists, print

NO SOLUTION EXISTS
The input file ends with an end-of-file. See next page for a sample input and output.

Sample Input

2 7 14 17 22 63 98
72
86
143
5

Sample Output

STAMP VALUES 2 7 14 17 22 63 98

AMOUNT 72
STAMPS USED 63 7 2

AMOUNT 86
STAMPS USED 63 14 7 2

AMOUNT 143
STAMPS USED 63 63 17

AMOUNT 5
STAMPS USED 2 2 2

This page maintained by Ed Karrels.
Last updated November 6, 1997