Yol tıxacları
Samara üçün Moskvadakı tıxaclarda sürücülərin daha sürətli hərəkət etmək üçün zolaqları tez-tez dəyişməsi xoşagəlməz bir haldır. Bu məsələdə belə bir davranışın məntiqli bir strategiya olub-olmadığını müəyyən etməlisiniz.
Biz yol tıxacının nisbətən sadə bir riyazi modelini öyrənəcəyik. Fərz edək ki, yol n zolaqdan ibarətdir, 1-dən n-ə qədər nömrələnmişdir. i-ci zolaqda hərəkət t vaxtında b[i] + a[i] * sin(t + delta[i]) sürəti ilə baş verir. Məlumdur ki, b[i] > a[i] bərabərsizliyi həmişə mövcuddur, yəni hərəkət sürəti həmişə müsbətdir. Siz istənilən vaxt zolağı dəyişə bilərsiniz, bu zaman x zolağından y zolağına keçid c * |x - y| vaxtı alacaq. Bu müddət ərzində irəliləmədiyinizi fərz edirik.
d məsafəsini qət etmək üçün lazım olan vaxtı və bu vaxtı əldə etmə üsulunu müəyyənləşdirin. Siz 0 vaxtında 1 zolağında başlayırsınız və istənilən zolaqda bitirə bilərsiniz.
Giriş məlumatları
Birinci sətir iki tam ədəd n və d, həmçinin həqiqi ədəd c (1 ≤ n ≤ 5, 1 ≤ d ≤ 1000, 0.001 ≤ c ≤ 1000) ehtiva edir. Növbəti n sətir zolaqları təsvir edir, hər biri iki tam ədəd a[i] və b[i] və həqiqi ədəd delta[i] (0 ≤ a[i] < b[i] ≤ 100, 0 ≤ delta[i] < 2 * pi) ehtiva edir.
Çıxış məlumatları
Birinci sətirdə d məsafəsini qət etmək üçün lazım olan minimal vaxtı göstərin. İkinci sətirdə bunun üçün lazım olan zolaq dəyişikliklərinin sayı k-ni göstərin. k dəyəri 10^6-dan çox olmamalıdır. Həmişə 10^6-dan çox olmayan zolaq dəyişiklikləri tələb edən optimal strategiyanın mövcudluğu təmin edilir. Növbəti k sətirdə dəyişikliklərin özlərini göstərin: hər sətir yeni zolaq nömrəsini və dəyişiklik vaxtını ehtiva etməlidir. Dəyişikliklər xronoloji ardıcıllıqla göstərilməlidir. Əgər bir neçə mümkün həll varsa, istənilənini göstərin.
Üzən nöqtəli ədədləri maksimum dəqiqliklə göstərin. Həllinizin düzgün hesab olunması üçün cədvəlinizin yoxlanması 10^(-6)-dan çox uyğunsuzluqlara səbəb olmamalıdır (qət edilmiş məsafənin yoxlanılması, zolaq dəyişikliklərinin üst-üstə düşməməsi və s.). Buna görə hər bir həqiqi ədədi ən azı 10 - 12 onluq dəqiqliklə göstərin.