UVa 11264

Jump to navigation Jump to search

Summary

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

• 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

• 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

Modify to handle when n = 1;

Optimizations

Optimizations here.

Input

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

```6
4
5
2
4
5
14
2
```