[ASSIGNMENT] Organization of a tourist group

Question

PART 1:
A group of tourists arrive in the City with the desire to reach the top of a very-very high Mountain located nearby, but they can not take with them enough food to reach the top in a single trip. That's why they decided to go up by some distance and organize a storage of food there. Then go down, take new food, and go up again.

Answer 1

PART 2:
If in a second time the amount of food is still not enough to reach the top, they can organize an other food storage (higher, lower or in the same place) and come back to the city for a new food again. Let's assume that nothing bad will happen with a food stored on the Mountain. Moreover, while passing the distance tourists must eat the food they have with them. They can also recover their food taking it out (all or any part of food) from a storage as soon as they reach it again. Your task as a member of a tourist group is to minimize the amount of required food. Good luck!

Answer 2

PART 3:
More formally:
D - a distance from the city to the mountain's top.
A - maximum amount of food that group of tourist can have with them leaving the city
S - speed of food loss over the distance
B - total amount of required food

Program input: D, A, S
Program output: B

For example:

Input: 5, 10, 1
Output: 10

Input: 4, 10, 1
Output: 8

Input: 10, 40, 3
Output: 80

Some hints for the solution:
1. The group of tourists can pass A/S distance in one direction, but then they will have eaten all their food, so they will not be able to go back to the city and will die in the mountains (try to avoid this situation ;-P )
2. The group of tourists can pass 1/2*A/S distance in one direction and then successfully come back to the city. So if D <= 1/2*A/S they can make a trip in one day and it will require only 2*D*S amount of food. Otherwise (D > 1/2*A/S) it is not possible to make a trip at once and some food have to be stored on a way.
3. For example, D = 3/4*A/S. Then the best solution (at my point of view) is to go up by D1 = 1/4*A/S, store there 1/2*A of food and go down. Note, that we will spend all food we had with us: we passed twice (up and down) D1 distance and for that we used 2*D1*S = 1/2*A of food and we stored 1/2*A of food. Then, the next day we leave the city with A amount of food, go up to our storage, when we arrive we have 3/4*A food left, we take out 1/4*A food from the storage, recovering the full amount of food and keeping also 1/4*A for way back. Then we go up by D2 = 1/2*A/S and we reach the top of the mountain, because we passed D1+D2 = 3/4*A/S = D. And we still have 1/2*A food with us to go down till the storage, take out the rest 1/4*A food from there and successfully reach the city. In a such way total amount of food we spent is B = 2*A.

In short:
You task is to understand the best location for your storages to minimize the amount of required food.
I will give the example of non-optimal algorithm in a couple of days.

Answer 3

Good point for proposing something new with some difficulty. But the description is a bit long to read making this uneasy to try on a mobile in public transportation. Any shorter desc of the problem ?

Answer 4

@VcC Here it is: https://www.sololearn.com/Discuss/1206060/?ref=app