Wednesday, August 6, 2008

TopCoder SRM 413 Round1 Div 2 Problem 250

Problem Statement
Subway trains can move people quickly from one station to the next. It is known that the distance between two consecutive stations is length meters. For safety, the train can't move faster than maxVelocity meters/sec. For comfort, the absolute acceleration can't be larger than maxAcceleration meters/sec^2. The train starts with velocity 0 meters/sec, and it must stop at the next station (i.e., arrive there with a velocity of 0 meters/sec). Return the minimal possible time to get to the next station.
Definition
Class:
Subway2
Method:
minTime
Parameters:
int, int, int
Returns:
double
Method signature:
double minTime(int length, int maxAcceleration, int maxVelocity)
(be sure your method is public)

Notes
-
Your return value must be accurate to within an absolute or relative tolerance of 1E-9.
-
If the train's speed at time 0 is v0 and the acceleration is always a, then at time t the speed will be (v0 + t * a) and the train will be (v0 * t + 0.5 * a * t^2) away.
Constraints
-
length, maxAcceleration and maxVelocity will each be between 1 and 1000, inclusive.
Examples
0)

1
2
10
Returns: 1.4142135623730951
maxVelocity is very large. So the train can keep speeding up until it reaches position 0.5.
1)

1
1
1
Returns: 2.0

2)

10
1
1
Returns: 11.0
The train reaches its maximum velocity after 1 second, while traveling 0.5 meters. It then travels the next 9 meters in 9 seconds, and takes 1 second to decelerate to 0 m/s while covering the final 0.5 meters.
3)

1
10
1
Returns: 1.1

4)

778
887
384
Returns: 2.458961621570838

5)

336
794
916
Returns: 1.301036207838119

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

`public class Subway2{`
`    public double minTime(int l,int a,int vMax){`
`        double t,t1,t2,v,s;`
`        v=Math.sqrt(2*a*l);`
`        v=Math.min(v,vMax);`
`        t1=v/a;`
`        s=a*t1*t1/2;`
`        t2=(l-2*s)/v;`
`        if(l>=2*s) return 2*t1+t2;`
`        return 2*Math.sqrt((double)l/a);`
`    }`
`}`