Masala #0504
Koptokchalar o’yini
Shoxjaxon va Laziz karantinda zerikib qolmaslik uchun navbatma-navbat o'yin o'ynab turishadi. Bir kuni ular antiqa o‘yin o‘ylab topishdi. O‘yin sharti quyidagicha: Bir qatorda joylashgan \(n\) ta koptokchalar bor. Har bir koptokcha o’z raqamiga ega va bir qatorda joylashtirilgan. Har bir o'yinchi o'z navbatida chap tarafda joylashgan koptokchani yoki o'ngda joylashgan koptokchani qatordan olib tashlashlari va qatordagi qolgan koptokchalarning qiymatlari yig'indisiga teng ball olishlari mumkin. Olib tashlash uchun toshlar qolmaganda, yuqori ball to'plagan g'olib hisoblanadi. Birinchi bo'lib o’yinni Shoxjaxon boshlaydi. Laziz har doim bu o'yinda yutqazishini aniqladi, shuning uchun u hisobdagi farqni minimallashtirishga qaror qildi. Shoxjaxonning maqsadi esa hisobdagi farqni maksimal darajada oshirish. Agar ikkalasi ham optimal darajada oʻynasa, Shoxjaxon va Lazizning yig’gan ballaridagi orasidagi farqni topib berishga yordamlashing.
Kirish faylida bitta butun son \(3 ≤ n ≤ 1000\) kiritiladi. Keyingi qatorda \(n\) ta butun son, qiymati 1000 dan oshmaydi
Chiqish faylida Shoxjaxon va Lazizning yig’gan ballaridagi orasidagi minimal farqni chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 1 2 10 5 3 |
7 |
1-testga izoh: \([ 1, 2, 10, 5, 3]\) kiritiladi.
Shoxjaxon 1 ni olib tashlaydi va ularning yig’gan ballari 2+10+5+3=20 ball. Shoxjaxon=20, Laziz=0. \([2,10,5,3]\)
Laziz 2 ni olib tashlaydi va ularni yig’gan ballari 10+5+3=18 ball. Shoxjaxon=20, Laziz=18. \([10,5,3]\)
Shoxjaxon 3 ni olib tashlaydi va ularning yig’gan balllari 10+5=15 ball. Shoxjaxon=35, Laziz=18. \([10,5]\)
Laziz 5 ni olib tashlaydi va ularni yig’gan ballari 10 ball. Shoxjaxon=35, Laziz=28. \([]\)
Ularning ballari orasidagi farqi esa 35 – 28 = 7 ball
Telegram kanalimizga obuna bo'ling