АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Хакерланд бол зам дагуу байшингууд нь цувран байршдаг нэг хэмжээст хот юм.

Хотын захирагч уг хотын байшингийн дээврүүд дээр радио дамжуулагчуудаа суурилуулахыг хүсч байна.

Дамжуулагч бүр тогтсон зайд мэдээ дамжуулах ба аль ч байшин дээр дамжуулагчийг суурилуулж болно.

Хакерланд хотын газрын зураг ба дамжуулалт шаардлагатай мужууд өгөгдсөн бол байшин бүр дор хаяж нэг

дамжуулагчийн дохионы дор байхаар хамгийн цөөн дамжуулагчийн тоог тодорхойлно уу.

Дамжуулагч бүр оршин буй байшингийн дээр суурилуулсан байх ёстой.

Жишээлбэл

 Байшингууд x = [1, 2, 3, 5, 9] байршил дээр байрладаг гэвэл k=1.3 зайд дамжуулах хүчин чадалтай антеныг

2, 5, 9 байшингуудад байрлуулахад хотыг нийтэд нь бүрхэнэ.

Бүрхэх мужууд [1, 2, 3], [5], [9] хэлбэртэй байна.

Функцийн тодорхойлолт

hackerlandRadioTransmitters нэртэй функцийг доорх код бичих талбарт гүйцээн бичнэ үү.

Энэ функц хамгийн цөөн дамжуулагчийн тоог илэрхийлэх ганц утгыг буцаах ёстой.

hackerlandRadioTransmitters функц дараах хоёр аргументтай:

x: байшингуудын байршлыг илэрхийлэх бүхэл тоон массив

k: дамжуулагчийн хүчин чадлыг илэрхийлэх бүхэл тоон утга

Оролт

Эхний мөрд байшингийн тоо n  болон дамжуулагч бүрийн хүчин чадлыг илэрхийлэх k бүхэл тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Хоёрдугаар мөрд n ширхэг байшингуудын байршлыг илэрхийлэх x[i] тоонууд зайгаар тусгаарлагдан өгөгдөнө. 

Зааглалт

Дэд бодлого

1 <= n <= 1000 үед ихдээ онооны 50%.

Гаралт

Хотын байшингуудыг бүрхэж чадах хамгийн цөөн дамжуулагчийн тоо болох нэг бүхэл тоо байна.

Жишээ

Оролт 1

 5 1

1 2 3 4 5

Гаралт 1

2

Тайлбар 1

Хакерланд хотын байшингуудыг дамжуулагч бүрхсэн байдал.

2 болон 4 дүгээр байшин дээр дамжуулагчийг байрлуулахад нийт 2 дамжуулагч хангалттай.

Оролт 2

 8 2

7 2 4 6 5 9 12 11

Гаралт 2

3

Тайлбар 2

Хакерланд хотын байшингуудыг дамжуулагч бүрхсэн байдал.

4, 9 болон 12 дугаар байшин дээр дамжуулагчийг байрлуулахад нийт 3 дамжуулагч хангалттай.

Орчуулсан : Р.Мижиддорж МУБИС, доктор