wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> maximum amount of grass carried
        
(Message started by: inexorable on Oct 14^th, 2005, 10:07am)

Title: maximum amount of grass carried
Post by inexorable on Oct 14^th, 2005, 10:07am

The distance between Cairo and Damascus is 1000 miles. Your mission is to move a 10,000 kilograms load of grass from Cairo to Damascus using your camel, but you have two problems:

1. The camel won't budge unless you let it to continuously chew grass - it consumes 1 kilogram of grass per mile.
2. The camel's maximum load is 1000 kilograms.

Can you manage to get ANY of the grass to Damascus?
What is the maximum amount of grass that you can get there?

Title: Re: maximum amount of grass carried
Post by Neelesh on Oct 14^th, 2005, 10:43am

[hide] 3381 kg of load can be taken up ? [/hide]

Title: Re: maximum amount of grass carried
Post by towr on Oct 14^th, 2005, 11:46am

I never knew Damascus had such a great need for grass. (Or is it the different kind of 'grass', but why than would you let the camel eat it, it'd just get the munchies and eat more)
Bananas made more sense.

Title: Re: maximum amount of grass carried
Post by inexorable on Oct 14^th, 2005, 11:51am

can u plz explain neelesh?

Title: Re: maximum amount of grass carried
Post by Grimbal on Oct 14^th, 2005, 3:10pm

I find [hide]1399.767[/hide] kg...

Title: Re: maximum amount of grass carried
Post by Neelesh on Oct 14^th, 2005, 10:52pm

on 10/14/05 at 11:51:56, inexorable wrote:

can u plz explain neelesh?

I divided the work between myself and a computer - I did the thinking and computer did the calculations.

So for every mile the camel will eat one kg of grass or banana or whatever.

So the best way is to always put 1000 kg on the camel, so that the ratio (eaten/carried) is minimized.

Thus the genral strategy is as follows - for first mile, the camel makes 10 rounds, each time with 1000 kg of grass. (thus it carries 1000 kgs , (eats 1 kg in the process) dumps the remaining (999 kg) at 1 mile distance and comes back. In the return journey, he doesnot need anything to eat since he is not carrying anything (As per condition 1)
So for 1st mile, 10 kg of grass is eaten. Calculate for each mile similarly.

Code:

int grassLeft()
{
int g = 10000; // 10000 kg of grass to start with
int d = 1000; // 1000 miles to go ....

while(d) // loop till we have some more to go...
{
int eat =g/1000 + (( ( g %1000 ) == 0) ? 0 : 1) ;

/*
This is the amount eaten for the journey from d to d-1. Observe that extra 1 is added to compenstate for the "last" trip from d to d-1, which would (possibly) carry less than 1000 kg)
*/

g -= eat; // grass left
d--; // one mile less .
}
return g;
}

This gives 3381.

Title: Re: maximum amount of grass carried
Post by Grimbal on Oct 15^th, 2005, 2:06am

Aah, I see, I assumed the camel eats both ways, loaded or not.

Title: Re: maximum amount of grass carried
Post by Neelesh on Oct 15^th, 2005, 3:24am

Well, I just happened to solve this problem using Template Metaprogramming.

I am aware that majority of the readers are not aware of this deep concept of C++ called Template metaprogramming. But for those few who know that, here is the code (its very simple to understand if one knows this paradigm of programming):

The beauty of template metaprogramming is that it solves this problem at compile time - thus there is practically no runtime overhead!!

Code:

#include <iostream>

using namespace std;

template <int g, int d> struct Camel{
enum { Val = Camel<g- (static_cast<int>(g/1000) + ((g%1000==0)?0:1)),d-1>::Val };
};

template<int g> struct Camel<g,0> {
enum { Val = g };
};

main()
{
cout << Camel<10000,1000>::Val << endl;
}

To compile this, use

g++ -ftemplate-depth-1001 filename

Title: Re: maximum amount of grass carried
Post by otter on Oct 18^th, 2005, 4:49am

on 10/15/05 at 02:06:35, Grimbal wrote:

Aah, I see, I assumed the camel eats both ways, loaded or not.

That's the way I read it, too. The original problem states that the camel will not budge unless it is continuously chewing grass. It says nothing about whether it does so only while carrying a load. So we must assume that if we drop off the 999 kilos of grass and have none for the return journey, the camel will not budge.

Title: Re: maximum amount of grass carried
Post by Neelesh on Oct 18^th, 2005, 5:35am

Yes....Now after I re-read the problem I think thats a fair point - I believe I solved the problem with wrong assumptions :(

Title: Re: maximum amount of grass carried
Post by Grimbal on Oct 18^th, 2005, 8:20am

Another assumption you make is that you can move only full miles. I would say you can move fractions of a mile provided you always have some grass, even a fraction of kg, to feed the camel.