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

Толгойлогчийн bot нь хуучин DOS дээр суурилсан тоглоом тоглож байв. Энд нэг эгнээнд байрлах өөр өөр өндөр бүхий байшингууд байна. 

Bot нь 0 өндөртэй 0 дүгээр байшингаас эхлэнэ. Тоглоом эхлэх үед bot -н байж болох хамгийн бага энергийн түвшинг тодорхойл. 

Энд байшингаас байшинруу дамжих үед bot -н энерги нь 0 – с доош орохгүй байх ёстой.

Өндрийн нэгж нь энергийн нэгжтэй шууд хамааралтай байна. Bot -н энергийн түвшин нь дараах байдлаар тооцоологдоно.

• Хэрэв bot -н botEnergy нь байшингийн өндрөөс бага байвал

newEnergy = botEnergy – (өндөр  - botEnergy)

• Эхэрв bot -н botEnergy нь байшингийн өндрөөс их байвал

newEnergy = botEnergy + (botEnergy - өндөр)

Жишээлбэл h = [2, 3, 4, 3, 2] гэсэн өндөртэй байшингууд өгөгдсөн гэж үзэе. Хэрэв bot -н эхлэх үеийн энерги botEnergy = 4 байвал дараах үр дүнд хүрнэ.

Энэ нь bot -г даалгавараа дуусгахад хангалттай энерги байна гэхдээ эхлэх min энерги биш юм. Энэ тохиолдолд эхлэх min botEnergy = 3 байна.

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

chiefHopper функцыг гүйцээ. Уг функц нь эхлэх min botEnergy -н утыг буцаах ёстой.

chiefHopper -н параметерүүд:

arr: байшингуудын өндрийг илэрхийлэх integer утгаас бүрдсэн хүснэгт

Оролтын формат

Эхний мөрөнд байшингуудын тоог илтгэх integer n байрлана.

Дараагийн мөрөнд зайгаар тусгаарлагдсан n ширхэг integer  тоо байна. h[1] . . h[n] тус бүр байшингийн өндрийг илэрхийлнэ.

Хязгаарлалт

1 <= n <= 10⁵

1 <= h[i] <= 10⁵ , i ϵ [1, n]

Гаралтын формат

Тоглоомыг дуусгахад хангалттай байх min энергийн хэмжээг илэрхийлсэн integer тоо.

Жишээ Оролт 0

5

3 4 3 2 4

Жишээ Гаралт 0

4

Тайлбар 0

Хэрэв 4-с эхэлбэл эхний алхамын дараа энерги нь 5, 2 дахь алхамын дараа 6, 3 дахь алхамын дараа 9, 4 дэх алхамын дараа 16, сүүлчийн алхамын дараа 28 болно.

Хэрэв 3-с эхэлбэл bot нь тоглоомыг дуусгаж чадахгүйд хүрнэ.

Жишээ Оролт 1

 3

4 4 4

Жишээ Гаралт 1

4

Тайлбар  1

Хэрэв bot -н энерги нь 4 байвал алхам бүрт (4 – 4 = 0)  өөрчлөгдсөнөөр 4 хэвээрээ байна.

Жишээ оролт 2

3

1 6 4

Жишээ гаралт 2

3

Тайлбар 2

botEnergy өндөр  delta

3 1 +2

5 6 -1

4 4  0

4

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

Орчуулсан : Б.Баясгалантөгөлдөр АНУ