Друзі#70

Друзі (Editorial)

Усі будинки стоять на прямій, тому маршрут повністю визначається тим, як далеко ви заходите ліворуч і праворуч.

Позначимо R = \max(0, x_1, x_2, x_3) — найправішу точку, яку треба відвідати, і L = \min(0, x_1, x_2, x_3) — найлівішу. Нуль включено, бо саме там ваш дім — і початок, і кінець маршруту.

Ви маєте побувати в точках і та повернутися в . Отже, кожну ділянку між і доведеться пройти щонайменше двічі — один раз «туди» й один раз «назад». Тому шлях не менший за 2(R - L).

Цю межу легко досягти: спочатку йдемо в один кінець, повертаємось у , потім в інший кінець і знову додому. Або ж проходимо 0 \to L \to R \to 0 — довжина буде та сама.

Отже, відповідь:

2 \cdot \left(\max(0, x_1, x_2, x_3) - \min(0, x_1, x_2, x_3)\right).

Випадки, коли друзі живуть в одній точці або просто вдома, обробляються тією ж формулою автоматично.