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

Санни болон Жонни нар мөнгөө цуглуулж, мөхөөлдөсний мухлагууд руу явах дуртай. 

Санни Жонни нар ижил төрлийн амттай мөхөөлдөс авахгүй байх болон бүх мөнгөндөө

тохирсон үнэ бүхий 2 мөхөөлдөс сонгон авах дүрэмтэй.

Тухайлбал

Тэдэнд m=6 доллар дундаа цуглуулсан бөгөөд мухлагууд дахь мөхөөлдөсний үнэ cost = [1, 3, 4, 5, 6]

гэсэн сонголттой байсан бол Санни Жонни хоёр 1-р болон 4-р мухлагнаас зайрмаг сонговол 1+5=6 буюу

мөнгөндөө тохирсон байдлаар нэг нэг зайрмагийг сонгож чадна.

Оролтын хэлбэр

Эхний мөрөнд мөхөөлдөсний мухлагууд руу хэдэн удаа явсныг илэрхийлэх t тоо

Дараа нь t удаагийн сонголт бүрд дараах өгөгдлүүд харгалзан өгөгдөнө.

 1. Тэдний цуглуулсан мөнгөний хэмжээ болох m тоо

 2. Тухайн үед ажиллаж байгаа мухлагуудын тоо болох n тоо

 3. Тухайн үед зарагдаж байгаа мөхөөлдөснүүдийн үнэ болох n ширхэг тоо зайгаар тусгаарлагдан өгөгдөнө.

    cost = [cost[1], cost[2], … , cost[n] ]

Хязгаарлалт:

Гаралтын хэлбэр:

Тест бүрд харгалзан сонголт хийх мухлагуудын дугаар болох хоёр тоог өсөх эрэмбээр нэг мөрөнд хэвлэнэ.

Жишээ оролт:

2

4

5

1 4 5 3 2

4

4

2 2 4 3

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

1 4

1 2 

Тайлбар:

Sunny ба Johnny мухлагууд руу явсан хоёр удаагийн явалтаар:

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх