Page 1 of 1

### 11264 - Coin Collector

Posted: Sun Sep 02, 2007 7:39 am
I think the problem statement is a little bit ambiguous because it says:

"He should maximize the number of different coins that he can collect in a single withdrawal."

and also it says:

"For each test case output one line denoting the maximum number of coins that Sultan can collect in a single withdrawal."

So what do we have to maximize, the number of different coins or just the number of coins?

(It should be the number of different coins.)

Posted: Sun Sep 02, 2007 7:48 am
Obviously ! It should be maximum number of different coins.
But how can we take value of x ? I think it's main logic in this problem...

Posted: Sun Sep 02, 2007 8:01 am
Well I used an interval based strategy to solve this problem but I get WA.
Some test cases would be appreciated.

Posted: Sun Sep 02, 2007 8:24 am
Input

Code: Select all

``````7
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
7
1 2 3 6 12 24 48``````
Output

Code: Select all

``````5
2
4
5
14
2
6``````
Hope it helps.

Posted: Sun Sep 02, 2007 9:37 am
The output for:

16
1 2 4 17 58 69 125 254 478 1023 10000 145236 172589 172590 1000000 10000000

is 2??

What happens if you want to withdraw 7?

Posted: Sun Sep 02, 2007 9:39 am
Wei-Ming Chen, your output is incorrect.
My program outputs 14 for this input:
16
1 2 4 17 58 69 125 254 478 1023 10000 145236 172589 172590 1000000 10000000

Posted: Sun Sep 02, 2007 10:29 am
Ah,very sorry. Something wrong happened when I copy the outputs.

Yes,the answer of that case is 14 actually..

Posted: Mon Sep 03, 2007 5:20 pm
I have the same results but still WA. I don't know what I am doing wrong.

Posted: Tue Sep 04, 2007 6:38 am
could anybody give me some hints?

Posted: Tue Sep 04, 2007 7:21 am
I just do dp for this problem.
f(x,i) = maximum number of coins we can get from any values between [0,x] from coins 1 to i

Posted: Tue Sep 04, 2007 2:42 pm
Pfff, Silly mistake just an integer overflow.

Posted: Tue Sep 04, 2007 4:08 pm
There is an obvious greedy solution for the problem. Which runs in O(n) time so it's optimal.

Posted: Tue Sep 04, 2007 5:13 pm
Can you explain steps of your algorithm