## 11264 - Coin Collector

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

### 11264 - Coin Collector

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

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA
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...

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
Well I used an interval based strategy to solve this problem but I get WA.
Some test cases would be appreciated.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
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.
Last edited by Wei-Ming Chen on Sun Sep 02, 2007 10:30 am, edited 1 time in total.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 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?

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia
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

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
Ah,very sorry. Something wrong happened when I copy the outputs.

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

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
I have the same results but still WA. I don't know what I am doing wrong.

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm
could anybody give me some hints?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
Pfff, Silly mistake just an integer overflow.
Last edited by jah on Tue Sep 04, 2007 6:28 pm, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
There is an obvious greedy solution for the problem. Which runs in O(n) time so it's optimal.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
Can you explain steps of your algorithm

wudanzy
New poster
Posts: 4
Joined: Wed Sep 05, 2007 3:04 pm

### DP

Our team use dynamic programming to slove it in O(n^2) time.

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am
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.