cash – Optimal Cash Machine – Computer Science by Example

cash – Optimal Cash Machine

Cash machines can be used to make cash withdrawals. They are also known as ATMs or Automated Teller Machines. Some cash machines are programmed to serve the minimum number of banknotes totaling a certain amount.

Banknotes of an imaginary currency: $1, $2, $5, $10, $20, $50 and $100

Consider an arbitary currency with banknotes valued at 1, 2, 5, 10, 20, 50 and 100. You can serve 31 currency units as:

thirty one banknotes valued at 1;
three banknotes valued at 10 and one banknote valued at 1; or
three banknotes valued at 20, 10 and 1.

Of the above three options, the last has less banknotes.

Write a program that computes the minimum number of banknotes totaling to a certain amount in an arbitrary currency with banknotes valued at 1, 2, 5, 10, 20, 50 and 100.

Input and Output

Input will consist of several lines each containing a single integer indicating the amount a to be served by a cash machine where 0 ≤ a ≤ 1 000 000.

For each line of input, your program should produce a line of output indicating the number of banknotes of each face value that should be served in the format <n>x<v> where <n> is the amount of notes to be served at the value <v> starting from <v> at 100 and ending at 1. If zero notes are to be served for a given value, you should omit that from the output. To serve 4 banknotes of 100 units and 1 banknote of 50 units your program should print 4x100 1x50. Banknote amounts should be space separated and there should be no trailing spaces.

Input is terminated by the end-of-file (EOF). This can be simulated from the command line using the “ctrl-D” combination.

Example input

31
450
199

Example output

1x20 1x10 1x1
4x100 1x50
1x100 1x50 2x20 1x5 2x2

Scoring

Submit your solution to be graded according to the following list:

1/6: works for the above example but produces output in an incorrect format
2/6: works for the above example and produces output in the correct format
5/6: works for other test cases
6/6: works for edge cases and has good performance

Hints

Here are some hints:

Automated judge: Keep in mind that when your program is submitted it will not be run by a human but instead by an automated judge. Instructions should be followed exactly or the judge will not give you a full score.

If you get a 1/6 score, check if you are not producing trailing spaces! There should not be a space after sequence of banknote amounts, only between each item. Printing 4x100[space]1x50[space] in a line will not work.
Produce output as you go: You do not need to accumulate input and then produce everything at the end. It is enough to produce output as you go.
Detecting the end of file. In this exercise, input is terminated by the end-of-file (EOF). Please see hints in earlier exercises on how to process input up to EOF.

try first: primes

try next: max-subarray

index | submit | rank | book