2018-04-23 08:18 AKDT

[email protected] #5 (Binary) Search


2018-04-30 08:18 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -806 days 21:06:48

Time elapsed


Time remaining


Problem G
Smooth Monkey

Photo by wallygrom
Once upon a time there was a Three-Headed Monkey who had a large stash of banana smoothie on one side of the forest. However, her family lived on the other side of the forest. Our dear monkey wants to suprise them and bring them as much banana smoothie as possible.

Unfortunately, having three heads consumes a lot of energy, so the monkey drinks one millilitre (ml) of smoothie per meter she walks. Note that this is completely continuous, so for example after walking $\frac{\sqrt {2} + \pi }{3}$ meters she has consumed $\frac{\sqrt {2} + \pi }{3}$ ml of smoothie. If she is not carrying any smoothie, she can not move. Furthermore, despite going to the gym every day, the monkey has limited strength and is only able to carry a limited amount of smoothie at a time. Thus she may not be able to bring all the smoothie with her at once.

What she can do however is to leave containers of smoothie anywhere she wants in the forest and then pick them up again later. That way she can for instance move some of the smoothie part of the way, go back to pick up more smoothie, and so on. The monkey starts with all the smoothie in a single place and a (for her purposes) unlimited supply of large containers (large enough so that each of them has room for more smoothie than the monkey can carry). As the monkey only has two hands (despite her large number of heads), she can only carry at most two containers at the same time. The containers are essentially weightless, so the monkey can carry the same amount of smoothie regardless of whether she is carrying one or two containers. They are also bio-degradable, so she can leave empty containers anywhere she likes in the forest without staining her conscience.

How much smoothie (in ml) can she bring to her family on the other side of the forest? The family members are lazy and will not help the monkey transport the smoothie. The monkey does not have to deliver all the smoothie to her family at the same time.

You may make the following somewhat unrealistic (in the sense that no smoothie-transporting monkeys we have ever seen have satisfied them) assumptions:

  • The monkey is able to exactly transfer any real number of ml of smoothie between two containers she is carrying. Similarly, she is able to exactly walk any real number of meters.

  • Any number of containers can occupy the exact same position (they do so at the start, and during the transport the monkey is able to leave several containers in exactly the same spot).

  • Only walking consumes energy: picking up or dropping off a container, turning around, or just standing still, does not consume energy.


The only line of the input contains three integers $D, W, C$ – the distance between the monkey and her family in meters, the total amount of smoothie in ml and finally her maximum carrying capacity in ml. All integers are positive and at most $1\, 000\, 000$.


Output one line with one number, the amount of smoothie in ml that the Three-Headed Monkey is able to bring to her family. Output will be considered correct if it is within relative or absolute error $10^{-7}$.

Sample Input 1 Sample Output 1
1000 3000 1000
Sample Input 2 Sample Output 2
1000 500 1000