İşıqları söndürün (Platin)

Farmer John özünün mal-qara tövləsinə yeni, müasir sağım maşını qurdu, lakin bu maşın o qədər çox elektrik enerjisi istifadə edir ki, bəzən elektrik enerjisinin kəsilməsinə səbəb olur! Bu, o qədər tez-tez baş verir ki, Bessie tövlənin xəritəsini əzbərləyib, bu da onun qaranlıqda tövlədən çıxışı tapmasını asanlaşdırır. Lakin o, elektrik kəsilmələrinin onun tövlədən tez çıxma qabiliyyətinə necə təsir etdiyini bilmək istəyir. Məsələn, o, çıxışı tapmaq üçün qaranlıqda nə qədər əlavə məsafə qət etməli ola biləcəyini bilmək istəyir.

Tövlə tam ədədli təpə nöqtələri (x_1, y_1), \ldots, (x_n, y_n) olan sadə (özü-özünü kəsməyən) çoxbucaqlı ilə təsvir olunur, təpələr saat istiqamətində sadalanır. Onun tərəfləri növbələşir: horizontal (x oxuna paralel) və vertikal (y oxuna paralel); birinci tərəf bu iki tipdən istənilən biri ola bilər. Çıxış (x_1, y_1) nöqtəsində yerləşir. Bessie tövlənin içərisində, hərəkətə i \u003e 1 üçün müəyyən bir (x_i, y_i) təpəsində olarkən başlayır. O, yalnız sərhəd boyunca hərəkət edə bilər — saat istiqamətində və ya saat istiqamətinin əksinə, lazım olduqda hər dəfə təpəyə çatanda istiqaməti dəyişərək. Onun məqsədi çıxışa çatmaq üçün mümkün olan minimal məsafəni qət etməkdir. İşıq yandığı zaman bunu etmək, əlbəttə ki, kifayət qədər sadədir: o, mövcud mövqeyindən çıxışa saat istiqamətində və ya saat istiqamətinin əksinə hərəkət edə bilər, daha qısa yolu seçərək.

Bir gün işıq sönür və Bessie çaşqınlıq içində məhz hansı təpədə olduğunu unudur. Xoşbəxtlikdən, o hələ də tövlənin dəqiq xəritəsini xatırlayır, ona görə də sərhəd boyunca hərəkət edərək və lamisə hissini istifadə edərək öz yerini müəyyən etməyə cəhd edə bilər. O, hər dəfə bir təpədə olarkən (o cümlədən başlanğıc təpəsində), həmin təpədəki dönüşün sola və ya sağa olduğunu, eləcə də bu təpənin çıxış olub-olmadığını müəyyən edə bilər. Tövlənin bir tərəfi boyunca hərəkət edərkən, o həmin tərəfi tam qət etdikdən sonra onun dəqiq uzunluğunu müəyyən edə bilər.

Ümumi halda, Bessie öz yerini dəqiq müəyyən etmək üçün kifayət qədər məlumat əldə edənə qədər öz təpəsindən başlayaraq strateji şəkildə ətraf mühiti araşdıracaq. Bundan sonra o, çıxışa çatmaq üçün mümkün olan minimal qalan məsafəni qət edərək ən qısa yolu asanlıqla müəyyən edə biləcək.

Bessie-yə, ən pis halda (bütün mümkün başlanğıc təpələri üzrə) qaranlıqda hərəkət edərkən qət etdiyi məsafənin işıq yandığı zaman qət etdiyi məsafəyə nisbətən artımının minimal mümkün miqdarını müəyyən etməkdə köməklik edin, hər iki halda onun optimal strategiya istifadə etdiyini fərz edərək. Qaranlıqda "optimal" strategiya, ən pis haldakı bu əlavə məsafəni minimuma endirən strategiya hesab olunur.