Yanacaqdoldurma məntəqələri#7551
Sizdən verilmiş şəhərlər dəstəsi üçün dairəvi tur təşkil etmək tələb olunur: müəyyən bir şəhərdən başlayaraq, hər şəhəri bir dəfə ziyarət etməli və başladığınız şəhərə geri dönməlisiniz.
Hər bir şəhərin öz nömrəsi var: 1, 2, 3 və s. Bu nömrələr şəhərlərin ziyarət edilmə sırasını göstərir, lakin başlanğıc nöqtəsi müəyyən edilməyib. Ən böyük nömrəli şəhərdən 1 nömrəli şəhərə keçməlisiniz. Məsələn, üç şəhər varsa (nömrələnmiş 1, 2, 3), səyahət üçün üç variantınız var:
1-də başlayın, 2-yə gedin, sonra 3-ə və 1-ə qayıdın.
2-də başlayın, 3-ə gedin, sonra 1-ə və 2-yə qayıdın.
3-də başlayın, 1-ə gedin, sonra 2-yə və 3-ə qayıdın.
Hər şəhərdə müəyyən miqdarda yanacaq olan yanacaqdoldurma məntəqəsi var. Bütün yanacaqdoldurma məntəqələrindəki yanacağın cəmi, bütün səyahəti həyata keçirmək üçün lazım olan yanacaq miqdarına bərabərdir. Siz yanacaq məntəqələrindən birinin yanında boş çənlə başlayırsınız. Turu tamamlayıb başlanğıc şəhərə qayıtdığınız zaman yanacağınız bitəcək.
Yanacaq bitmədən ilkin stansiyaya qayıda biləcəyiniz halda hansı şəhərin (və ya şəhərlərin) səyahətə başlama nöqtəsi ola biləcəyini müəyyən etməlisiniz. Yanacaq çəninin bütün yanacaq doldurma əməliyyatlarını yerinə yetirmək üçün kifayət qədər böyük olduğunu düşünün.
Bir neçə testdən ibarətdir. Hər test üç sətirdən ibarətdir. Birinci sətir şəhərlərin sayını ehtiva edir. İkinci sətir şəhərlərdə nömrə sırasına görə 1, 2, 3 və s. yanacaq doldurma üçün mövcud olan yanacaq miqdarını ehtiva edir. Üçüncü sətir növbəti şəhərdəki yanacaqdoldurma məntəqəsinə çatmaq üçün lazım olan yanacaq miqdarını ehtiva edir: 1 nömrəli şəhərdəki stansiyadan 2 nömrəli şəhərdəki stansiyaya, 2 nömrəli şəhərdəki stansiyadan 3 nömrəli şəhərdəki stansiyaya və s.; sonuncu rəqəm son nömrəli şəhərdən 1 nömrəli şəhərə getmək üçün lazım olan yanacaq miqdarını təyin edir. Bütün yanacaq miqdarları müsbət tam ədədlərdir və imperiya gallonlarında verilir. Yanacaq təchizatlarının cəmi 32-bit tam ədədləri keçməyəcək. Ən azı iki və ən çox 100000 şəhər mövcuddur. Sonuncu sətir sıfır ehtiva edir və işlənmir.
Hər test üçün ayrı sətirdə dairəvi turu uğurla başa çatdıra biləcək başlanğıc şəhərlərin siyahısını çıxarın. Belə şəhərlər bir neçə varsa, onları artan qaydada göstərmək lazımdır, nümunədəki formata uyğun olaraq. Macar riyaziyyatçısı L.Lovász sübut edib ki, həmişə ən azı bir başlanğıc şəhər mövcuddur.
Nümunə 1