Tıxac
Moskva tıxaclarında ən əsəbi məqam, sürücülərin daha sürətli hərəkət etmək üçün zolaqları tez-tez dəyişməyə çalışmasıdır. Bu məsələdə bu strategiyanın məntiqli olub-olmadığını araşdırmalısınız.
Tıxacın nisbətən sadə riyazi modelini nəzərdən keçirəcəyik. Fərz edək ki, N zolaqlı bir yol var, zolaqlar 1-dən N-ə qədər nömrələnib və i-ci zolaq t anında b_i+a_i·sin(t+δ_i) sürəti ilə hərəkət edir. Həmişə b_i > a_i olduğu üçün hərəkət sürəti həmişə müsbətdir. İstənilən vaxt zolağı dəyişə bilərsiniz, x-ci zolaqdan y-ci zolağa keçmək c·|x-y| vaxt aparır. Bu müddət ərzində irəli hərəkət etmə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 anında 1-ci zolaqda başlayırsınız və istənilən zolaqda bitirə bilərsiniz.
Giriş verilənləri
Girişin ilk sətri iki tam ədəd N və d və bir onluq nöqtə ilə verilmiş c ədədi ehtiva edir, 1 ≤ N ≤ 5, 1 ≤ d ≤ 1000, 0.001 ≤ c ≤ 1000. Növbəti N sətir zolaqları təsvir edir, hər biri iki tam ədəd a_i və b_i və bir onluq nöqtə ilə verilmiş δ_i ədədi ehtiva edir, 0 ≤ a_i < b_i ≤ 100, 0 ≤δ_i < 2π.
Çıxış verilənləri
Çıxışın ilk sətrində d məsafəsini qət etmək üçün tələb olunan minimal vaxtı yazın. Çıxışın ikinci sətrində bunu etmək üçün tələb olunan zolaq dəyişikliklərinin sayı K yazın. K 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 strategiya mövcuddur. Növbəti K sətirdə dəyişikliklərin özlərini yazın, hər sətir yeni zolaq nömrəsini və dəyişiklik başladığı vaxtı ehtiva etməlidir. Dəyişikliklər xronoloji ardıcıllıqla çap edilməlidir. Əgər bir çox mümkün cədvəl varsa, istənilənini çıxış edin.
Bütün onluq nöqtə ilə verilmiş ədədləri mümkün olan maksimal dəqiqliklə çıxış edin. Həllinizin düzgün sayılması üçün cədvəlinizi yoxlamaq ümumi qət edilən məsafədə, zolaq dəyişikliklərinin üst-üstə düşməməsində və s. 10^{-6}-dan çox fərqlərə səbəb olmamalıdır, buna görə də hər onluq nöqtə ilə verilmiş ədədi ən azı 10-12 rəqəm dəqiqliklə çıxış etmək daha yaxşıdır.