A. XOR massiv

Xotira: 32 MB, Vaqt: 1000 ms

Sizga \(n\) ta elementdan tashkil topgan \(A\) massivi berilgan. Sizning vazifangiz massivni shunday ikkita to'plamga ajratib bo'ladimi yoki yoq tekshirishdan iborat: \(XOR(set1) = XOR(set2)\) bu yerda \(XOR(x)\) bu \(x\) to'plamdagi barcha elementalrning \(\oplus\) (bitwise xor) lariga teng.  

4
7 1 3 5

yes

3
1 2 3

yes

2
3 10

no

B. Teskari son

Xotira: 32 MB, Vaqt: 1000 ms

Barchamizga ma'lumki berilgan \(x(x>1)\) butun sonni tub sonlar ko'paytmasi ko'rinishida ifodalash mumkin. Ya'ni \(x = p_1^{q_1}*p_2^{q_2}*p_3^{q_3} *\ldots *p_n^{q_n}\) bunda \(p_i\) tub sonni anglatadi, \(q_i\) esa manfiy bolmagan butun son. Yana shunisi ma'lumki \(1\) dan katta bolgan har qanday songa teskari son \((\frac{1}{x})\) o'nli kasr korinishida bo'ladi. Sizga \(n\) ta elementdan tashkil topgan \(p\) va  \(q\) massivlari beriladi. Bunda \(p_i\) soni\(x\) sonini tub ko'paytuvchilarga ajratganda hosil bolgan tub sonlarni, \(q_i\) esa shu tub sonning darajasini anglatadi. Sizning vazigangiz ushbu massivlardan foydalanib \(x\) sonini hosil qilish va unga teskari bolgan sonni verguldan keyingi raqamlari sonini topishdan iborat.

3
5 7 13
2 1 2

inf

2
2 5
1 1

1

C. Azimjon va sonlar o`yini

Xotira: 16 MB, Vaqt: 1000 ms

Azimjon eng uchiga chiqqan hackerlardan biri. U istalgan saytni buzib kira oladi. U bugun juda zerikkani bois bir saytda o`yin o`ynamoqchi bo`ldi. U saytda Azimjon \(n\) ta odam bilan online o`yin o`ynaydi. O'yin shartlari quidagicha: o'yinda har bir odam \([1;10^{12}]\)oraliqdagi sondan birini tanlaydi. So'ng barcha odam tallagan sonlarni o'rta arifmetigi olinib 0.8 ga ko'paytiriladi. Hosil bo'lgan son kimning soniga yaqin bo'lsa o'sha odam g'olib hisoblanadi. Azimjon bu o'yinda g'olib bo'lishni istaydi. O'yin online bo'lgani sababli u saytni buzib kirib barcha raqiblari tanlagan sonlarni ko'ra oladi. Endi Azimjonga barcha tanlangan sonlar ma'lum bo'lsa u qaysi sonni tanlash orqali o'yinda g'olib bo'lishi mumkinligini aniqlang.

4
10 25 30 40

24

D. Maksimum qismsatr

Xotira: 32 MB, Vaqt: 1000 ms

Sizga lotin alifbosining kichik harflaridan tashkil topgan \(S\) satri berilgan. \(S\) satrining qismsatri deb \(S[i : j]\) \((1 \leq i \leq  j \leq |s|)\) ga aytiladi. Bilamizki lotin alifbosi \(26\) ta harfdan tashkil topgan va biz ularni \(1\) dan \(26\) gacha raqamlab olamiz \((a = 1, b = 2, \dots z = 26)\). Sizning vazifangiz shundan qismsatrni topishki, undagi har bir belgi bu qismsatrda faqat bir marotaba kelgan bolsin va ularning summasi iloji boricha maksimum bo'lsin. 

abcabcbb

abc

E. Konfetlar

Xotira: 32 MB, Vaqt: 1000 ms

