A. XOR

Xotira: 16 MB, Vaqt: 1000 ms

Biz yangicha fibonachchi sonlarining turini ishlab chiqdik, u quyidagicha hosil qilinadi. Avvaliga \(K\) ta son olinadi, demak fibonachchining dastlabki \(K\) ta elementi shular ya’ni quyidagicha:
\(F(1) = a_1,  F(2) = a_2, \space F(3) = a_3, \space\dots\space, \space F(k) = a_k\)
Qolgan elementlari esa o`zidan oldingi K tasining umumiy xoriga teng ya’ni quyidagicha:
\(F(i) = F(i−1) \space\text{xor}\space F(i−2) \space\text{xor}\space F(i-3) \space\text{xor}\space … \space\text{xor}\space F(i-k), \space (\text{qachonki} \space i > k)\)
Demak sizga yangicha Fibonachchi ketma-ketligimiz tushunarli bo`lsa sizning vazifangiz \(L\) va \(R\) oraliqdagi barcha fibonachchi sonlarimizni umumiy xor qiymatini hisoblab berishingiz talab qilinadi ya’ni quyidagicha:
\(F(L) \space\text{xor}\space F(L+1) \space\text{xor}\space F(L+2) \space\text{xor}\space … \space\text{xor}\space F(R-1) \space\text{xor}\space F(R)\)

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

3
1
0

5
3 3 4 3 2
4
1 2
1 3
5 6
7 9

0
4
7
4

B. Alien

Xotira: 16 MB, Vaqt: 1000 ms

Yaqinda kosmik kemamiz boshqa gallaktikadagi yerga o`xshash sayyoraga borib qo`ndi, bu yerda ham tirik mavjudod bor ekan, baxtga ko`ra ular ham idrok etish va hatto musiqa kuylab pianino chalishni yaxshi ko`rishar ekan. U yerdagilardagi o`zgacha xususiyat ularda qo`l barmoqlari aynan 10 ta emas ekan hammada har xil, \(K\) ta ekan, bizni yangicha pianinoda esa \(N\) ta klavish bo`lib har bir klavishni o`zining yangicha xususiyati bor, har bir klavishda aniq bir tovush \(A_i\) balandligi bor ba’zilarining tovush balandligi bir xil, agar siz 2 ta bir xil balandlikdagi tovush chiqaradigan klavishni bossangiz ixtiyoriy biri ovoz chiqaradi, ammo 2 ta turli xil ovozdagini bossangiz faqat baland ovozlisi ovoz chiqaradi, bu holat bir nechta klavishni bosganda ham shunday, endi biz o`zga sayyorlik do`stimizga shu holatda har doim har xil usuldagi urunishlarni hamma barmoqlari bilan tengidan klavishlarni bosganida umumiy tovush balandligining yig`indisi qancha bo`lashini so`ragandik, u buni hisoblab bera olmadi, endi siz ularni mushkulini yengillashtirish uchun bizga dastur tuzib yordam bering.

5 3
2 4 2 3 4

39

5 1
1 0 1 1 1

4

C. Min-Max

Xotira: 32 MB, Vaqt: 1000 ms

\(L\) va \(R\) oraliqdan shunday eng kichik va eng katta sonlarni topingki har ikkilasining ham raqamlari yig`idisi \(N\) ga teng bo`lsin.

1
20
5

5
14

100
200
10

109
190

D. Reverse-Sort

Xotira: 32 MB, Vaqt: 1000 ms

Vectorni saralashda biz ushbu metodni ishlatamiz bu yerda ishlatilayotgan divider() metodi vectorni eng kam sondagi kamayuvchi qism massivlarga bo`lib beradi, bu funksiyani birinchi marta chaqirilganda undan qaytgan qism massivlar uzunligi juft bo`ladi, bu holat faqat birinchi marta chaqirilganda, reverse() metodi vectorni teskarisiga o`girib beradi.

Sizga \(N\) ta elementda iborat \(A\) vector berilgan, vector elementlari \(1\) dan \(N\) gacha bo`lgan sonlarning qaysidir permutatsiyasi, siz vectorni bizning sort() metodimiz orqali saralaganingizda eng kamida necha marta reverse() metodi chaqiriladi.

4
4 3 2 1

1

E. Make-String

Xotira: 512 MB, Vaqt: 2500 ms

Sizga \(N\) uzunlikda \(S\) satr beriladi. Sizning vazifangiz ushbu satrdan yana bir nusxa tayyorlash, buning uchun sizga \(M\) ta \(L_i\) \((1 \le i \le M)\) satrchalar borligi aytiladi, bu satrchalar cheksiz ko`p. Siz \(S\) satrni \(M\) xil satrlar yordamida qayta yozishingiz kerak bunda \(L_i\) satr bilan \(L_j (1 \le i \le M, 1 \le j \le M,  i \space \text{va} \space j \space \text{bir xil bo`lishi mumkin})\) satrni faqat o`xshash harflarini ustma – ust qo`yish yordamida birlashtirishingiz yoki satrlarni ketma-ket joylashtirishingiz mumkin. Satrlarning tartibi buzilishiga ham ruxsat etilgan ammo satrlarni bo`laklash yoki teskarisiga o`girish mumkin emas.

Sizning vazifangiz \(S\) satrdan eng kam nechta belgini qayta tiklay olmasligingizni aniqlash. Unutmang siz hosil qiladigan satr \(N\) dan oshmasligi kerak!

18
abrakadabrakadabra  
3
abr
kada
kobra

3

18
abrakadabrakadabra  
3
abra
kada
kobra

0