11150 - Cola

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11150 - Cola

Post by arsalan_mousavian » Sat Dec 30, 2006 9:17 pm

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

Post by StatujaLeha » Sat Dec 30, 2006 9:19 pm

For N == 1 your output is wrong :)

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sat Dec 30, 2006 9:24 pm

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

Post by Observer » Mon Jan 01, 2007 4:48 am

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

Post by temper_3243 » Mon Jan 01, 2007 9:55 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

Post by Observer » Mon Jan 01, 2007 10:28 am

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!!!) :wink:

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:

Post by jan_holmes » Mon Jan 01, 2007 12:53 pm

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... :P Thx for the answers... AC already... :D

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Mon Jan 01, 2007 5:49 pm

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

Post by Observer » Tue Jan 02, 2007 3:31 am

temper_3243 wrote:Hints needed , do we have a recurrence relation for this problem ?
Yes. And that's not hard. :wink:

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. :wink:
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

Post by SRX » Tue Jan 02, 2007 6:57 am

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
Location: Dhaka, Bangladesh

Some thoughts

Post by MAK » Tue Jan 02, 2007 2:01 pm

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.

User avatar
Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Location: Sylhet, Bagladesh
Contact:

Post by Masud_CSE_SUST » Mon Jan 08, 2007 8:05 pm

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

Post by Observer » Wed Jan 17, 2007 2:38 pm

It's been almost a month since this task is available here. I shall say a bit more about this task.
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.
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!!!
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
Location: Dhaka, Bangladesh

Borrowing two bottles

Post by MAK » Wed Jan 17, 2007 8:38 pm

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:

Post by dileep » Sun Mar 04, 2007 9:29 am

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
Is your input/output case correct?
Last edited by dileep on Sun Mar 04, 2007 9:44 am, edited 1 time in total.

Post Reply

Return to “Volume 111 (11100-11199)”