Markov Qatarları#3226
Hollandiya Dəmiryolu Şirkəti NS üçün işlər yaxşı getmir. Texniki problemlər səbəbindən, onlar çoxlu qatar xidmətlərini əvvəlcədən xəbərdarlıq etmədən ləğv etməyə məcbur olurlar. Bu, evdən məktəbə qatarla gedən tələbələr üçün çox əsəbi bir vəziyyətdir.
Vəziyyətin ən pis tərəfi isə ləğvlərin təsadüfi olmasıdır. Heç kim əvvəlcədən bir qatar xidmətinin ləğv ediləcəyini bilmir; ləğv yalnız rəsmi yola düşmə vaxtında elan edilir. Adətən evdən məktəbə bir neçə mümkün marşrut olduğuna görə, insanlar tez-tez "əgər bunu əvvəlcədən bilsəydim, başqa marşrutu seçərdim" deyə düşünürlər.
Son zamanlarda, NS-in statistika şöbəsi bu problemə inqilabi bir həll tapdı. Onlar bəzi qatar xidmətlərinin digərlərindən daha tez-tez ləğv edildiyini müşahidə etdilər. Sərnişinlərə kömək etmək üçün bu məlumatı dərc etməyə qərar verdilər. Yeni cədvəllər hər bir xidmətin yola düşmə və çatma vaxtını deyil, həm də ləğv edilmə ehtimalını göstərəcək.
NS-in normalda stansiyalar arasında ən sürətli marşrutu tapan səyahət-planlaşdırma proqramı, sərnişinlərin vaxtında çatma ehtimalını artıran marşrutu tapmaq üçün yenilənməlidir. Bu, sərnişinlərə problem yarada biləcək qatarları keçərək, bir az daha uzun, lakin daha etibarlı bir marşrutla məktəbə getməyə kömək edir.
Yeni cədvəllər, yola düşmə stansiyası və vaxtı, təyinat stansiyası və istənilən çatma vaxtı verildikdə, təyinat yerinə vaxtında çatma ehtimalını artıran marşrutu tapın.
Bu halda marşrut sadəcə sərnişinin ziyarət etdiyi stansiyaların sıralı siyahısıdır, yola düşmə stansiyası ilə başlayır və təyinatla bitir. Sərnişin marşruta sadiq qalacaq, hər dəfə növbəti stansiyaya ilk mümkün qatarı götürəcək. Əgər qatar ləğv olunarsa, sadəcə həmin stansiyaya növbəti qatarı gözləyəcək.
Vaxtında çatma ehtimalı, yuxarıda təsvir edilən marşruta əməl edərkən sərnişinin istənilən çatma vaxtından əvvəl və ya vaxtında təyinat stansiyasına çatma ehtimalı kimi qəbul edilir. Bu ehtimalı hesablayarkən, qatar xidmətlərinin bir-birindən müstəqil olaraq və cədvəldə göstərilən ehtimallara uyğun olaraq ləğv edildiyini fərz edirik.
Girişin ilk sətri qaçışların sayını göstərən müsbət tam ədəd ehtiva edir. Hər bir qaçış üçün giriş aşağıdakı kimidir:
Cədvəldəki qatarların sayını göstərən müsbət tam ədəd n olan bir sətir (n ≤ 100).
Cədvəli təsvir edən n sətir. Hər sətir bir qatarı təsvir edir, onun yola düşmə stansiyası x, yola düşmə vaxtı t_x, təyinat stansiyası y (x ≠ y), çatma vaxtı t_y (t_x < t_y) və ləğv edilmə ehtimalı p. Stansiyalar 'A' ... 'L' aralığında böyük hərflərlə təyin edilir. Vaxtlar hh:mm formatındadır, burada 00 ≤ hh < 24 və 00 ≤ mm < 60. Ehtimal p 0.0 ≤ p < 1.0 olan onluq real ədəddir. Giriş elementləri boşluqlarla ayrılır.
Yola düşmə stansiyası a, ən erkən yola düşmə vaxtı t_a, təyinat stansiyası b (a ≠ b) və istənilən çatma vaxtı t_b (t_a < t_b) olan bir sətir. Stansiya identifikatorları və vaxtlar cədvəldəki kimidir.
Çıxış hər bir qaçış üçün iki sətirdən ibarətdir. Hər bir qaçışın ilk sətri sərnişin üçün ən yaxşı mümkün marşrutu stansiya identifikatorlarının boşluqlarla ayrılmış siyahısı kimi ehtiva edir. İkinci sətir sərnişinin verilmiş marşruta əməl edərkən vaxtında çatma ehtimalını ehtiva edir. Ehtimal dəqiq bir onluq real ədəd kimi formatlanmalıdır, ondalıq nöqtədən əvvəl dəqiq bir rəqəm və ondalıq nöqtədən sonra dəqiq 4 rəqəm olmalıdır. Adi yuvarlaqlaşdırma qaydaları tətbiq edilir: növbəti rəqəm ≥ 5 olarsa yuxarı yuvarlaqlaşdırın, əks halda aşağı yuvarlaqlaşdırın.
Qeydlər
Aralıq stansiyada qatar dəyişərkən, ən erkən mümkün yola düşmə vaxtı çatma vaxtından bir dəqiqə sonra olur.
Bütün vaxtlar eyni gündədir; səyahət gecə yarısını keçmir.
Eyni stansiyadan eyni vaxtda eyni təyinat stansiyasına iki və ya daha çox qatar yola düşmür.
Giriş elədir ki, maksimum ehtimallı unikal marşrut var.
Sərnişin marşrutuna sadiq qalacaq, həmişə növbəti stansiyaya ilk mövcud qatarı götürəcək. Əgər qatar ləğv olunarsa, həmin stansiyaya növbəti qatarı gözləyəcək. O, heç vaxt daha sürətli qatarlar və ya fərqli marşrutlar götürməyə çalışmayacaq.
Nümunə 1