UVa 11264

From Algorithmist
Jump to navigation Jump to search

11264 - Coin Collector[edit]

Summary[edit]

This problem can be solved in O(n) time using greedy approach. Given types of coins available , problem asks to find the maximum number of "different types" of coins, we can get in "one" withdraw. We have also been given the algorithm bank follows for withdrawing :

withdraw(X){ if( X == 0) return; Let Y be the highest valued coin that does not exceed X. Give the customer Y valued coin. withdraw(X-Y); }

Explanation[edit]

  • First point to understand is we always get first and last(maximum) coin. how? ask any amount > maximum coin and you will get maximum valued coin. similarly ask for amount==minimum coin value and you will get minimum coin.
  • Now we have to decide for other coins (whether or not we can get them ?)
  • let's see how to decide about ith coin (1<i<n). Say I have decided to withdraw 'S' amount of money to get most of (i-1) coins.
 Now there are two cases
    • 1. I can't get ith coin : if (i+1)th coin value <= 'S'+(ith coin value)
     why ? because as explained in withdraw(x) algorithm followed by bank, they will simply give us (i+1)th coin. 
    • 2. I can get ith coin : if (i+1)th coin > 'S'+(value of ith coin).
     In this case don't forget to update S to S+value of ith coin

Use this approach to greedily decide about all i from 1 to n-1.

Gotchas[edit]

  • Types of coin in input are sorted in ascending order of values, so do not waste time in sorting.
  • minimum number of coins is 2, except the case when there is only one coin available.
  • We have to maximize and calculate the number of "different types" of coin in single withdraw. Amount to be withdrawn is irrelevant.

Implementations[edit]

Modify to handle when n = 1;

Optimizations[edit]

Optimizations here.

Input[edit]

8
6
1 2 4 8 16 32
6
1 3 6 8 15 20
7
1 5 9 74 111 121 159
10
1 2 3 4 5 6 7 8 9 10
5
1 2 4 8 15
8
1 5 9 17 25 33 42 100
16
1 2 4 17 58 69 125 254 478 1023 10000 145236 172589 172590 1000000 10000000
2
1 2

Output[edit]

6
4
5
2
4
5
14
2