11264 - Coin Collector

[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]

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]

Well I used an interval based strategy to solve this problem but I get WA.
Some test cases would be appreciated.

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

[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]

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]

Ah,very sorry. Something wrong happened when I copy the outputs.

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

[jah]

I have the same results but still WA. I don't know what I am doing wrong.

[lena]

could anybody give me some hints?
thanks in advance.

[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]

Pfff, Silly mistake just an integer overflow.

[Robert Gerbicz]

There is an obvious greedy solution for the problem. Which runs in O(n) time so it's optimal.

[hamedv]

Can you explain steps of your algorithm

Thanks in advance

[wudanzy]

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

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