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

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

11264 - Coin Collector

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

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

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

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

Post by jah »

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

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

Post 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?

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post 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

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

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

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

Post by jah »

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

Post by lena »

could anybody give me some hints?
thanks in advance.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post 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

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

Post by jah »

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:

Post by Robert Gerbicz »

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

Post by hamedv »

Can you explain steps of your algorithm

Thanks in advance

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

DP

Post by wudanzy »

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

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

Post Reply

Return to “Volume 112 (11200-11299)”