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.
Consider an arbitary currency with banknotes valued at 1, 2, 5, 10, 20, 50 and 100. You can serve 31 currency units as:
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 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> is the amount of notes to be served at the value
<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
Input is terminated by the end-of-file (EOF). This can be simulated from the command line using the “ctrl-D” combination.
31 450 199
1x20 1x10 1x1 4x100 1x50 1x100 1x50 2x20 1x5 2x2
Submit your solution to be graded according to the following list:
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.
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
Copyright © 2020-2021 Rudy Matela
All rights reserved