Altıbucaqlı yollar#4629
Avtomobil sürücüsü üçün ən qısa marşrutu tapmaq adi bir vəzifədir. Avtomobil ən qısa yolla hərəkət edərsə, bu, xərclərə qənaət edir. Bundan əlavə, əsas marşrut əlçatan olmadıqda, məsələn, bəzi yol işləri səbəbindən, eyni uzunluqda alternativ marşrutları bilmək vacibdir.
Ərazini təsvir etmək üçün onun xəritəsini modelləşdirmək lazımdır. ACM-də yaxınlarda aşkar edilib ki, üçbucaq və düzbucaqlı ərazi modelləri kifayət deyil, buna görə də xəritələrin təsviri üçün altıbucaqlar istifadə etməyə qərar verilib. Düzgün altıbucaqlı torun hüceyrələri (məsələn, arı pətəyi) 1 (istənilən hüceyrədən) başlayaraq və digər hüceyrələrə spiral şəkildə hərəkət edərək nömrələnə bilər. Beləliklə, hər bir hüceyrə öz nömrəsi ilə birmənalı şəkildə müəyyən edilir. Əksinə, hər bir müsbət tam ədəd bir hüceyrəni müəyyən edir.
İki hüceyrə, əgər bir ortaq tərəfə malikdirsə, qonşu adlanır. Sonsuz struktura hər bir hüceyrənin dəqiq altı qonşusu var. Məsələn, 2 nömrəli hüceyrə 1, 3, 7, 8, 9 və 10 ilə qonşudur. Altıbucaqlı yol - bu, hər biri (sonuncudan başqa) növbəti ilə qonşu olan hüceyrələrin boş olmayan ardıcıllığıdır. İki hüceyrə X və Y arasında altıbucaqlı yol - bu, X ardıcıllığın ilk hüceyrəsi, Y isə sonuncu olan yoldur. Yolun uzunluğu - bu, içindəki hüceyrələrin sayı minus birdir. Yolun uzunluğu bütün marşrutu keçmək üçün lazım olan addımların sayını təmsil edir.
Sizə iki hüceyrə arasında ən qısa marşrutun uzunluğunu və eyni uzunluqda qarşılıqlı fərqli marşrutların ümumi sayını tapmaq lazımdır. Fərqli marşrutlar ən azı bir ardıcıllıq üzvündə fərqlənməlidir, yəni tamamilə üst-üstə düşməyən ardıcıllıqlar olmamalıdır.
Giriş məlumatları hər biri ayrı bir sətirdə yerləşdirilmiş bir neçə testdən ibarətdir. Sətir iki tam ədəd X və Y (1 ≤ X, Y ≤ 1000000, X ≠ Y) ehtiva edir, boşluqla ayrılmışdır. Ədədlər iki fərqli hüceyrəni təyin edir. Son testdən sonra giriş məlumatlarının sonunu göstərən iki sıfırdan ibarət bir sətir gəlir.
Hər bir test üçün "There are N routes of the shortest length L." cümləsini çıxarın. L hüceyrələr X və Y arasında ən qısa yolun uzunluğu ilə əvəz edin. N eyni uzunluqda fərqli yolların sayı ilə əvəz edin. Əgər yalnız bir yol varsa, "are" və "routes" əvəzinə "is" və "route" sözlərini istifadə edin.
Nümunə 1