A. O’chirish

Xotira: 16 MB, Vaqt: 1000 ms

Sizga \(N\) ta har xil natural sonlardan tashkil topgan \(A\) to’plam berilgan. Siz to’plamda yagona son qolgunga qadar quyidagi amallardan birini qilishingiz kerak:

• To’plamdan \(\text{birlarSoni}(Ai⊕Aj)=1\) shartni qanoatlantiradigan ikkita sonni tanlab ulardan ixtiyoriy birini(yoki \(Ai\), yoki \(A_j\)) ni to’plamdan o’chirishingiz mumkin. Buning uchun \(E_1\) energiya sarflaysiz.
• To’plamdan \(\text{birlarSoni}(Ai⊕Aj)>1\) shartni qanoatlantiradigan ikkita sonni tanlab ulardan ixtiyoriy birini(yoki \(A_i\), yoki \(A_j\)) ni to’plamdan o’chirishingiz mumkin. Buning uchun \(E_2\) energiya sarflaysiz.

Bu yerda \(⊕\) bitwise XOR amali, \(\text{birlarSoni}(X)\) esa \(X\) sonining ikkilik sanoq tizimida yozilishidagi birlar sonini qaytaradi.

Siz to’plamda yagona son qolgunga qadar bu amallarni bajarish uchun eng kamida qancha energiya sarflanishini aniqlang

1
4
50 100
1 2 3 4

200

B. Tub ko'paytuvchilar tarkibi

Xotira: 16 MB, Vaqt: 1000 ms

Sizga \(N = P_1^{A_1} * P_2^{A_2} * \dots * P_x^{A_x}\)  soni berilgan. Bu yerda \(P\) tub sonlardan tashkil topgan massiv (hech bir elementi takrorlanmaydi), \(A\) natural sonlardan tashkil topgan massiv. Sizning vazifangiz tub ko’paytuvchilari tarkibiga \(N\) sonining tub ko’paytuvchilari tarkibidagi barcha tub sonlar qatnashgan hamda \(N\) sonining bo’luvchisi bo’la oladigan natural sonlar yig’indisini chop eting.

1
3
2 3 5
2 1 1

90

C. CTRL+P

Xotira: 16 MB, Vaqt: 1000 ms

Agar siz kompyuter sohasida bilimga ega bo’lsangiz demak siz printer degan qurilmani ham juda yaxshi bilasiz. Sizga ma’lumki biror bir hujjatni printerdan chop etish uchun shunchaki chop etish tugmasini bosish kifoya. Ba’zi hollarda printerdan hujjatning qaysidir sahifalarinigina chiqarish ham mumkin, buning uchun siz chop etish jarayonida aynan qaysi sahifalarni chop etish kerakligini aytib o’tishingiz kerak. Misol uchun siz hujjatning beshinchi, o’ninchi, va o’n to’qqizinchi sahifalarini chop etmoqchi bo’lsangiz chop etish jarayonida hujjatning sahifalar raqamlarini vergul bilan ajratgan holda kiritishingiz kerak, ya’ni 5,10,19. Bundan tashqari chop etish jarayonida hujjatning qaysidir oralig’idagi barcha sahifalarni ham chop etish mumkin, buning uchun ‘-‘ (chiziqcha) qo’yib, chiziqchaning chap tomoniga qaysi sahifadan boshlab (Agar qo’yilmasa avtomatik tarzda hujjat boshidan deb hisoblaydi), chiziqchaning o’ng tomoniga qaysi sahifagacha ekanligi(agar qo’yilmasa hujjat oxirigacha ekanligini bildiradi) yoziladi. Misol uchun sizga 25-sahifadan 35-sahifagacha barcha sahifalarni chop etmoqchi bo’lsangiz 25-35 deb yozish yetarli hisoblanadi.

Siz hozirgi vaqtda algoritm va dasturlash musobaqalariga tayyorgarlik ko’ryapsiz, shu sababli sizga 2624 varoqli http://e-maxx.ru/bookz/files/tucker.pdf kitobning ba’zi sahifalari kerak bo’lib qoldi. Siz kitobni printerdan chop etmoqchi bo’ldingiz hamda sahifalarni tanlash qismiga S satrni yozdingiz.

Yozilgan S satr bo’yicha sahifalarni chop etish uchun printerga nechta oq list qo’yilishi kerakligini aniqlang.

1-3,5,7,10-13

9

D. Davlat shifri

Xotira: 16 MB, Vaqt: 1000 ms

Sizga biror bir davlatning alpha-2 shifri berilgan. Siz aynan shu davlatning alpha-3 shifrini chop eting. Davlatlarning alpha-2 va alpha-3 shifrlarini https://www.iban.com/country-codes sahifadan bilib olishingiz mumkin!

3
UZ
SO
VN

UZB
SOM
VNM

E. Prefiks funksiya

Xotira: 16 MB, Vaqt: 2500 ms

