11150 - Cola

[arsalan_mousavian]

can somebody tell me what is the correct output for my input ?

Code: Select all

1
2
3
4
5
6
7
8
9
10
15
20
30
40
50
100
150
190
199
200

Code: Select all

2
3
5
6
8
9
11
12
14
15
23
30
45
60
75
150
225
285
299
300

thanks

[StatujaLeha]

For N == 1 your output is wrong

[jan_holmes]

Here is my output :

Code: Select all

1
3
4
6
7
9
10
12
13
15
22
30
45
60
75
150
225
285
298
300

[Observer]

During the contest a contestant (I will not say who : ) makes the following clarification request:

Can we borrow more than 1 bottle at a time? And is it true that we are allowed to borrow bottle(s) only in the beginning?

I shall not put my answers here. Those who get Accepted should be able to answer the two questions quite easily. For those who don't know how to solve this task, thinking about the two questions above may help~

[temper_3243]

i got the solution by
1-1
2-3
3-4
4-6
5-7
6-9
7-10
etc
this is pretty trivial

Can someone tell me the DP solution or the recurrence relation.
f0(n) = n + f0(n/3); if 0 bottles borrowed
f1(n-1) = n-1 + f1(n/3); if 1 bottles borrowed
f2(n-1) = n-2 + f2(n/3); if 2 bottles borrowed
f(n)=max(f0(n),f1(n),f2(n));

is that correct or is there some simpler recurrence or DP

[Observer]

is there some simpler recurrence or DP

If you think about the two questions I posted above, then you shall get an easy relation. Thinking more deeply will even give you a very very fast method. (Don't post it here because it is a big spoiler!!!)

About your recurrence: what is "n"? If it is the number of cola you've bought, then where does the "n-1", "n-2" come from?

[jan_holmes]

Posted: Mon Jan 01, 2007 7:18 am Post subject:

--------------------------------------------------------------------------------

During the contest a contestant (I will not say who : ) makes the following clarification request:

Quote:
Can we borrow more than 1 bottle at a time? And is it true that we are allowed to borrow bottle(s) only in the beginning?

I shall not put my answers here. Those who get Accepted should be able to answer the two questions quite easily. For those who don't know how to solve this task, thinking about the two questions above may help~

Btw, it's me who sent those questions... Thx for the answers... AC already...

[temper_3243]

Hints needed , do we have a recurrence relation for this problem ?

[Observer]

Hints needed , do we have a recurrence relation for this problem ?

Yes. And that's not hard.

A (maybe) silly hint: Even if you decide to borrow k bottles, it doesn't mean that you have to use all of them!!! You may actually borrow many bottles, use none of them at all, and then return them all finally.

[SRX]

Hints needed , do we have a recurrence relation for this problem ?

you can think about it , if you borrow two bottles to get more one drink , then what is the cost of the "more one drink" ?

[MAK]

if you think about the two questions I posted above, then you shall get an easy relation.

1. You are allowed to borrow bottles --- you can borrow at any stage. But since each state is dependent only on its previous state, it makes sense to get all the bottles you need as early as possible. Having more bottles at one stage means you can get more colas in the succeeding stages.

2. How many bottles might you need? More importantly, how many bottles will you be able to give back? You will always have at least one bottle that you can return at the end. You migth also have two bottles. But you will never have three or more bottles to return. If you had three or more, you would be able to use them to get more colas until you had less than three.

Once I realized these facts, the solution was clear. Hope this helps.

[Masud_CSE_SUST]

temper_3243 wrote

do we have a recurrence relation for this problem ?

I found the following recurrence relation

.............| 0 if N = 1
F(N) =...| 1 if N = 2
.............| N / 3 + F ( N / 3 + N % 3 ) otherwise

where F(N) is total extra cola we can get from N cola

[Observer]

It's been almost a month since this task is available here. I shall say a bit more about this task.

you can borrow at any stage

That's right~ And as I have said, you do NOT need to use all borrowed bottles. You may also want to borrow bottles only when you are "trading in bottles for colas". But that's basically the same as borrowing all bottles you need at the beginning. (Why?)

Also,

You migth also have (to borrow) two bottles.

Please name one such situation.

There is actually a direct formula (without any simulation) to this task. And that is rather obvious. But please don't post the formula here!!!

[MAK]

MAK wrote:
You migth also have (to borrow) two bottles.

I actually wrote

You migth also have two bottles.

(sorry for the typo )

What I meant was that at the end of the simulation you can have either one or two empty bottles left, but never three. So you can either borrow one or two bottles and still be able to return them at the end. If you borrow three or more, you will never be able to return any more than two. In my solution I just simulated the process for three cases. The first case is where we don't borrow any extra bottles. The second is where we borrow only one bottle (we can be sure that there will be at least one bottle left so we will be able to return it). The third case is where we try with two extra bottles. Here we also have to check whether we actually have two empty bottles at the end that we can return. The maximum yield of colas from all three cases is the answer.

This was the first solution that occurred to me from reading the problem statement, and it got accepted during the contest. I truly don't know whether there are any cases where you actually need to borrow two empty bottles, but from the problem statement it seems possible that you can borrow two and still be able to give them back, so handled that case too. If there are no cases like that, no harm done.

[dileep]

Here is my output :

Code: Select all

1
3
4
6
7
9
10
12
13
15
22
30
45
60
75
150
225
285
298
300

Is your input/output case correct?