A - Hands Editorial by evima


Since the buildings are not so high, we can solve the problem fast enough using the shortest path algorithms such as Dijkstra’s and Floyd-Warshall. We can also solve it in \(O(1)\) time with simple implementation, as follows.

Consider the sequence of floors arranged in the order visited when going from the \(1\)-st floor of A to the \(100\)-th floor of B using only corridors:

A1 - B1 - A2 - B2 - \(\dots\) - A100 - B100

In this sequence, we can move one floor in \(x\) minutes and move two floors in \(y\) minutes. Let \(y'\) be \(\min(2x,y)\), the shortest time needed to move two floors.

Then, if the destination is two or more floors away from where we are (in the above sequence), the optimal action is to move two floors in \(y'\) minutes; if the destination is just one floor away, the optimal action is to move one floor in \(x\) minutes.

Thus, the answer is \(\text{floor}(d/2) y' + x\), where \(d=|2b+1-2a|\) is the difference between the positions of the \(a\)-th floor of A and \(b\)-th floor of B in the sequence. Here, \(|x|\) denotes the absolute value of \(x\), and \(\text{floor}(x)\) denotes truncation, that is, the greatest integer not exceeding \(x\).

Sample Implementation in C++

posted:
last update: