A. Juft yig'indi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Dasturchi Kamronni menimcha barcha CP o'quvchilari tanisa kerak-aa! Kamron oldinlari chiterlikni eng yaxshi yo'l deb bilgan, hozirda ham unday insonlar yo'q deya olmaymiz. Shunday ekan, Kamron o'z bilimiga ishonib masalalar ishlashni boshladi, ammo u masala topishda qiynalmoqda. Mr Ustoz unga quyidagi masalani berdi:

Sizga \(n\) massiv berilgan. Nechta juft indeks \((i, j)\) \((i < j)\) bor — \(a[i] + a[j]\) juft son bo'ladigan?

Bu masalani dasturchi Kamron tezda ishladi, qani sizning ham mahoratingizni sinab ko'ramiz..

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\), \((1 ≤ n ≤ 2·10^5)\).

Ikkinchi qatorda \(n\) ta butun son \(a[i] (|a[i]| ≤ 10^9)\).

Chiquvchi ma'lumotlar:

Masalada so'ralgan javobni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 2 3 4 5	4

B. Oyna va almashtirish

Xotira: 256 MB, Vaqt: 1000 ms

Masala

\(0\) va \(1\) dan iborat satr \(s\) berilgan va butun \(k\). Siz \(s\) dagi istalgan \(k\) ta \(0\) ni \(1\) ga aylantirishingiz mumkin. Olingan satrda ketma-ket \(1\) lar eng uzun maksimal uzunligi nechi bo‘lishi mumkin?

Kiruvchi ma'lumotlar:

\(s\) — uzunligi \(n\), \((1 ≤ n ≤ 2·10^5)\)

Keyingi qatorda \(k\), \((0 ≤ k ≤ n)\).

Chiquvchi ma'lumotlar:

Maksimal ketma-ket \(1\) larning uzunligi

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	0010011 2	5

C. Guruhni tanla

Xotira: 256 MB, Vaqt: 1000 ms

Masala

\(n\) butun sonlar berilgan. Siz \(k\) ta elementni tanlab birinchi guruhga, qolganlarini ikkinchi guruhga qo‘yasiz. Maqsad — \(|sum(guruh1) - sum(guruh2)|\) ni maksimal qilish. Maksimal qiymatni aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda, \(n,k\) \((1 ≤ k ≤ n ≤ 2·10^5)\).

Keyingi qatorda \(n\) ta butun son \(a[i]\), \((|a[i]| ≤ 10^9)\).

Chiquvchi ma'lumotlar:

Masalada so'ralgan javobni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 2 1 2 3 4 5	9

D. Maksimal eng kichik

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Yuk tashuvchi kompaniyada ketma-ket joylashgan \(n\) ta yuk qutisi bor. Har bir qutining og‘irligi maʼlum.

Kompaniya bu qutilarni ketma-ket \(m\) ta mashinaga joylashtirmoqchi. Har bir mashina kamida bitta qutini olishi shart va qutilar tartibini o‘zgartirish mumkin emas.

Kompaniya uchun eng og‘ir yuk ortilgan mashina muammo tug‘diradi. Shuning uchun ular sizdan quyidagini aniqlashni so‘rashdi:

Qutilarni eng optimal tarzda taqsimlaganda, eng og‘ir mashinadagi yuk og‘irligini minimal qilish mumkin bo‘lgan qiymat nechchi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n, m\), \((1 ≤ m ≤ n ≤ 2·10^5)\).

Keyingi qatorda, qutilar og'irliklari, \(n\) ta butun son \(a[i]\), \((1 ≤ a[i] ≤ 10^9)\)

Chiquvchi ma'lumotlar:

Minimal mumkin bo‘lgan maksimal yuk og‘irligi

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 7 2 5 10 8	14

E. Mustaqil to‘plam

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Qadimiy bog‘da \(n\) ta haykal joylashgan bo‘lib, ular yo‘laklar orqali daraxtsimon shaklda ulangan. Har bir haykalning estetik qiymati mavjud (musbat yoki manfiy bo‘lishi mumkin).

Bog‘bon bir nechta haykallarni tanlab, ko‘rgazma tashkil qilmoqchi. Biroq, xavfsizlik sababli yonma-yon joylashgan haykallarni birga tanlash mumkin emas.

Bog‘bon sizdan yordam so‘raydi:

Qaysi haykallarni tanlash kerakki, ularning umumiy estetik qiymati maksimal bo‘lsin?

Kiruvchi ma'lumotlar:

Birinchi qatorda, \(n\), \((1 ≤ n ≤ 2·10^5)\).

Keyingi qatorda \(n\) butun \(w[i]\), \((|w[i]| ≤ 10^9)\).

Keyingi qatorda \(n-1\) ta yo'lak: \(u,v\)

Chiquvchi ma'lumotlar:

Maksimal umumiy qiymat

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 -2 3 4 -1 1 2 1 3 3 4 3 5	7

F. Minimal subset

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Kriptografiya bilan shug‘ullanuvchi olimda \(n\) ta maxfiy kalit mavjud. Har bir kalit butun son bilan ifodalangan.

Olim tajribalar davomida turli qiymatlar ustida XOR amali bajaradi. Har bir tajribada u quyidagi savolga duch keladi:

Mavjud kalitlardan ayrimlarini tanlab, ularning XOR natijasini aniq \(x\) ga teng qilish uchun eng kam nechta kalit tanlash kerak?

Agar bunday tanlash imkonsiz bo‘lsa, olim natijani \(-1\) deb belgilaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n, q\).

Ikkinchi qatorda \(n\) ta \(a[i]\).

Keyingi \(q\) qatorda har qatorda bitta \(x\).

Chiquvchi ma'lumotlar:

Har bir so‘rov uchun javob

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 1 2 3 4 0 1 7	0 1 -1