index | submit | rank | book

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:

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.

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

Example input


Example output

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:

  1. 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.

  2. 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.

  3. 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

Copyright © 2020-2021 Rudy Matela
All rights reserved