UVa 357

From Algorithmist
Jump to navigation Jump to search

357 - Let Me Count The Ways[edit]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=293

Summary[edit]

Find the number of ways to calculate N using only coins of values (1,5,10,25,100 cents)

Explanation[edit]

Classical DP Coin change problem.

Gotchas[edit]

N limit is 30000, the limits in the PDF are wrong. Take care of output formatting.

Input[edit]

29999
1
4
30000

Output[edit]

There are 543065523200 ways to produce 29999 cents change.
There is only 1 way to produce 1 cents change.
There is only 1 way to produce 4 cents change.
There are 543427145501 ways to produce 30000 cents change.

Solutions[edit]