Given segment distances and speedometer readings plus a total time, find the constant offset c making the summed travel times equal t.
Medium4Binary searchMathImplementationInterviewNo attempts yetTime limit1sMemory limit512 MB
Sheila is a student and she drives a typical student car: old, slow, rusty, and falling apart. Recently the needle on the speedometer fell off. She glued it back on, but she might have placed it at the wrong angle. So when the speedometer reads s, her true speed is s+c, where c is an unknown constant that may be negative.
Sheila kept a careful record of a recent journey and wants to use it to compute c. The journey consisted of n segments. In the ith segment she traveled a distance of di, and the speedometer read si for that entire segment. The whole journey took time t. Help Sheila by computing c.
The speedometer may show a negative reading, but her true speed was greater than zero on every segment.
The first line contains two integers n and t. Here n is the number of segments of the journey (1≤n≤1000), and t is the total time of the journey (1≤t≤106).
Each of the next n lines describes one segment. The ith of these lines contains two integers di and si (1≤di≤1000, ∣si∣≤1000), the distance and the speedometer reading for the ith segment. Time is given in hours, distance in miles, and speed in miles per hour.
A real number c that makes every true speed greater than zero and the total time exactly t always exists. The sum ∑i=1nsi+cdi strictly decreases in c, so that value is unique.
Print the constant c in miles per hour, rounded to exactly six digits after the decimal point. If the value is zero, print 0.000000 and not -0.000000.