# Problem Link

Loop Through**Author:**pskalbhav1

# Difficulty

EASY# Prerequisites

Greedy# Problem Statement

Jack likes buying "Retro Art" images. Once, during a party, he was given a challenge. Given n dollars cheque, he has to exchange it with cash of denominations 1, 5, 10, 20, 100 to buy a very famous Retro art. What is the minimum number of bills he could receive after withdrawing his entire balance?Jack really wants the Retro Art. So help him to solve the challenge and the painting.

# Approach

The problem is to minimize x

_{1}+x

_{2}+x

_{3}+x

_{4}+x

_{5}given that x

_{1}+5x

_{2}+10x

_{3}+20x

_{4}+100x

_{5}= n.

It is pretty simple to see that we can operate greedily: take as many 100 as we can, then 20, then 10, etc.

The solutions works because each number in the sequence 1,5,10,20,100 is a divisor of the number after it.

# Solution

```
#include <bits/stdc++.h>
using namespace std;
int n;
main()
{
cin>>n;
cout <<n/100+n%100/20+n%20/10+n%10/5+n%5;
}
```