Vom calcula concret distantele pentru cele doua sensuri. Sa presupunem ca locatarul trece prin cladirile x, x1, x2, ..., xn, y. Distanta parcursa va fi dist(x, x1) + dist(x1, x2) + ... + dist(xn-1, xn) + dist(xn, y). Dar distanta dintre oricare 2 constructii consecutive este 1, deci distanta totala parcursa este defapt numarul de cladiri diferite de x prin care trece locatarul.

Pentru sensul rosu, cum x < y, locatarul va trece intotdeauna prin cladirile x + 1, x + 2, ..., y - 1, y. Numarul acestora este y - (x + 1) + 1 = y - x. Pentru sensul albastru, locatarul va trece prin cladirile x - 1, x - 2, ..., 2, 1, 2 * N, 2 * N - 1, ..., y + 1, y. Pentru a calcula numarul de cladiri prin care locatarul in acest caz, vom imparti in doua calculele. Intai vom calcula distanta dintre x - 1 si 1, apoi distanta dintre 1 si y. Astfel, distanta parcursa pe portiunea x - 1 si 1 este (x - 1) - 1 + 1 = x - 1. Distanta pe portiunea 1 si y este distanta de pe portiunea 2 * N si y plus 1. Pe portiunea 2 * N si y, locatarul va trece prin orasele 2 * N - 1, 2 * N - 2, ..., y + 1, y. Deci distanta pe portiune este 2 * N - 1 - y + 1 = 2 * N - y. Distanta totala pe banda albastra este x - 1 + 1 + 2 * N - y = x + 2 * N - y. In concluzie, distanta dintre orasele x si y este min(y - x, x + 2 * N - y).

Pentru sensul rosu, cum x < y, locatarul va trece intotdeauna prin cladirile x + 1, x + 2, ..., y - 1, y. Numarul acestora este y - (x + 1) + 1 = y - x. Pentru sensul albastru, locatarul va trece prin cladirile x - 1, x - 2, ..., 2, 1, 2 * N, 2 * N - 1, ..., y + 1, y. Pentru a calcula numarul de cladiri pe care le parcurge locatarul in acest caz, vom calcula intai cata distanta trebuie sa parcurga pentru a ajunge la cladirea 2 * N, dupa aceea ce distanta trebuie sa mai parcurga de la cladirea 2 * N la cladirea y. Pentru a ajunge la cladirea 2 * N, locatarul trebuie sa treaca pe langa cladirile x - 1, x - 2, ..., 1 si 2 * N.
Pentru a ajunge la coordonata 1, el trebuie sa parcurga x - 1 cladiri, iar pentru a ajunge la de la 1 la 2 * N mai trebuie sa mearga 1 unitate de distanta. Asadar, distanta dintre x si 2 * N este x. Acum, ppornind din 2 * N, locatarul trebuie sa ajunga in y. El parcurge cladirile 2 * N - 1, 2 * N - 2, ..., y + 1, y. In total, aceste cladiri sunt in numar de 2 * N - 1 - y + 1 = 2 * N - y. Deci distanta totala pentru sensul albastru este x + 2 * N - y. Evident, distanta minima dintre cladirea x si cladirea y va fi acum min(y - x, x + 2 * N - y).

Complexitatea algoritmului este O(N) timp si O(1) memorie. Pentru o sursa de referinta, puteti consulta sursa mea din arhiva Monthly: http://pastebin.com/BH2uir8P