A. Wizards and Trolleybuses

Time Limit: 20 Sec

Memory Limit: 256 MB

題目連接

http://codeforces.com/contest/167/problem/A

Description

In some country live wizards. They love to ride trolleybuses.

A city in this country has a trolleybus depot with?n?trolleybuses. Every day the trolleybuses leave the depot, one by one and go to the final station. The final station is at a distance of?d?meters from the depot. We know for the?i-th trolleybus that it leaves at the moment of time?ti?seconds, can go at a speed of no greater than?vi?meters per second, and accelerate with an acceleration no greater than?ameters per second squared. A trolleybus can decelerate as quickly as you want (magic!). It can change its acceleration as fast as you want, as well. Note that the maximum acceleration is the same for all trolleys.

Despite the magic the trolleys are still powered by an electric circuit and cannot overtake each other (the wires are to blame, of course). If a trolleybus catches up with another one, they go together one right after the other until they arrive at the final station. Also, the drivers are driving so as to arrive at the final station as quickly as possible.

You, as head of the trolleybuses' fans' club, are to determine for each trolley the minimum time by which it can reach the final station. At the time of arrival at the destination station the trolleybus does not necessarily have zero speed. When a trolley is leaving the depot, its speed is considered equal to zero. From the point of view of physics, the trolleybuses can be considered as material points, and also we should ignore the impact on the speed of a trolley bus by everything, except for the acceleration and deceleration provided by the engine.

Input

The first input line contains three space-separated integers?n,?a,?d?(1?≤?n?≤?105,?1?≤?a,?d?≤?106) — the number of trolleybuses, their maximum acceleration and the distance from the depot to the final station, correspondingly.

Next?n?lines contain pairs of integers?ti?vi?(0?≤?t1?<?t2...?<?tn?-?1?<?tn?≤?106,?1?≤?vi?≤?106) — the time when the?i-th trolleybus leaves the depot and its maximum speed, correspondingly. The numbers in the lines are separated by spaces.

Output

For each trolleybus print a single line the time it arrives to the final station. Print the times for the trolleybuses in the order in which the trolleybuses are given in the input. The answer will be accepted if the absolute or relative error doesn't exceed?10?-?4.

Sample Input

3 10 10000
0 10
5 11
1000 1

Sample Output

1000.5000000000
1000.5000000000
11000.0500000000

HINT

?

題意

有n輛車，車的加速度為a，他們都要從起點(diǎn)開到終點(diǎn)，起點(diǎn)終點(diǎn)距離為d

第i輛車的發(fā)車時(shí)間是t[i]，最大速度是v[i]

保證，不能超車

問你每輛車到達(dá)終點(diǎn)的時(shí)間是多少

題解：

高中物理題，稍微推推公式O1回答就好了

代碼：

#include<iostream> #include<stdio.h> #include<math.h> using namespace std; int n; double a,d; double t[1000005],v[1000005]; double ans[1000005]; int main() {scanf("%d%lf%lf",&n,&a,&d);for(int i=0;i<n;i++){scanf("%lf%lf",&t[i],&v[i]);if(v[i]*v[i]/(2*a)>=d)ans[i]=sqrt(2.*d/a)+t[i];elseans[i]=v[i]/a + (d-v[i]*v[i]/(2.0*a))/v[i]+t[i];}for(int i=1;i<n;i++){if(ans[i]<ans[i-1])ans[i]=ans[i-1];}for(int i=0;i<n;i++)printf("%.10f\n",ans[i]); }

?

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #114 (Div. 1) A. Wizards and Trolleybuses 物理题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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