Go Go Gorelians#6057
Gorelyanlar kosmosda səyahət etmək üçün warp bağlantılarından istifadə edirlər. Warp bağlantısından keçid ani baş verir, lakin təhlükəsizlik səbəbindən bir şəxs yalnız hər 10 saatda bir dəfə warp edə bilər. Həmçinin, warp bağlantısı yaratmağın dəyəri bağlantı nöqtələri arasındakı xətti məsafə ilə birbaşa artır.
Gorelyanlar, məlum kainatda dominant qüvvə olaraq, tez-tez darıxırlar, buna görə də yeni kosmos bölgələrini aşağıdakı şəkildə fəth edirlər.
İlkin işğal qüvvəsi uyğun bir planet tapır və onu fəth edir, bu bölgədəki bütün Gorelyan məsələlərini idarə edəcək Regional Gorelyan Qalaktik Hökumətini, bundan sonra RGGG adlandırılacaq, qurur.
Növbəti planet fəth edildikdə, yeni planet ilə RGGG planet arasında tək bir warp bağlantısı qurulur. Bu şəkildə warp bağlantıları ilə birləşdirilən planetlər Regional Gorelyan Planet Şəbəkəsinin, yəni RGPN-in bir hissəsi sayılır.
Əlavə planetlər fəth edildikcə, hər yeni planet RGPN-də artıq olan ən yaxın planetə tək bir warp bağlantısı ilə birləşdirilir, beləliklə yeni planetləri şəbəkəyə birləşdirmə xərcləri minimuma endirilir. İki və ya daha çox planet yeni planetdən eyni məsafədədirsə, yeni planet onlardan hansının əvvəl fəth edildiyinə birləşdirilir.
Lakin bu bir problem yaradır. Planetlər daha çox təsadüfi şəkildə fəth edildiyi üçün bir müddət sonra RGGG ehtimal ki, ideal bir yerdə olmayacaq. RGGG ilə məsləhətləşməyə ehtiyacı olan bəzi Gorelyanlar yalnız bir və ya iki warp etməli ola bilər, lakin digərləri onlarla warp tələb edə bilər - warplar arasında 10 saat gözləmə müddətini nəzərə alanda çox əlverişsizdir.
Beləliklə, hər Gorelyan ilində RGGG RGPN-i təhlil edir və özünü optimal bir yerə köçürür. Optimal yer, RGPN-dəki hər hansı bir planetdən RGGG-ə çatmaq üçün tələb olunan maksimum warp sayını minimuma endirən bir planet olaraq təyin edilir. Məlum olur ki, həmişə dəqiq bir və ya iki belə planet var. İki olduqda, onlar həmişə bir warp bağlantısı ilə birbaşa bitişikdirlər və RGGG özünü bu iki planet arasında bərabər şəkildə bölür.
Sizin işiniz RGGG üçün optimal planetləri tapacaq bir proqram yazmaqdır. Bu problemin məqsədləri üçün, Gorelyanlar tərəfindən fəth edilən kosmos bölgəsi (0, 0, 0) ilə (1000, 1000, 1000) arasında dəyişən bir kub olaraq təyin edilir.
Giriş, Gorelyanların bir kosmos bölgəsini fəth etdiyi ssenarilər dəstindən ibarətdir. Hər ssenari müstəqildir. Ssenarinin ilk sətri, Gorelyanlar tərəfindən fəth edilən planetlərin ümumi sayını göstərən bir N tam ədədidir. Girişin növbəti N sətri, fəth edildikləri sırayla, RGPN-ə əlavə ediləcək fəth edilmiş planetlərin ID və koordinatlarını ID X Y Z formatında göstərir. ID 1 ilə 1000 arasında bir tam ədəddir. X, Y və Z 0 ilə 1000 arasında tam ədədlərdir. Rəqəmlər arasında tək boşluq var. N = 0 dəyəri girişin sonunu göstərir.
Hər giriş ssenarisi üçün, RGGG-nin köçməli olduğu optimal planetin və ya planetlərin ID-lərini çıxarın. Tək bir planet üçün sadəcə planet ID-ni çıxarın. İki planet üçün, planet ID-lərini, kiçik ID birinci olmaqla, tək bir boşluq ilə ayıraraq çıxarın.
Nümunə 1