## 11150 - Cola

Moderator: Board moderators

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

### 11150 - Cola

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
Last edited by arsalan_mousavian on Sat Dec 30, 2006 10:03 pm, edited 1 time in total.
In being unlucky I have the record.
StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
For N == 1 your output is wrong
jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am
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
Last edited by temper_3243 on Mon Jan 01, 2007 1:39 pm, edited 1 time in total.
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
temper_3243 wrote: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?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am
Hints needed , do we have a recurrence relation for this problem ?
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
temper_3243 wrote: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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
temper_3243 wrote: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" ?
studying @ ntu csie
MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm

### Some thoughts

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
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Contact:
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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### Re: Some thoughts

MAK wrote: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,
MAK wrote:You migth also have (to borrow) two bottles.

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!!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm

### Borrowing two bottles

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
New poster
Posts: 2
Joined: Sun Mar 04, 2007 9:25 am
Contact:
jan_holmes wrote: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
``````