UVa 147

From Algorithmist
Jump to navigation Jump to search

147 - Dollars[edit]

Summary[edit]

Count the number of ways we can form a certain amount.

Explanation[edit]

This is a standard Dynamic Programming - Subset Sum problem.

Gotchas[edit]

  • Rounding Errors.
  • Use long long instead of int

Notes[edit]

  • Avoid using double in the input.
  • The inputs have been raised in the recent years.

Optimizations[edit]

  • You can make the array smaller by noting that everything is a multiple of 5 cents.

Input[edit]

0.20
2.00
299.95
0.00

Output[edit]

  0.20                4
  2.00              293
299.95  181000196059736

Solutions[edit]