Masala #0504

Xotira 128 MB Vaqt 1500 ms Qiyinchiligi 40 %
14

  

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.


Kiruvchi ma'lumotlar:

Kirish faylida bitta butun son \(3 ≤ n ≤ 1000\) kiritiladi. Keyingi qatorda \(n\) ta butun son, qiymati 1000 dan oshmaydi


Chiquvchi ma'lumotlar:

Chiqish faylida Shoxjaxon va Lazizning yig’gan ballaridagi orasidagi minimal farqni chop eting.


Misollar
# input.txt output.txt
1
5
1 2 10 5 3
7
Izoh:

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

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin