Summer Institute '17 Contest 1 P7 - Grand Theft Otto

View as PDF

Submit solution

Points: 7
Time limit: 1.4s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Otto is late for the programming contest that he's supposed to compete in today! The time now is t = 0; Otto just woke up at his house, which is d_1 meters away from the site of the contest. Luckily, Otto prepared so much for waking up yesterday that he can immediately leave his house and jump into his car, which is also considered d_1 meters away from the contest at t = 0. Because Otto is also a certain type of superhero (or supervillain, depending on perspective), he can transform his body into electricity and possess machines (like cars) and start driving them immediately. That's actually how he starts using his car as he leaves his house. The road he takes from his house to the contest site is a straight-line road with n cars parked on the side of the road, including Otto's car. Each of these cars is indexed 1 through n, and car i is parked d_i meters away from the contest site. While possessing car indexed i, Otto can travel v_i meters per second towards the contest site, without needing any time to accelerate. He can also instantaneously switch the car that he is possessing with another whenever the other car is parked and the same distance from the contest as the car he is currently possessing. In such a situation, the new car will instantaneously accelerate to its fastest speed and the old car will stop immediately. Of course, such a switch of car usage does not always have to happen.

Input Specification

The first line of input contains a single positive integer n (n \le 10^5), the number of cars. n lines follow, each with two space-separated positive integers each. The ith of these lines will denote that car i is parked d_i meters away from the contest site and has a top speed of v_i meters per second. The cars will be listed in decreasing order of their distance from the contest.

Output Specification

Output the minimum amount of time it will take for Otto to arrive at the contest site, in seconds. Solutions will be considered correct if their output differs from the judge output by less than 10^{-4} seconds.

Sample Input 1

4 1
2 2

Sample Output 1


Sample Input 2

5 1
4 2
3 3

Sample Output 2


Sample Input 3

7 2
5 6
4 3
4 6
3 9

Sample Output 3



There are no comments at the moment.