Make Change

Given an integer amount representing money, your task is to determine the least number of physical pieces (bills and coins) needed to make up that amount. Use the available denominations \(50, 20, 10, 5, 2, 1\) in descending order. If the amount is 0, output an empty dictionary.

Example:

Input: 97
Output: {50: 1, 20: 2, 5: 1, 2: 1}

The solution must read input from stdin and produce output to stdout.

inputFormat

The input consists of a single integer \(n\) \((0 \leq n \leq 10^9)\) on one line, which represents the amount of money.

outputFormat

Output a dictionary (or its equivalent representation) with the keys as the denominations (in descending order) that are used and values as the count of each denomination. If no change is needed, output an empty dictionary: {}.

97

{50: 1, 20: 2, 5: 1, 2: 1}