【二分】乗用車問題
1696 ワード
4乗用車問題
ソースプログラム名car.???(pas,c,cpp)実行可能ファイル名car.exeファイル名carを入力.inファイル名carを出力する.out
【問題の説明】
甲、乙二人は同時にA地を出発して、できるだけ早く同時にB地に到着しなければならない.出発時A地には乗用車が1台あったが、この乗用車は運転員のほかに1人しか連れて行けなかった.甲、乙の2人の歩行速度は同じで、車の速度より小さいことが知られている.問:どのように車を利用すれば、二人ができるだけ早く同時に到着することができますか.
【入力】
わずか1行、3つのデータはそれぞれAB両地の距離s、人の歩行速度a、車の速度bを表している.
【出力】
二人が同時にB地に到着するのに要する最短時間.
【例】
car.in car.out
120 5 25 9.6000000000E+00
O(1)アルゴリズムの問題です.しかし、二分でやることができます.簡単にしてください.
考えやすいのは、必然的に乗用車は一人一人しか乗せていないことだ.さもないと必ずこのように等価になる.
そのため、私たちは1人目の車に乗る長さを2人の時間で判断します.
2人目の乗車長をxとし、1人目と2人目の合計時間をそれぞれt 1,t 2とする
必然的にt 2はxと正相関し,t 1はxと負相関すると考えられる.
ソースプログラム名car.???(pas,c,cpp)実行可能ファイル名car.exeファイル名carを入力.inファイル名carを出力する.out
【問題の説明】
甲、乙二人は同時にA地を出発して、できるだけ早く同時にB地に到着しなければならない.出発時A地には乗用車が1台あったが、この乗用車は運転員のほかに1人しか連れて行けなかった.甲、乙の2人の歩行速度は同じで、車の速度より小さいことが知られている.問:どのように車を利用すれば、二人ができるだけ早く同時に到着することができますか.
【入力】
わずか1行、3つのデータはそれぞれAB両地の距離s、人の歩行速度a、車の速度bを表している.
【出力】
二人が同時にB地に到着するのに要する最短時間.
【例】
car.in car.out
120 5 25 9.6000000000E+00
O(1)アルゴリズムの問題です.しかし、二分でやることができます.簡単にしてください.
考えやすいのは、必然的に乗用車は一人一人しか乗せていないことだ.さもないと必ずこのように等価になる.
そのため、私たちは1人目の車に乗る長さを2人の時間で判断します.
2人目の乗車長をxとし、1人目と2人目の合計時間をそれぞれt 1,t 2とする
必然的にt 2はxと正相関し,t 1はxと負相関すると考えられる.
#include
#include
double mid;
const double eps = 1e-8;
double t1,t2,t3,l3,l4;
long s,a,b;
long getint()
{
char tmp;long rs=0;bool sgn=1;
do tmp=getchar();
while (!isdigit(tmp)&&tmp-'-');
if (tmp=='-'){tmp=getchar();sgn=0;}
do rs=(rs<<3)+(rs<<1)+tmp-'0';
while (isdigit(tmp=getchar()));
return sgn?rs:-rs;
}
void calc()
{
t2 = (mid/(double)b);
l3 = mid - t2 * a;
t3 = l3/(double)(b+a);
l4 = ((double)s-mid+t3*b);
t1 = t2 + t3 + (l4/(double)b);
t2 = t2 + (double)(s-mid)/(double)a;
}
int main()
{
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
s = getint();
a = getint();
b = getint();
double l = 0;
double r = s;
while (r-l>-eps)
{
mid = (l+r)/2;
calc();
if (t1-t2-eps)
{
printf("%.40lf",t1);
break;
}
if (t1-t2>eps)
r = mid-1e-9;
else if (t1-t2