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

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

Post by Ron » 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...

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

Post by jah » 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.

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

Post by Wei-Ming Chen » 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.
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 » 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?

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

Post by kalinov » 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

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

Post by Wei-Ming Chen » Sun Sep 02, 2007 10:29 am

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 » Mon Sep 03, 2007 5:20 pm

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 » Tue Sep 04, 2007 6:38 am

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 » 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

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

Post by jah » Tue Sep 04, 2007 2:42 pm

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

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Tue Sep 04, 2007 5:13 pm

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 » Sat Sep 08, 2007 11:00 am

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 » Sat Sep 08, 2007 2:54 pm

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