Geek Answers Handbook

Algorithm - the maximum number of grains that can be transported

I came across a question posed by Google that I cannot solve:

There is a bunch of N kg grains in an oasis located at a distance of D km from the city. Grains should be transported by a camel cart whose original location is in an oasis. A cart can carry C kg of grain at a time. A camel uses grain as fuel for transportation. It consumes F kg / km.

Write a function that calculates the maximum number of grains ( X kg) that can be sent to the city.

I tried to use recursion, but I could not get much more without confusing myself.

Here is what I still have:

 number of transports = N / C fuel amount for distance D = D * F X = N - ((number of transports) * 2 * (fuel amount for distance D))
+6
source share
4 answers

Assuming N, D, C, and F are inputs, -

 float computeMaxGrains(float N, float D, float C, float F) { //Case when the cart can carry all grains at once if(N <= C) { float remainingGrains = N - D*F; if(remainingGrains >= 0) { return remainingGrains; } else { //out of fuel return 0; } } // Grains consumed per Km = (Total Number of Trips) * F // Total Number of Trips = 2*(N/C) + 1 float grainsConsumedPerKm = (float) (2*(Math.floor(N/C)) + 1); // Remaining grains after Camels fuel = C*(N/C - 1) float remainingGrains = (float) (C*(Math.floor(N/C))); // Distance that the Camel is able to travel before the camel is // 1 less round trip = // (N - Remaining Grains) / grainsConsumedPerKm // From equation N - (grainsConsumedPerKm * distanceTravelled) = // Remaining Grains float distanceTravelled = (N - remainingGrains) / grainsConsumedPerKm; if(distanceTravelled >= D) { return N - (D * grainsConsumedPerKm); } //Use recursion for every 1 less round trip return computeMaxGrains(remainingGrains, D-distanceTravelled, C, F); }
+4
source

I think this problem works best iteratively, forward. I am going to split the solution points. If I wrote one formula, would I use ?: All results are given in Kg.

 The first question is whether there is enough grain, and cart capacity, to justify an initial trip from oasis to town. The camel would eat FD, so if FD >= min(N,C) the answer is 0 If FD < min(N,C), the net amount transferred on the initial oasis to town trip is min(N,C)-FD. The camel is now in town, the remaining grain pile is N-min(N,C), and we have to decide whether to send it back again. If C <= 2FD, no round trip can be profitable. Otherwise consider a round trip with at least C remaining at the oasis. That gains net C-2FD (FD put in the cart in town to keep the camel fed getting to the oasis, C-FD remaining in the cart when it gets back to town). If N>C, we can do floor((NC)/C) of those round trips, net gain floor((NC)/C)*(C-2FD). After doing the initial run and any full cart round trips, the remaining grain pile is N%C, the remainder on dividing N by C. If N%C > 2FD it is worth doing a final trip to empty the grain pile, with an additional net gain of N%C-2FD.
+2
source

As an idea, while there are more D * F grains in the oasis, the camel will travel, with C kg, or how much is left in the oasis. A camel consumes D * F kg when traveling there, removes the load - 2 * D * F kg of grain and returns if enough grain is left to guarantee the return trip.

0
source

This is just an assumption. I'm not quite sure.

Let G (x) denote the maximum amount of grain moving a distance x from the source. Then

 G(x+1)= (G(x)/C)*(C-2F) + max(F,G(x)%C - F)

Now G (0) = N and we need to find G (D) using the above formulation.

The second term max (F, G (x)% CF) means

  • F = when he does not return to collect the remaining grains on his last visit
  • G (x)% C - F = remaining grain in the last visit, and then consumes F to return to the destination
0
source

More articles:


All Articles