Екскурсія по пам'ятках

Туристичний оператор пропонує маршрути, що включають відвідини $n$ пам’яток та музеїв у Парижі, який моделюється у вигляді прямокутної ґратки. Тур здійснюється наступним чином: автобус в’їжджає в місто із заходу (по будь-якій вулиці, що спрямована на схід) і рухається на схід через місто. У разі необхідності він може звернути наліво або направо, щоб відвідати пам’ятку, після чого зобов’язаний повернутися на ту саму східну вулицю, по якій він в’їхав у місто. Цей процес триває доти, поки автобус не покине місто зі східної сторони.

Приклад маршруту в місті з ґраткою розміром 6 \times 5 показано на рисунку вище. У цьому прикладі автобус в’їжджає в місто в точці $(0,2)$ (при цьому точка $(0,0)$ вважається північно-західним кутом міста). Спочатку він відвідує пам’ятку в точці $(1,2)$, яка розташована безпосередньо на основній дорозі. Потім автобус повертає наліво і відвідує пам’ятку в точці $(1,0)$, повертається на основну дорогу і продовжує рух на схід. Далі він повертає направо, щоб відвідати пам’ятку в точці $(2,4)$, знову повертається на основну дорогу, відвідує пам’ятку в точці $(4,2)$ (також розташовану на основній дорозі), і нарешті, покидає місто в точці $(5,2)$.

Вважається, що проїзд одного міського кварталу коштує 1 одиницю пального. Для наведеного вище прикладу сумарна вартість маршруту дорівнює 5 + 2 \times 2 + 2 \times 2 = 13 одиниць пального.

Ваше завдання — допомогти туристичному оператору визначити, по якій східній вулиці має рухатися автобус, щоб мінімізувати сумарну вартість маршруту при відвіданні всіх $n$ пам’яток.

Важливі зауваження

• Автобусу заборонено переходити на іншу паралельну східну вулицю; він зобов’язаний завжди повертатися і продовжувати рух по тій самій вулиці, по якій в’їхав у місто.

• В одній і тій самій точці може перебувати декілька пам’яток.