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

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.

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.