UVA 11264 Coin Collector Our dear Sultan is visiting a country where there are n di erent types of coin. He wants to collect as many di erent types of coin as you can. Now if he wants to withdraw X amount of money from a Bank, the Bank will give him this money using following algorithm.

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);

}

Now Sultan can withdraw any amount of money from the Bank. He should maximize the number of di erent coins that he can collect in a single withdrawal.

Input First line of the input contains T the number of test cases. Each of the test cases starts with n (1 ≤ n ≤ 1000), the number of di erent types of coin. Next line contains n integers C1, C2, ..., Cn the value of each coin type. C1 < C2 < C3 < ... < Cn < 1000000000. C1 equals to 1.

Output For each test case output one line denoting the maximum number of coins that Sultan can collect in a single withdrawal. He can withdraw in nite amount of money from the Bank.

Sample Input 2 6 1 2 4 8 16 32 6 1 3 6 8 15 20

Sample Output 6 4

https://uva.onlinejudge.org/external/112/11264.pdf

############################################################################

Whenever I look at this problem and I realise that, we can withdraw any amount of money, and we want to maximize the number of different coins we can get from bank. Then why not, just sum up all the different coins available from bank, and use that as the amount to withdraw. This way, the constraints are followed (as amount can be any value), the answer always comes to be Entire coins set!

What am i missing? (is it Brain??)