Author |
Topic: maximum amount of grass carried (Read 1624 times) |
|
inexorable
Full Member
Posts: 211
|
 |
maximum amount of grass carried
« on: Oct 14th, 2005, 10:07am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Neelesh
Junior Member
Gender: 
Posts: 147
|
|
Re: maximum amount of grass carried
« Reply #1 on: Oct 14th, 2005, 10:43am » |
Quote Modify
|
3381 kg of load can be taken up ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: maximum amount of grass carried
« Reply #2 on: Oct 14th, 2005, 11:46am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: maximum amount of grass carried
« Reply #3 on: Oct 14th, 2005, 11:51am » |
Quote Modify
|
can u plz explain neelesh?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: maximum amount of grass carried
« Reply #4 on: Oct 14th, 2005, 3:10pm » |
Quote Modify
|
I find 1399.767 kg...
|
|
IP Logged |
|
|
|
Neelesh
Junior Member
Gender:
Posts: 147
|
|
Re: maximum amount of grass carried
« Reply #5 on: Oct 14th, 2005, 10:52pm » |
Quote Modify
|
on Oct 14th, 2005, 11:51am, 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: maximum amount of grass carried
« Reply #6 on: Oct 15th, 2005, 2:06am » |
Quote Modify
|
Aah, I see, I assumed the camel eats both ways, loaded or not.
|
|
IP Logged |
|
|
|
Neelesh
Junior Member
Gender:
Posts: 147
|
|
Re: maximum amount of grass carried
« Reply #7 on: Oct 15th, 2005, 3:24am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
otter
Junior Member
Gender:
Posts: 142
|
|
Re: maximum amount of grass carried
« Reply #8 on: Oct 18th, 2005, 4:49am » |
Quote Modify
|
on Oct 15th, 2005, 2:06am, 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.
|
| « Last Edit: Oct 18th, 2005, 4:52am by otter » |
IP Logged |
We shall not cease from exploration. And the end of all our exploring will be to arrive where we started
and know the place for the first time.
T.S. Eliot
|
|
|
Neelesh
Junior Member
Gender:
Posts: 147
|
|
Re: maximum amount of grass carried
« Reply #9 on: Oct 18th, 2005, 5:35am » |
Quote Modify
|
Yes....Now after I re-read the problem I think thats a fair point - I believe I solved the problem with wrong assumptions 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: maximum amount of grass carried
« Reply #10 on: Oct 18th, 2005, 8:20am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print