This is a variant of change making problem. Here, we are just asked to count the number of ways to make the specific change. With a little change to the change making problem's solution, we can solve this one. The problems which can be solved with the following solution are
UVa - 657 - Coin Change UVa - 357 - Let Me Count The Ways (Need to change the way solution is printed as per problem description)
# include <iostream> # include <cstdio> using namespace std; unsigned long long NumberOfWays [30001], Coins []= {1, 5, 10, 25, 50}, Num; int main () { //freopen ("Input.txt", "r", stdin); //freopen ("Scratch.txt", "w", stdout); NumberOfWays[0] = 1; for (int i = 0; i < 5; i++) for (int j = Coins[i]; j < 30001; j++) NumberOfWays [j] += NumberOfWays [j - Coins[i]]; while (scanf ("%lld", &Num) != EOF) printf ("%lld\n", NumberOfWays[Num]); //Change this for UVa - 357 - Let Me Count The Ways }
No comments:
Post a Comment