Abidələr üzrə ekskursiya

Turizm operatoru Parisdə $n$ abidə və muzeyləri ziyarət etməyi özündə cəmləşdirən marşrutlar təklif edir və bu marşrutlar düzbucaqlı şəbəkə kimi modelləşdirilir. Səyahət aşağıdakı kimi həyata keçirilir: avtobus qərbdən şəhərə girir (şərqə yönəlmiş istənilən yolda) və şəhər boyunca şərqə doğru hərəkət edir. Lazım gəldikdə abidə ziyarət etmək üçün sola və ya sağa dönə bilər, bundan sonra şəhərə girdiyi şərqə baxan həmin yola qayıtmalıdır. Bu proses avtobus şəhəri şərq tərəfdən tərk edənə qədər davam edir.

Yuxarıda təsvir edilən şəkildə 6 \times 5 ölçülü şəbəkəyə malik şəhərdə marşrut nümunəsi göstərilib. Bu nümunədə avtobus $(0,2)$ nöqtəsindən şəhərə girir (bu nöqtə şəhərin şimal-qərb küncü kimi qəbul edilir). Əvvəlcə o, əsas yolda birbaşa yerləşən $(1,2)$ nöqtəsindəki abidəni ziyarət edir. Sonra sola dönərək $(1,0)$ nöqtəsindəki abidəni ziyarət edir, əsas yola qayıdır və şərqə doğru hərəkətini davam etdirir. Daha sonra sağa dönərək $(2,4)$ nöqtəsindəki abidəni ziyarət edir, yenidən əsas yola qayıdır, əsas yolda yerləşən $(4,2)$ nöqtəsindəki abidəni ziyarət edir və nəhayət şəhəri $(5,2)$ nöqtəsindən tərk edir.

Bir şəhər kvartalından keçmək 1 vahid yanacaq sayılır. Yuxarıda göstərilən nümunə üçün marşrutun ümumi dəyəri 5 + 2 \times 2 + 2 \times 2 = 13 yanacaq vahididir.

Sizin vəzifəniz — turizm operatoruna avtobusun bütün $n$ abidələri ziyarət edəcəyi məqamda marşrutun ümumi dəyərini minimallaşdırmaq üçün hansı şərq yolunun üzərində hərəkət etməli olduğunu müəyyən etməkdə kömək etməkdir.

Vacib qeydlər

• Avtobusa digər paralel şərq yoluna keçmək qadağandır; o, bütün dövrlərdə girdiyi yolda hərəkət etməli və bu yolda davam etməlidir.

• Eyni nöqtədə bir neçə abidə ola bilər.