Codeforces Round #364 (Div. 2) D. As Fast As Possible

D. As Fast As Possible

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

On vacations n pupils decided to go on excursion and gather all together. They need to overcome the path with the length l meters. Each of the pupils will go with the speed equal to v1. To get to the excursion quickly, it was decided to rent a bus, which has seats for k people (it means that it can't fit more than k people at the same time) and the speed equal to v2. In order to avoid seasick, each of the pupils want to get into the bus no more than once.

Determine the minimum time required for all n pupils to reach the place of excursion. Consider that the embarkation and disembarkation of passengers, as well as the reversal of the bus, take place immediately and this time can be neglected.

Input

The first line of the input contains five positive integers n, l, v1, v2 and k (1 ≤ n ≤ 10 000, 1 ≤ l ≤ 109, 1 ≤ v1 < v2 ≤ 109, 1 ≤ k ≤ n) — the number of pupils, the distance from meeting to the place of excursion, the speed of each pupil, the speed of bus and the number of seats in the bus.

Output

Print the real number — the minimum time in which all pupils can reach the place of excursion. Your answer will be considered correct if its absolute or relative error won't exceed 10 - 6.

Examples
input
5 10 1 2 5 
output
5.0000000000 
input
3 6 1 2 1 
output
4.7142857143 

Note

In the first sample we should immediately put all five pupils to the bus. The speed of the bus equals 2 and the distance is equal to 10, so the pupils will reach the place of excursion in time 10 / 2 = 5.

题意：

有n个小学生，每个小学生的走路速度为v1，有一个汽车，速度为v2，有k个座位，每个小学生只能上一次车，问全部到达距离L的终点最短需要的时间

题解：

要想达到最短的时间，肯定只有汽车运最后一组学生和第一组学生同时到达终点，这里要好好推敲一下，画图看看，就知道求的是一个数学的追及问题

最后推出的公式可以人工求解，也可以二分

 1 #include<cstdio>
 2 const double eps=1e-10;
 3 double l,v1,v2;
 4 int n,k,g;
 5 /*
 6     设t'为汽车运第一组小学生的时间
 7     可以列出一个方程：
 8     ((t'*v2-t'*v1)/(v1+v2)+t')*(g-1)*v1+t'*v2=L;
 9     g为汽车一共要运多少次
10     因为只有一个未知量，并且是一次的，然后可以解出t'
11     然后最终的答案t=((t'*v2-t'*v1)/(v1+v2)+t')*(g-1)+t'
12     我不想去解上面的方程所以用二分来解出t'，然后算答案
13 */
14 bool check(double x)
15 {
16     double ans=(x*v2-x*v1)/(v1+v2)+x;
17     ans=ans*(g-1)*v1+x*v2;
18     if(ans>l+eps)return 0;
19     return 1;
20 }
21 
22 double fuck()
23 {
24     double ll=0,rr=l/v1,m;
25     for(int i=1;i<=100;i++)
26     {    m=(ll+rr)/2;
27         if(check(m))ll=m;else rr=m;
28     }
29     return ll;
30 }
31 
32 int main()
33 {
34     scanf("%d%lf%lf%lf%d",&n,&l,&v1,&v2,&k);
35     g=n/k+(n%k!=0);
36     double an=fuck(),ans;
37     ans=(an*v2-an*v1)/(v1+v2)+an;
38     ans*=(double)(g-1);
39     ans+=an;
40     printf("%.10lf
",ans);
41     return 0;
42 }

View Code