## Editorial for BPC 1 S2 - Train Commute

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: BalintR

Hint

for the first subtask fits in the query limit. Maybe binary search?

This subtask was meant to reward all kinds of binary search solutions and linear solutions that use more than queries. The outline of one is provided below.

Finding the position of any station when none of the stations are known can be hard. Therefore, we start by binary searching for the positions of the first and last stations. To do so, we first calculate ? 0 C to get the total amount of time saved by using the train as opposed to walking all the way from to . This is also the distance between the first and last stations. Then we binary search for the smallest value of such that you save the same amount of time by using the train instead of walking from to as you did in the initial query. This value of is the position of the rightmost station. Then we can calculate the position of the leftmost station by subtracting by the value we got in our first query.

After we have the position of the leftmost station, we can do some other type of binary search for each subsequent station. For example, we could take a station and binary search to its right for the smallest position where we can get to it faster than walking. This will be roughly halfway between the current and next station and we can use the result of the final query to determine the exact location of the next station.

Number of queries:

Hint

If we have determined that there are stations at positions and , is there an easy way to check for the position of a station between them?