← All solutions

Shortest judge solution: 321 bytes. Shortest team solution (during contest): 413 bytes.

Python solutions by the judges: both Pypy and CPython

This was one of the two easiest problems of the set. Given a guess for the value of c, we can compute the resulting distance that this would result in. If the guess of c was too high, the travelled distance will be too high (because in each segment travelled we’re overestimating the speed), and if the guess was too low, the travelled distance will be too low. Thus we can simply binary search for the correct value of c. The potentially tricky part is what lower and upper bounds to use for the binary search. If in some segement the speedometer read v, the value of c needs to be at least −v. Thus, c needs to be at least − min v. For the upper bound, a common mistake was to assume that c could never be larger than 10⁶. This is almost true, but not quite – the maximum possible value is 10⁶ + 1000 (our true speed can be as large as 10⁶, but the reported readings of the speedometer can be −1000).