Revizia anterioară Revizia următoare
Runda 9 a atras 112 participanti. Dintre acestia, 103 au trimis cel putin o sursa, iar 88 de concurenti au rezolvat corect cel putin o problema. Setul de probleme ales a fost unul mai usor decat in rundele precedente. Spre deosebire de ultimele 3 runde, unde concurentii au putut rezolva maxim 3 probleme in timp de concurs, in runda asta 5 concurenti au rezolvat corect toate problemele. Cei cinci: 
Serviciu
Aceasta a fost problema simpla a setului. 86 concurenti au trimis o sursa corecta in timpul concursului la ea. De asemenea, cea mai rapida submisie corecta a venit dupa doar 4 minute de la inceperea rundei, apartinand castigatorului premiului IXIA si al rundei
Pentru a rezolva problema, trebuie sa aflam intai, pentru fiecare dintre cei N locatari, distanta minima dintre birou si locuinta. Distanta maxima parcursa va fi maximul acestor N valori calculate.
Cum calculam distanta minima dintre 2 blocuri? Fie x coordonata locuintei si y coordonata biroului. Putem presupune ca x < y. In cazul in care x > y, putem interschimba valorile lui x si y. Interschimbarea nu schimba rezultatul, deoarece distanta minima de la locuinta la birou este aceeasi cu distanta minima de la birou la locuinta.
Acum locatarul nostru trebuie sa se plimbe pe conturul cercului (pornind din x si ajungand in y). El se poate plimba fie in sens trigonometric (reprezentat cu rosu in desenul din stanga) fie in sens orar (reprezentat cu albastru). Nu are niciun rost ca locatarul sa-si aleaga un sens de deplasare si apoi, undeva in drumul sau sa si-l schimbe. Practic schimbarea sensului va anula ce a mers el inainte, crescand distanta parcursa de el inutil. Asadar, distanta minima va fi minimul dintre distanta obtinuta daca ar alege sensul rosu si distanta obtinuta daca ar alege sensul albastru.
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 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).
Formula de baza folosita pentru rezolvarea problemei a fost ca numarul de numere dintr-o multime {A, A + 1, A + 2, .., B - 1, B} este B - A + 1. 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
