Problem A
Bucket Brigade

You are at one end of a line of $n$ people. You and the other $n-1$ people are holding one bucket each, each with a capacity of $x$ liters. You want to move a total of $v$ liters of water from a large tub next to you to a similar tub at the other end of the line. You use your bucket to take water from the tub on your end, turn to the person beside you, pour the contents of your bucket into his and then turn back to the tub and repeat the process. Similarly, each person transfers the contents of his or her bucket to the people beside them, with the last person emptying her bucket into the tub at their end. You want to move the water as efficiently as possible. At the same time, you don’t want to end up with one bucket (the last one) that is almost empty. Instead, you determine the minimum number of bucket loads sufficient to transfer the water, and then you distribute the water evenly so that, each time you draw a bucket from your tub, you take exactly the same amount out.

Buckets can be filled and emptied at a rate of $f$ liters per second, whether they are filled from another bucket, from a tub or emptied into a tub. It takes $t$ seconds to turn to the left or the right, and everyone starts out turned toward you, ready to receive the first bucket load.


Input consists of up to $100$ test cases, one per line. Each test case gives the values of the five parameters: the integer $n$ ($1 \le n \le 1\, 000$), followed by real values for $v$ ($1 \le v \le 2\, 000$), $x$ ($0 < x \le 10$), $f$ ($0 < f \le 5$), and $t$ ($0 < t \le 2$). Each real value has up to $3$ digits past the decimal. It’s guaranteed that $|\lfloor v / x \rfloor - v / x| > 10^{-5}$. Input ends at end of file.


For every test case, output the total time, in seconds, required to get $v$ liters of water to the destination tub in the manner described above. Your answer should have an absolute error of no more than $10^{-5}$.

Sample Input 1 Sample Output 1
25 5.5 6.0 2.5 0.25
1 1000.0 0.3 0.25 1.5
5 100.0 3.0 1.0 0.5
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
David Sturgill
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in