題干：

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個(gè)人，一段路程為L(zhǎng)，走路的速度為v1，公交車的速度v2（公交車只有一輛，且v1<v2），車中最多坐k人，每人最多做一次車，求所有人到終點(diǎn)的最小時(shí)間。?(1?≤?n?≤?10?000,?1?≤?l?≤?109,?1?≤?v1?<?v2?≤?109,?1?≤?k?≤?n)

解題報(bào)告：

因?yàn)樽罴汛鸢覆灰欢ㄊ前阉腥溯d到終點(diǎn)再回去載下一波人，且注意到時(shí)間符合單調(diào)性，可以二分。首先求出一共需要用多少波公交車（因?yàn)関1<v2，所以充分利用公交車肯定可以使得時(shí)間最短），然后維護(hù)當(dāng)前所有人所在的位置，然后求出載的這一波人在當(dāng)前二分的可用時(shí)間下可以最短用多久的公交車，就讓他用這么久的公交車，然后就讓公交車返程來載下一波人。注意統(tǒng)計(jì)時(shí)間的時(shí)候，公交車是不需要返程的，所以不需要加上這一部分時(shí)間。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; const double eps = 1e-8; ll n,k; double L,v1,v2; bool ok(double time) {ll all = n/k + (n%k>0);double pos=0,t=0;for(int i = 1; i<=all; i++) {double tmpt = (L-pos-(time-t)*v1)/(v2-v1);if(i == all) {t += tmpt;break;}double chepos = tmpt * v2;//車本次走的的最遠(yuǎn)長(zhǎng)度 double huit = (chepos-tmpt*v1)/(v1+v2); pos = pos + (tmpt+huit) * v1;t += tmpt+huit;}return t <= time; }int main() {cin>>n>>L>>v1>>v2>>k; double l = 0,r = L,mid,ans=r;int cnt=0;while(cnt++<500) {mid=(l+r)/2;if(ok(mid)) r = mid,ans=mid;else l = mid;} printf("%.8f\n",ans);return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 701D】As Fast As Possible（二分，模拟，数学公式）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。