Канад улсын иргэд хокэй үзэх үнэхээр дуртай. Тэд хокэйг шууд талбай дээр нь үзэхийн тулд улсын өнцөг булан бүрээс ирдэг. Харин тэмцээн дууссны дараа бүгд машиндаа суугаад харих хэрэгтэй ба ганц бэршээл нь маш их машин ирсэн учраас зам дээрх машины тоо хэтэрхий ихсэнэ. Нэгэн баян үйлдвэрийн эзэн хоккэйн баг худалдаж авсан ба түүндээ зориулж шинэ талбай барих болов. Таны даалгавар бол энэ баякаад тусалж хоккэйн талбай барих хамгийн тохиромжтой хотыг олно уу. Тохиромжтой гэдэг нь тэмцээн дууссны дараа зам дээр яваа машины тоог хамгийн бага байлгахаар хот юм.
Канад улс нь хоорондоо 2 чиглэлт замаар холбогдсон хотуудаас тогтоно. Аль нэг 2 хотын хооронд яг ганц замын маршруттай. Барих шинэ талбай нь энэ хотуудын аль нэг хотод баригдах ёстой. Мэдээж тэмцээн дууссны дараа тухайн хотын иргэдээс бусад нь бүгд машиндаа суугаад харьж таарна. Тухайн зам дээрх машины тоо нь тухайн замыг ашиглаж өөрийн хотдоо очиж байвал эдгээр хотуудын хоккэй-д дуртай хүмүүсийн нийлбэр байна. Таны програм талбай баригдсан хотын хамгийн их машин явах замын машины тоог хамгийн бага байлгах ёстой. Олон хариу байхыг үгүйсгэхгүй ба энэ тохиолдолд аль нэгийг гаргаж болноо. Та LocateCentre(N,P,S,D) процедурыг зохиох ба энд N нь бүх хотуудын тоог илтгэх эерэг бүхэл тоо, хотуудыг 0-ээс N-1 хүртэл дугаарлана, P нь N ширхэг тоог агуулсан массив байх ба 0<=i<=N-1 байх P[i] болгонд i-р хотын хоккэй үзэх фанатуудын тоо. Бүх хотуудад байгаа фанатуудын тоо нь хамгийн ихдээ 2 000 000 000 байх болно. S болон D нь мөн массив байх ба тус бүр N-1 элементтэй. S[i] D[i] нь энэ 2 хотын хооронд замтайг илтгэнэнэ. Таны зохиосон процедур зөвхөн талбайг барих хотын дугаарыг буцаах ёстой.
Жишээ: Доорх жишээнд эхний зурганд 0 1 2 гэсэн хотууд тус тус 10 хокэй сонирхохгчтой, 3 4 гэсэн хотууд тус бүр 20 сонирхогчтой. 2 дахь зурганд хокэйн талбайг 2 гэсэн дугаартай хотод барьвал хамгийн их машинтай зам нь 40 болохыг харуулж байна.3 дахь зурганд талбайг 3 гэсэн хотод барьвал хамгийн их машинтай зам нь 30 болохыг харуулсан байна. Эндээс 3 дугаартай хот нь 2 дугаартай хотоос илүү тохирох болохыг харуулж байна.
Эхний 25 онооны тест нь:
Хотуудыг зүүнээс баруун хүртэл шулуун шугаман байрлуулсан гэж үз. Ямар ч мөчөр байхгүй. Эндэ хамгийн ихдээ 1000 хот байна.
2 дахь 25 онооны тестүүд:
Хотууд адилхан шугаман байрлуулсан ба хамгийн ихдээ 1 000 000 хотууд байгаа гэж үд
3 дахь 25 онооны тестүүд:
Шугаман байх албагүй ба хамгийн ихдээ 1000 хот байгаа гэж үз
4 дахь 25 онооны тестүүд:
Мөн шугаман байрлах албагүй ба хамгийн ихдээ 1 000 000 хот байгаа гэж үз.
No comments:
Post a Comment