Azimjon konfetlarni juda yaxshi ko'radi. Bu safar u Robolandiya konfetlaridan yeb ko'rishga qaror qildi. U shu mamlakatga kelib qarasaki, konfetlar o'zining mamlakatidagidan ko'ra ancha shirinroq ekan. Endi u iloji boricha ko'proq sondagi konfetlarni o'zining mamlakatiga olib ketmoqchi bo'ldi va Roboshop do'koniga tashrif buyurdi. Bu do'konda jami \(N\) xil turdagi konfetlar bo'lib, har bir turdagi konfetlar yo'lakdagi rastalarda bir qatorda joylashtirilgan. Ammo, bu dokonni o'ziga yarasha qonunlari bor: hech qaysi yonma-yon turgan ikki hil turdagi rastadan konfet sotib olish mumkin emas va qaysidur turdagi konfetni olmoqchi bo'lsa, bu turda mavjud barcha konfetlarni sotib olishi shart! \(i-\)rastada  \(a[i]\) ta quti mavjud va har bir quti ichida \(b[i]\) ta konfet bor(bunda barcha \(a[i]\) ta qutidagi konfetlarni olishi kerak). Bu rastadagi barcha konfetlarni olish uchun \(c[i]\) so'm pul to'lash lozim.  Azimjon dokonga kirishidan oldin qarasa unda \(B\) so'm pul bor ekan. Endi u uyiga necha dona konfet olib keta olishini aniqlamoqchi. Siz unga yordam bering.

5 10
3 2 5 10 7
1 2 3 1 4
2 1 4 2 3

46

F. Pul daraxti

Xotira: 32 MB, Vaqt: 1000 ms

Azimjon kunlardan bir kuni g'alati bir orolga tushib qoldi. Bu oroldagi \(K\) ta daraxt mavjud. Bu daraxtning o'ziga hos hususiyati daraxt aylana shaklida bo'lib, uning har bir tugunida pullar o'sar edi. Ammo, hamma yerda bo'lgani kabi bu yerni ham o'zining aholisi va qiroli bor edi. Shuning uchun Azimjon shunchaki hamma pullarni terib olib keta olmas edi. Yaxshiyamki qirol sahiy va uning mehmonlarga nisbatan hurmati baland ekan. U Azimjonga istalgan faqat bitta daraxtni tanlashni va u ustida bitta o'yin o'ynashni taklif qildi, o'yin qoidalari quyidagicha: dastlab Azimjon o'zi uchun istalgan bir tugunni tanlaydi va undagi pulni oladi. So'ng, qirol ham o'zi uchun bir tugunni tanlab undagi pulni o'z haznasiga qoshib qo'yadi. Ikkala holatda ham tugundagi pullar qiymati \(0\) ga teng bo'lib qoladi. Keyingi har bir qadamda, azimjon oldin pul olgan tugunlar bilan bog'langan biror qiymati \(0\) ga teng bo'lmagan tugunni tanlaydi va undagi pulni oladi. Qirol ham har bir qadamda ilgari pul olgan tugunlar bilan bog'langan istalgan qiymati \(0\) ga teng bo'lmagan tugunni tanlab undagi pulni o'ziga oladi(Ikkala o'yinchi ham navbati kelganda yurish qila olmasa shunchaki navbatini o'tkizib yuboraveradi). Azimjon boshqa pul ololmay qolgan payt o'yinni yakunlaydi. Qirolning xazinasida pul ko'p bo'lgani sababli unga u qancha pul yig'ishi muhim emas, u faqat Azimjon olishi mumkin bo'lgan pulni minimallashtirishni hohlaydi. Albatta Azimjon esa bu daraxtni tanlaganda boshqa daraxtni tanlagandagidan ko'ra ko'proq pul yutishni hohlaydi.  Ikkala o'yinchi ham optimal o'ynasa Azimjon olishi mumkin bo'lgan maksimum pul miqdorini toping.   

3 
4
5 7 3 9
3
20 52 7
6
5 1 7 9 3 10

59