Dasturlash musobaqasi bilan shug’ullanib yurgan barchaga Prefiks funksiya nima ekanligi ma’lum bo’lsa kerak. Agar bilmasangiz Prefiks funksiya haqida https://e-maxx.ru/algo/prefix_function havoladan o’rganib olishingiz mumkin.

Keling endi asosiy masalaga o’tamiz!

\(S\) to’plam \(m\) ta harfli alifbodan tuzilgan uzunligi \(n\) ga teng bo’lgan barcha satrlar to’plami.

\(F(s)\) funksiyasi \(\text{prefix\_function}(s)\) dan olingan to’plamning eng katta qiymati bo’lsin.

Sizning vazifangiz \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni hisoblashdan iborat.

3 2 1000

8

F. Tartib

Xotira: 16 MB, Vaqt: 1000 ms

Sizga \(A, B, C\) sonlari aralash tartibda berilgan. Sonlar aralash tartibda berilgani bilan sizga ma’lumkin \(A < B < C\) shart o’rinli. Shu uchchala sonni ko’rsatilgan tartibda chop eting:

1 5 3
ABC

1 3 5

G. O’nuchboy

Xotira: 16 MB, Vaqt: 1000 ms

Tadqiqotchilarning hisob-kitoblariga ko’ra AQSH aholisining 10 foizi 13 sonidan qo’rqishadi, va har yilning 13-jumasini paraskevidekatriaphobia deb nomlashadi. Bu kun ular uchun 13 sonidanda qo’rqinchliroq hisoblanadi.

O’zimizning O’nuchboy ismli yigit yaqinda GreenCard da qatnashib Amerikaga yo’llanmani qo’lga kiritgan edi va u hozir Amerikada. O’nuchboy ismining ma’nosi sababli haligacha ish topolmayapti, chunki u hozirda ish izlab borgan joylarining barchasi ismining ma’nosini aytganidan so’ng ishga qabul qilmasliklarini aytishyabdi.

O’nuchboy ma’lumotlar bazasi bilan ishlaydigan firmalardan biriga ish izlab borganida ham xuddi shu holat takrorlandi. O’nuchboy buning sababini so’raganida ish beruvchi 13 raqamidan qo’rqishini aytdi. Shunda O’nuchboy ish beruvchiga 13 raqamidan qo’rqmaslik uchun shunchaki 13 sonini hech qayerda ishlatmaslikni taklif qildi. Bu taklifdan so’ng ish beruvchi O’nuchboyga «Taklifing zo’r. Hozirda meni ma’lumotlar bazamda id raqami 0 dan \(10^N-1\) gacha bo’lgan ma’lumotlar mavjud, shularni ichidan id raqami yozilishida 13 raqami mavjud bo’lgan barcha ma’lumotlarni o’chirsam bazamda jami nechta ma’lumot qolishini hisoblab bera olsang ishga qabul qilaman» deb vada berdi.

O’nuchboy matematikani yaxshi bilmaydi, ammo unga ish juda zarur, ishga kirishi uchun unga sizning yordamingiz kerak. O’nuchboyning ishga kirishida yordam bering.

2
2
1

99
10

H. Hemming masofasi

Xotira: 16 MB, Vaqt: 1000 ms

Uzunligi \(N\) ga teng bo’lgan \(A\) va \(B\) massivlarning Hemming masofasi deb \(H(A, B) = \sum_{i=1}^{n} f(A,B,i)\) yig’indiga aytiladi. Bu yerda \(f(A,B,i)= \begin{cases} 1 \text{, } A_i \ne B_i \\ 0 \text{, } A_i = B_i \end{cases}\) 

Sizda \(N\) ta elementdan iborat \(F (F_i = i)\) to’plamning barcha anagrammalarini leksikografik o’sish tartibida joylashtirilgan jami \(N!\) ta ketma-ketlikdan iborat \(P\) to’plam bor. Siz \(\sum_{i=2}^{N!}H(P_i, P_{i-1})\) yig’indining \(10^9+7\) ga bo’lgandagi qoldiqni hisoblang!

3

12

I. Satrni o’zgartirish

Xotira: 16 MB, Vaqt: 1000 ms

Ali va Vali bir – biriga ajoyib boshqotirmalar berib savol-javob qilib turishni juda yaxshi ko’rishadi. Kunlardan bir kun Ali S satrni o’yladi va Valiga o’zi o’ylagan sonni topishni boshqotirma qilib berdi. Vali S satrni topa olishi uchun Ali o’ylagan satrini N marotaba quyidagi shakldaqa o’zgartirganidan so’ng P satr hosil bo’lganligini aytdi: Masalan agarda Ali contest so’zini o’ylagan bo’lsa bir marotaba o’zgartirgandan so’ng u ctosnet ga o’zgaradi. Agar uzbekistan so’zini o’ylagan bo’lsa bir marotaba o’zgartirgandan so’ng unzabteski ga o’zgaradi.

2
rotnocstboe

robocontest