UVa 674

From Algorithmist

Contents 1 Problem Number - Problem Name 2 Summary 3 Explanation 4 Gotchas 5 Notes 6 Implementations 7 Optimizations 8 Input 9 Output 10 References

[edit] Problem Number - Problem Name

• [1]

[edit] Summary

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 7489 cents.

[edit] Explanation

[edit] Gotchas

[edit] Notes

[edit] Implementations

The high-values are computationally expensive, but can be accelerated using Dynamic Programming.

[edit] Optimizations

[edit] Input

11
26

[edit] Output

4
13

[edit] References