Rinsing the Cream Can

Time limit1sMemory limit128 MB

Summary
Minimize the whiskey left in a can after at most k rinses, each adding water then pouring out with a fixed residual volume, using at most Vb water.
Level

Medium7 of 10

Topics
Math, Greedy, Binary search, Implementation
Solved
No attempts yet

Problem

Granny keeps her moonshine whiskey in a cream can, and a surprise inspection by Eliot Ness is imminent. Before he arrives she wants to remove as much whiskey from the can as possible.

She can upend the can to pour its contents onto the ground, but because of surface tension and the shape of the can a fixed volume VrV_r of liquid always clings to the inside and cannot be poured out. To wash out more whiskey she has a barrel of rain water and may rinse the can up to kk times.

The can starts holding VwV_w units of pure whiskey. Each rinse works like this:

  1. pour in some amount of water w≥0w \ge 0 (possibly none); the total liquid in the can may never exceed its capacity VcV_c;
  2. mix thoroughly, so the whiskey is spread uniformly through the liquid;
  3. upend the can, leaving exactly VrV_r units of liquid behind (a whiskey-and-water mixture in the same proportion as just before pouring).

Whiskey and water mix perfectly and their volumes are additive. Granny has time for at most kk rinses and a total of VbV_b units of rain water. By choosing how much water to use on each rinse, she wants to minimize the volume of whiskey still left in the can after her final rinse.

Input

The input contains several test cases. Each test case is a single line with five numbers:

  • kk — an integer with 0<k≤1000 < k \le 100, the maximum number of rinses allowed;
  • VbV_b — a real number with Vb>0V_b > 0, the volume of rain water available in the barrel;
  • VwV_w — a real number with Vw>0V_w > 0, the initial volume of whiskey in the can;
  • VrV_r — a real number with Vr>0V_r > 0, the volume of liquid that always remains after upending;
  • VcV_c — a real number with Vc>VwV_c > V_w and Vc>VrV_c > V_r, the capacity of the can.

A line containing a single 00 follows the last test case and must not be processed.

Output

For each test case, print on its own line the minimum possible volume of residual whiskey left in the can after at most kk rinses, rounded to exactly six decimal places.

Notes

The total amount of water used across all rinses may not exceed VbV_b, and the total liquid in the can may never exceed VcV_c at any moment. Assume whiskey and water mix perfectly and that their volumes add: combining xx units of whiskey with yy units of water yields exactly x+yx + y units of liquid.

Examples3

  1. Example 1

    Input
    2 15.0 25.0 1.0 50.0
    0
    
    Expected output
    0.062500
    
  2. Example 2

    Input
    1 10.0 20.0 2.0 50.0
    0
    
    Expected output
    1.333333
    
  3. Example 3

    Input
    4 15.0 30.0 1.0 100.0
    0
    
    Expected output
    0.004630