Mən Dairəvi Olacağam#6009
Avropada və ABŞ-da populyarlaşan bir yol kəsişməsi növü "dairəvi hərəkət" adlanır. Sürücü dairəvi hərəkətə daxil olduqda, artıq dairəvi hərəkətdə olan avtomobillərə yol verir və sonra düzgün çıxışa doğru hərəkət edir. Dairəvi hərəkətlərdə bir neçə zolaq ola bilər ki, bunlar da yol strukturu daxilində dövr edir və çıxır, mərkəzi sahə isə adətən dairəvi olur. ABŞ-da avtomobillər saat əqrəbi əksinə istiqamətdə hərəkət edir, Birləşmiş Krallıqda və sol tərəfdə sürmənin norma olduğu yerlərdə isə avtomobillər saat əqrəbi istiqamətində dövr edir.
Roundoslaviya adlı xüsusi bir ölkə, bütün yol kəsişmələri üçün dairəvi hərəkətlərdən istifadə edir. Dairəvi hərəkətlər çox populyar olduğu üçün hökumət mərkəzi dairənin kifayət qədər böyük ola biləcəyinə qərar verib. Onlar mərkəzdə parklar yerləşdirməyi planlaşdırırlar. Bu, Roundoslaviya turizm bürosu üçün bir problem yaradır; xəritədə iki nöqtə arasındakı məsafə, turizm bələdçilərində çap etmək istədikləri bir şey, kəsişmələrdə artan məsafə səbəbindən daha uzun olacaq.
Roundoslaviyalılar yolun sağ tərəfində sürürlər, buna görə də saat əqrəbi əksinə istiqamətdə hərəkət edirlər. Beləliklə, sağdan (Şərq) kəsişməyə daxil olan və aşağıdan (Cənub) çıxan bir avtomobil dairənin dörddə üçü (¾) qədər dövr edəcək. Əgər mərkəzi ada 500 metr diametrindədirsə, avtomobil 500 metr diametrində olan dairənin çevrəsinin ¾ hissəsini qət edəcək. Ümumiyyətlə, Şərqi 0 dərəcə, Şimalı 90 dərəcə, Qərbi 180 dərəcə və s. hesab etsək, bunu "avtomobil sıfır dərəcədən daxil olur və 270 dərəcədə çıxır" kimi yenidən ifadə edə bilərik. Dairəvi hərəkətlər arasında lazım olan yol miqdarını minimuma endirmək üçün yerləşdirilir, belə ki, avtomobillər təsadüfi bir nöqtədə, məsələn, 48 dərəcədə daxil ola bilər və 190 dərəcədə çıxa bilər. Həmçinin, digər avtomobillər 190 dərəcədə daxil olub 48 dərəcədə çıxa bilər.
Xəritədə yerlər arasındakı məsafələri hesablamaq üçün səyahət bürosu bu əlavə dairəvi hərəkət məsafələrini daxil etmək istəyir ki, ölkəyə gələn ziyarətçilər sürmə vaxtlarının nə qədər olacağını dəqiq təxmin edə bilsinlər.
Dairəvi hərəkətlər, onları birləşdirən yollar və başlanğıc və son dairəvi hərəkətlər haqqında məlumat verildikdə, başlanğıc və son dairəvi hərəkətlər arasındakı minimum məsafəni və müvafiq marşrutu müəyyən edin. Düzgün marşrut həmişə unikal olacaq.
Nəzərə alınacaq təsadüfi sayda hallar olacaq. Giriş bir tam ədəd ilə başlayır ki, bu da halların sayını göstərir. Bu sətirdən sonra birinci halın girişi, sonra ikinci halın girişi və s. gəlir.
Hər bir halın girişi bir tam ədəd NRB (1 ≤ NRB ≤ 25) ilə başlayır ki, bu da dairəvi hərəkətlərin sayıdır. Bu sətirdən sonra NRB sətir gəlir, I-ci sətir (1 ≤ I ≤ NRB) I-ci dairəvi hərəkətin diametrini metrlə verir.
Hər bir halın girişindəki növbəti sətir dairəvi hərəkətləri birləşdirən yolların sayını göstərən bir tam ədəd NRD (1 ≤ NRD ≤ 100) ehtiva edir. Bu sətirdən sonra NRD sətir gəlir (yəni, hər bir yol üçün bir), hər biri bir və ya daha çox boşluqla ayrılmış beş (5) tam ədəd ehtiva edir. İlk iki tam ədəd yol ilə birləşdirilən dairəvi hərəkətləri müəyyən edir. Üçüncü tam ədəd yolun uzunluğunu metrlə verir, lakin dairəvi hərəkətlər daxilində qət edilə biləcək hər hansı məsafəni daxil etmir. Dördüncü tam ədəd yolun birinci tam ədəd ilə müəyyən edilən dairəvi hərəkətə hansı bucaqla bağlandığını göstərir. Eyni şəkildə, beşinci tam ədəd yolun ikinci tam ədəd ilə müəyyən edilən dairəvi hərəkətə hansı bucaqla bağlandığını göstərir. Bucaqlar həmişə qeyri-mənfi və 360 dərəcədən kiçik olacaq.
Hər bir halın girişindəki son sətir boşluqla ayrılmış iki tam ədəd ehtiva edir. Bu tam ədədlər başlanğıc və son dairəvi hərəkətləri müəyyən edir ki, minimum məsafə və müvafiq marşrut müəyyən edilsin.
Yollar bir az əyri ola bilər; dairəvi hərəkətdən 90 dərəcədə çıxmaq mütləq 270 dərəcədə digərinə daxil olmaq demək deyil. Biz bununla maraqlanmırıq. Həmçinin, heç bir tək istiqamətli yol yoxdur və hər hansı bir dairəvi hərəkət cütünü birbaşa birləşdirən ən çox bir yol var.
Bir dairəvi hərəkət daxilində qət edilən məsafəni müəyyən edərkən, hesablamalar real ədədlərlə aparılmalı və sonra tam ədəd əldə etmək üçün kəsilməlidir.
Dairəvi hərəkətə girişdə "U-dönüşlər" icazə verilmir. Eyni bucaqla daxil olmaq və çıxmaq üçün sürücü tam dövr etməlidir—360 dərəcə.
Nümunə: Aşağıdakı Nümunə Girişdə göstərilən girişi nəzərdən keçirin. İki hal nəzərə alınmalıdır. Birinci halda 9 dairəvi hərəkət (diametrləri 500, 450, …, 1500) və 12 yol var. İlk yol 6 və 1 dairəvi hərəkətləri birləşdirir və 15000 metr məsafəyə malikdir. Bu, 6 dairəvi hərəkətinə 0 dərəcədə və 1 dairəvi hərəkətinə 180 dərəcədə bağlanır. Bu halda, 6 və 9 dairəvi hərəkətləri arasında uyğun marşrutu tapmalısınız.
Qeyd edək ki, başlanğıc və son nöqtələrə daxil olmaq və ya çıxmaqla əlaqəli əlavə məsafə yoxdur. Birinci nümunə halında, altı dairəvi hərəkətdən ilkin çıxış heç bir əlavə məsafə əlavə etmir və doqquz dairəvi hərəkətə daxil olmaq da əlavə məsafə əlavə etmir. Sadə bir nümunə olaraq, bir və altı dairəvi hərəkətlər arasındakı məsafə soruşulsa, bu sadəcə 15000 metr olacaq. Başqa bir nümunə olaraq, bir dairəvi hərəkətdən bir dairəvi hərəkətə məsafə sıfır metrdir. Bu halda marşrut 1-dir.
Hər bir giriş halı üçün hal nömrəsini (1, 2, …), başlanğıc və son nöqtələr arasındakı məsafəni və marşrutu göstərilən formatda çap edin. "Distance: " və "Path: " sətirlərini üç boşluqla girintiləyin və hər bir halın çıxışının son sətiri kimi boş bir sətir daxil edin. Göstərilən formata uyğun olun.
Nümunə 1