Прогулянка#206

Прогулянка (Розбір)

Магазини стоять на прямій, і відвідати треба всі три. Насправді конкретні координати , , не важливі — важливі лише найлівіша й найправіша точки маршруту.

Позначимо L = \min(0, a, b, c) та R = \max(0, a, b, c); нуль додано тому, що старт теж належить маршруту. Оскільки L \le 0 \le R, зручно ввести відстані \ell = -L \ge 0 до найлівішої точки і r = R \ge 0 до найправішої.

Будь-який маршрут має побувати і в точці , і в точці . Рухаючись по прямій, розумно спочатку піти повністю в один бік, а потім повністю в інший — будь-які «метання» лише додають зайвих кроків. Отже, є рівно два кандидати:

  • спочатку ліворуч, потім праворуч: \ell + (\ell + r) = 2\ell + r;

  • спочатку праворуч, потім ліворуч: r + (r + \ell) = 2r + \ell.

Відповідь — менше з цих двох чисел, тобто \ell + r + \min(\ell, r): сторону, до якої ближче, вигідно пройти двічі.

Окремі випадки обробляються самі собою. Якщо всі магазини з одного боку від нуля, то одна з величин , дорівнює нулю, і формула дає просто відстань до найдальшого магазину.