A. Komiljon va shokolad

Xotira: 32 MB, Vaqt: 1000 ms

Komiljon bugun xolasinikiga bormoqchi. Komiljonni xolasining uyida shirin taomlar va xolasidan tashqari jiyanlari bo‘lmish Asror, Abror va Ahror kutishmoqda. Komiljon jiyanlarini juda yaxshi ko‘radi, shuning uchun ularga o‘zining shokoladlarini olib bormoqchi. 

Unda hozir $N$ dona shokolad bor. Ammo u xolasinikiga borganda hamma jiyanlarini birdek xursand qilish uchun ularga bir xil sondagi shokoladlar berishi shart. U uyidan ko‘pi bilan nechta shokoladni o‘zi bilan olib ketsinki, jiyanlariga shokoladlarni tarqatib bo‘lgach, uning o‘zida ortiqcha shokolad qolmasin?

8

6

B. Komiljon va uning do'stlari

Xotira: 32 MB, Vaqt: 1000 ms

Komiljon va uning do‘stlari dekart koordinatalar sistemasida yashashadi. Afsuski, Komiljonning uyi ba’zi sabalarga ko‘ra buzilmoqda. Shuning uchun ham Komiljon yangi uy xarid qilmaguncha bir do‘stining uyida yashab turmoqchi. Komiljon o‘z buyumlarini do‘stining uyiga ko‘chirishi uchun Manhattan masofasini bosib o‘tishi lozim. Ya’ni agar Komiljonning uyi $(a, b)$ koordinatada, do'stining uyi $(c, d)$ koordinatada bo'lsa, Komiljon $|a-c|+|b-d|$ masofani bosib o'tishi kerak. 

Sizga xaritadagi barcha uylarning koordinatalari beriladi, bunda $i$-uy $(X_i, Y_i)$ koordinatalarda joylashgandir. Ammo siz na Komiljonning va na uning do‘sting uyi bilasiz. Sizning vazifangiz Komiljon va uning do‘stining uylari joylashgan barcha holatlardan Komiljon eng kam harakat qiladigan va eng ko‘p harakat qiladigan masofalarni topishdir. E’tibor bering, Komiljon va uning do‘sti har xil raqamli uylarda yashashadi, ammo ularning koordinatalari ustma-ust tushib qolishi mumkin.

4
2 3
0 0
4 5
1 1

2 9

C. Banknotalar

Xotira: 256 MB, Vaqt: 1000 ms

Robolandiya Markaziy bankida $N$ta banknota qolgan, va ularning qiymati $A_1, A_2, ..., A_N$ robodollarga teng. Robolandiya banknotalarining bir ajoyib xususiyati bor: ixtiyoriy $A_i$ va $A_j$ banknotalar uchun $(1 \le i, j \le N)$ ulardan biri boshqasiga qoldiqsiz bo‘linadi.

Bankning $Q$ta potensial mijozi bor va har bir mijoz ma’lum bir miqdorda pul qarzga olmoqchi. Agar mijoz bankdan $X_i$ robodollar qarz olmoqchi bo‘lsa, bank bu pullarni qaytimsiz bera oladigan bo‘lsa, buning uchun eng minimal nechta banknotalar ishlatish mumkin? Sizning vazifangiz shu savolga javob berish. Agar qaytimsiz qarz berishning iloji bo‘lmasa $-1$ deb chiqaring. 

E’tibor bering, sizning dasturingiz mijozlarga pullarni bermaydi, ya’ni so‘rovlar bir biriga ta’sir etmaydi.

3
2 1 8
5
3 1 5 11 12

2 1 -1 3 -1

4
1 1 1 100
4
4 3 101 104

-1 3 2 -1

D. Shifuning topshirig'i

Xotira: 256 MB, Vaqt: 2000 ms

Kung-fu Panda ustoz Shifuning topshirig‘iga binoan, uzunligi $N$ga teng ketma-ketlik yasadi. Ammo ustoz Shifu bu ketma-ketlik Nefrit saroyi qoidalariga zidligini aytib, unga $M$ta cheklov qo‘ydi: har bir $X_i, Y_i$ indekslar uchun, ushbu indeksdagi elementlar farqi 1ga teng bo'lishi kerak. 
Boshqa so‘zlar bilan aytganda $|A_{X_i} - A_{Y_i}| = 1$ shart bajarilishi lozim.

Endi Kung-fu Panda ketma-ketlik boshidan yasamoqchi. Siz unga yordam bering va ustoz Shifuning cheklovlariga mos keluvchi istalgan massivni topib bering. Agar bunday ketma-ketlikni topishning iloji yo‘q bo'lsa, $-1$ chiqaring

6 4
3 5
1 2
4 2
4 6

2 1 5 2 6 3

3 1
2 2

-1

E. Asilbek va g'aroyib oraliqlar

Xotira: 256 MB, Vaqt: 2000 ms

Asilbekda uzunligi $N$ga teng $A$ massiv hamda $T$ soni bor. Asilbek barcha $1 \le l \le r \le N$ bo‘lgan oraliqlar ichidan $F(l, r) \le T$ bo‘lgan oraliqlar sonini topmoqchi. Siz unga yordam bering.

$F(l, r)$ quyidagicha hisoblanadi:
- $B_1=A_l; B_2=A_{l+1}; ...; B_{r-l+1}=A_r$ massiv bo'lsin
- Bitta amalda $B$ning ixtiyoriy elementini 1ga oshirish, yoki 1ga kamaytirish mumkin.
- $B$ massiv barcha elementlarini teng qilish uchun kerak bo'ladigan minimal amallar soni $F(l, r)$ ga teng bo'ladi.

Masalan, $A=[4,2,8,5]$. Bunda $F(1, 2)=2$; $F(3,3)=0$ hamda $F(1, 4) = 7$.

4 3
4 2 8 5

6

4 0
1 1 1 1

10