Page 1 of 1

11264 - Coin Collector

Posted: Sun Sep 02, 2007 7:39 am
by jah
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
by Ron
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
by jah
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
by Wei-Ming Chen
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
by jah
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
by kalinov
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
by Wei-Ming Chen
Ah,very sorry. Something wrong happened when I copy the outputs. :oops:

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

Posted: Mon Sep 03, 2007 5:20 pm
by jah
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
by lena
could anybody give me some hints?
thanks in advance.

Posted: Tue Sep 04, 2007 7:21 am
by sclo
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
by jah
Pfff, Silly mistake just an integer overflow.

Posted: Tue Sep 04, 2007 4:08 pm
by Robert Gerbicz
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
by hamedv
Can you explain steps of your algorithm

Thanks in advance

DP

Posted: Sat Sep 08, 2007 11:00 am
by wudanzy
Our team use dynamic programming to slove it in O(n^2) time.

Posted: Sat Sep 08, 2007 2:54 pm
by goodwill
Just do greedy like this:
Let A is the least money that you can collect exactly i coins.
If you draw the sample input in the paper, you can see the pattern.