# UVa 11264

Jump to navigation
Jump to search

## Contents

## 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