Tsunami

Cartesia ölkəsi yalnız Kartesiya müstəvisi ilə təsvir edilə bilər. x-oxu sahil xəttini təmsil edir. Müsbət y yarım müstəvisi quru, mənfi y yarım müstəvisi isə okeandır. Materikdə bir neçə böyük şəhər yerləşir və onların mövqeləri koordinatlarla (x, y) ifadə edilir, burada y > 0. Təəssüf ki, bəzən Cartesia yaxınlığında okeanda sunamilər baş verir və bu zaman bütün ölkə su altında qala bilər. Sular y = 0 nöqtəsindən başlayaraq müsbət y istiqamətində bərabər şəkildə irəliləyir.

Cartesia sunami xəbərdarlıq sistemi inkişaf etdirməyə çalışır. Bu sistem iki komponentdən ibarətdir: sunamini uzaqdan aşkar edə bilən tək meteoroloji mərkəz və şəhərlər arasında düz xətlərlə xəbərdarlığı daşıya bilən kabelli əlaqələr (Simsiz rabitə yoxdur!). Simsiz rabitənin olmamasına baxmayaraq, kabelli əlaqələr xəbərdarlığı demək olar ki, ani şəkildə daşıya bilir.

Bir şəhər təhlükəsiz sayılır, əgər ya meteoroloji mərkəzə sahibdirsə, ya da başqa bir təhlükəsiz şəhərə birbaşa kabelli əlaqəsi varsa (yəni tək meteoroloji mərkəzə çoxlu keçidli kabel yolu varsa).

Təəssüf ki, sadə mühəndislik problemi siyasət tərəfindən daha da mürəkkəbləşdirilir! Əgər A şəhəri xəbərdarlığı B şəhərindən alırsa və B şəhəri A şəhərindən sahilə daha uzaqdadırsa, o zaman A şəhərinin rəhbərləri şikayət edəcək! "Biz B şəhərindən okeana daha yaxınıq, ona görə də xəbərdarlıq bizdən keçməli idi!" Siz də bir ah çəkərək, heç bir şəhərin xəbərdarlığı sahildən daha uzaq olan bir şəhərdən almayacağı bir həll tapmağa razılaşırsınız. (Bu o deməkdir ki, meteoroloji mərkəz sahilə ən yaxın olan şəhərdə olmalıdır.)

Cartesia-nın təsviri verildikdə, hər bir şəhərin təhlükəsiz olduğu və heç bir şəhərin xəbərdarlığı sahildən daha uzaq olan bir şəhərdən almayacağı sunami xəbərdarlıq sistemini qurmaq üçün lazım olan ən az kabel miqdarını tapın.