Çətin Marşrutlar
Olimpiadaya hazırlıq çərçivəsində, ölkənizin komandası üçün velosiped təlim marşrutları təklif etməyiniz xahiş olunur. Təlim komitəsi, ölkə ərazisindəki müxtəlif məkanlar arasında səyahət marşrutlarını müəyyənləşdirmək istəyir. Hər bir marşrutun çətinlik səviyyəsi, təpələrin dikliyinə əsaslanmalıdır.
Sizə üzərinə yüksəklik məlumatları yerləşdirilmiş bir yol xəritəsi təqdim olunacaq. İki və ya daha çox yolun kəsişdiyi hər bir nöqtə öz x-, y-, və z-koordinatları ilə müəyyən edilir. Hər bir yol bir kəsişmə nöqtəsindən başlayır və digər kəsişmə nöqtəsində bitir, düzdür və digər yolların üzərindən körpü və ya altından tunel keçmir. Velosiped sürmənin çətinlik səviyyəsi, d, yol səviyyəli və ya eniş istiqamətində gedildikdə 0-dır. Səviyyəsiz bir yolun çətinliyi, yuxarıya doğru gedildikdə 100*rise/run-dir. Burada rise yüksəliş dəyişməsinin mütləq dəyəri və run isə iki kəsişmə nöqtəsi arasındakı məsafənin üfüqi proyeksiyasıdır. Qeyd edək ki, eniş istiqamətində gedilən yolun çətinlik səviyyəsi sıfırdır.
Bir marşrut, ardıcıl yolların bir-birinin ardınca gəldiyi bir sıra yollardır ki, burada bir yolun sonlandığı kəsişmə nöqtəsindən növbəti yol başlayır. Bu marşrutun çətinlik səviyyəsi d olur, əgər onun bütün yolları arasında velosiped sürmənin maksimum çətinlik səviyyəsi d-yə bərabərdirsə. Komitə həmçinin iki seçilmiş yer arasında istənilən çətinlik səviyyəsi olan marşrutun, əgər belə bir marşrut mövcuddursa, mümkün olan ən qısa məsafəyə malik olmasını istəyir.
Xatırlatma: Döşəmə funksiyası X tam ədədə qədər kəsilmiş X deməkdir.
Giriş verilənləri
Giriş bir çox yol xəritəsindən ibarətdir. Hər bir xəritə təsviri iki qeyri-mənfi tam ədəd N və M ilə başlayır, bunlar öz aralarında boşluqla ayrılmış və bir sətirdə yerləşdirilmişdir, bu isə müvafiq olaraq kəsişmə nöqtələrinin və yolların sayını təmsil edir. 0 < N, M ≤ 10000. Həm N, həm də M-in sıfıra bərabər olması giriş məlumatlarının sonunu göstərir.
Növbəti N sətirin hər biri üç tam ədəd ehtiva edir, bunlar öz aralarında tək boşluqla ayrılmışdır və bir kəsişmə nöqtəsinin x-, y- və z-koordinatlarını təmsil edir. Tam ədədlər 0 və 10000 arasında dəyərlərə malikdir, daxil olmaqla. Kəsişmə nöqtələri öz görünmə sırasına görə bir dəyərdən başlayaraq nömrələnir. Növbəti M sətirin hər biri bir yolun başlanğıc və son kəsişmə nöqtələrini təmsil edən iki tam ədəd ehtiva edir.
Nəhayət, üç tam ədəd s, t və d verilmişdir ki, bunlar müvafiq olaraq təlim marşrutunun istənilən başlanğıc kəsişmə nömrəsi s, bitiş kəsişmə nömrəsi t və çətinlik səviyyəsi d-ni təmsil edir. Etibarlı təlim marşrutu ən azı bir yolun çətinlik səviyyəsinin d olması və heç bir yolun çətinlik səviyyəsinin d-dən böyük olmaması tələb olunur. 0 ≤ d ≤ 10. Əgər təlim marşrutu qapalı dövrə təşkil etməlidirsə, onda s və t eyni kəsişmə nömrələridir.
Çıxış verilənləri
Hər bir yol xəritəsi və istənilən marşrut üçün çıxış bir sətirdən ibarətdir ki, bu da:
təlim marşrutunun ən qısa uzunluğunu bir ondalık yerə qədər yuvarlaqlaşdırılmış şəkildə göstərən bir rəqəm, və ya
əgər uyğun marşrut mövcud deyilsə, tək söz "None".
Xatırlatma: Müsbət R.xxxy ədədini üç ondalık yerə qədər yuvarlaqlaşdırmaq
Əgər dördüncü ondalık yer 5-dən kiçikdirsə, onda yuvarlaqlaşdırılmış dəyər R.xxx-dir
Əks halda, yuvarlaqlaşdırılmış dəyər R.xxx + 0.001-dir
Misallar: 10.3463 dəyəri üçün çıxış 10.346 olmalıdır və 10.3695 dəyəri üçün çıxış ya 10.37, ya da 10.370 olmalıdır.