Change Maker Problem

Problem Statement

You are given an amount of money and a list of available denominations. Your task is to determine the smallest set of coins and bills (i.e. the fewest number of items) needed to make up the given amount. The approach is to use a greedy algorithm which, at each step, selects the highest possible denomination that does not exceed the remaining amount.

If it is impossible to make the exact amount using the given denominations, output an empty dictionary {}.

The procedure can be described mathematically as follows: \[ \text{For each denomination } d \text{ (sorted in descending order), choose } c = \left\lfloor \frac{\text{amount}}{d} \right\rfloor \text{ coins and reduce } \text{amount} \text{ by } c \times d. \]

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains an integer representing the amount.
2. The second line contains an integer n indicating the number of available denominations.
3. The third line contains n space-separated integers representing the denominations.

outputFormat

Output a dictionary in the format {denom: count, ...} where the keys (denominations) are sorted in descending order. If the amount cannot be exactly formed using the given denominations, output {}.## sample

97
5
1 5 10 25 50

{50: 1, 25: 1, 10: 2, 1: 2}