Maze hərəkəti#4413
Rəhbəriniz sizə bir gəzinti labirinti yaratmaq tapşırığı verib və siz müxtəlif dizaynları qiymətləndirirsiniz. Hər hansı birinə qərar verməzdən əvvəl, hər bir fərqli labirintdə insanların nə qədər tez hərəkət edə biləcəyini bilmək istəyirsiniz. Axı, rəhbəriniz bu təşəbbüsdən pul qazanmaqla maraqlanır və insanlar labirintdən nə qədər tez keçə bilsələr, bir o qədər çox ödənişli müştəri qəbul edə bilərsiniz.
Labirint, nömrələnmiş otaqlar və otaqları birləşdirən keçidlər dəstidir. Labirintin yeganə girişi ən aşağı nömrəli otaqda və yeganə çıxışı isə ən yüksək nömrəli otaqdadır.
Hər bir keçidin eyni vaxtda keçə biləcək insan sayında məhdudiyyəti var. x və y nömrəli iki otaq üçün, əgər x və y birdən böyük ümumi faktora malikdirsə, onda x və y arasında keçid var. Ən böyük ümumi faktor p, x-dən y-ə keçə biləcək insan sayıdır. Eyni zamanda, p insan dəqiqədə y-dən x-ə də keçə bilər. Giriş, çıxış və otaqlar eyni vaxtda keçən hər hansı sayda insanı idarə edə bilər. İnsanlar labirintdən mümkün qədər tez keçmək istəyirlər, ona görə də otaqlarda gözləmirlər.
Budur iki nümunə girişin təsvirləri. Qutular nömrələnmiş otaqları təmsil edir və hər bir ox, onun vasitəsilə keçə biləcək insan sayını göstərən keçiddir.
Giriş, tək bir labirint təsviridir. İlk sətir, labirintdəki otaqların sayını göstərən 2 ≤ n ≤ 1000 tam ədədidir. Bu, labirint üçün otaq nömrələri olan n unikal tam ədəd ilə davam edir, hər sətirdə bir ədəd. Hər otaq nömrəsi [2, 2×10^9] aralığındadır.
Labirintə daxil ola biləcək maksimum insan sayını dəqiqədə çap edin, labirintdən çıxan insanların sürətinin labirintə daxil olan insanların sürəti ilə eyni olduğunu nəzərə alaraq. Heç bir labirint dəqiqədə 10^9 insandan çoxunu qəbul etmir.
Nümunə 1