Challenge: Fewest Notes

Lab C++ Beginner 10 points

With Indian notes and coins of 2000, 500, 200, 100, 50, 20, 10, 5, 2 and 1 rupees, pay an amount with the fewest pieces (greedy works for these). Print each value used as <value> x <count>, biggest first, then Total pieces: <n>.

Input

One whole number (1 ≤ amount ≤ 100000).

Output

As described.

Example

Input

Output

2000 x 1
500 x 1
200 x 1
50 x 1
20 x 1
10 x 1
5 x 1
2 x 1
1 x 1
Total pieces: 9

Sample input available Sample output available

Editor

C++

Hints

Go from the biggest value down.

amount / v pieces of value v fit.

Solution explanation

For this set of values the greedy choice is always optimal.

Show solution

#include <iostream>
using namespace std;

int main() {
    int amount;
    cin >> amount;
    int values[] = {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
    int total = 0;
    for (int v : values) {
        if (amount >= v) {
            int k = amount / v;
            amount -= k * v;
            total += k;
            cout << v << " x " << k << endl;
        }
    }
    cout << "Total pieces: " << total << endl;
    return 0;
}

Output

Answer