Hobson qatarları

G-n Hobson at tövlə idarəçiliyindən ayrıldı və daha müasir bir nəqliyyat növü olan qatarlar sahəsinə sərmayə qoydu. O, $n$ stansiyadan ibarət bir dəmir yolu şəbəkəsi qurdu. Lakin o, sərnişinləri çox seçim yükündən azad etmək istəyirdi: hər stansiyadan sərnişin yalnız bir başqa stansiyaya qatarla gedə bilər. Belə bir səyahət mərhələ adlanır. Qeyd edək ki, bu, bir tərəfli səyahətdir və geri qayıtmaq imkanı olmaya bilər.

Hobson həmçinin sərnişinlərə bir səyahətdə $k$ mərhələ keçməyə imkan verən yalnız bir bilet variantı təklif edir. Hər stansiyanın çıxışında avtomatlaşdırılmış bilet oxuyucu (yalnız bir dənə, sərnişinlərin hansını istifadə edəcəyinə qərar verməməsi üçün) yerləşdirilib. Avtomat, başlanğıc stansiyadan son stansiyaya qədər olan məsafənin $k$ mərhələdən çox olmadığını yoxlayır.

Hər bilet oxuyucu icazə verilən başlanğıc stansiyaların siyahısı ilə proqramlaşdırılmalıdır. Lakin bu siyahı üçün nə qədər çox yaddaş tələb olunarsa, maşın bir o qədər bahalı olacaq. Hobsona kömək edin, hər bir stansiya $A$ üçün müştərinin $A$-ya $k$ mərhələdən çox olmamaqla çata biləcəyi stansiyaların sayını (o cümlədən $A$) müəyyən edin.

Şəkil H.1: Nümunə 1 üçün illüstrasiya. Hər bir dairə stansiyanı təmsil edir. Dairələrin xaricindəki rəqəmlər k = 2 olduqda bilet oxuyucularına yüklənmiş stansiyaların nömrələridir.