A. Yozuv terish mashinasi

Xotira: 32 MB, Vaqt: 1000 ms

Bir kuni Asilbek kulguli mashinaga duch keldi! U juda katta ekran va bitta tugmadan iborat edi. U qurilmani ishga tushirgach, ekranda faqat A harfi ko'rindi. U tugmani bosgandan so'ng, harf B ga o'zgardi. Keyingi bir necha marta tugmani bosganida so'z B dan BA ga, so'ngra BAB ga, keyin BABBA ga aylandi… Buni ko‘rgach, Asilbek mashina so‘zni shunday o‘zgartirishini tushundiki, barcha B harflari BA ga, A harfi esa B ga aylanadi.

Mashinadan zavqlangan Asilbek sizga juda qiyin savol berdi! Tugmani K marta bosgandan so'ng ekranda qancha A harfi va qancha B harfi ko'rsatiladi?

1

0 1

4

2 3

10

34 55

B. Ramka

Xotira: 32 MB, Vaqt: 1000 ms

Shohruh ajoyib krossvord to'pladi va endi uni ramkaga solmoqchi. Shohruhning krossvord boshqotirmasi \(N \times M\) harflaridan iborat bo‘lib, uning atrofidagi ramka tepada \(U\), chapda \(L\), o‘ngda \(R\) va pastki tomonda \(D\) qalinlikda bo‘lishi kerak.
Ramka # (panjara) va . (nuqta) belgilardan iborat. shaxmat taxtasidagi maydonlar kabi almashinadi. Bu belgilar shunday joylashtirilishi kerakki, agar ramka butun krossvordni qamrab oladigan darajada kengaytirilsa va biz bu belgilarni shaxmat taxtasi deb hisoblasak, # belgilari shaxmat taxtasidagi qizil maydonlar sifatida joylashtirilishi kerak (ya'ni, yuqori chap maydon) . Vazifani yaxshiroq tushunish uchun quyidagi misollarga qarang.

4 4
2 2 2 2
abcd
efgh
ijkl
mnop

#.#.#.#.
.#.#.#.#
#.abcd#.
.#efgh.#
#.ijkl#.
.#mnop.#
#.#.#.#.
.#.#.#.#

2 5
1 0 3 1
salom
dunyo

#.#.#.#.
salom#.#
dunyo.#.
.#.#.#.#

C. Musobaqa

Xotira: 128 MB, Vaqt: 1000 ms

Huquqni muhofaza qilish organlaridagi kutilmagan muammolar Shohruhni yangi kasbni egallashga majbur qildi: u kompyuter fanlari bo‘yicha jamoaviy musobaqaning bosh tashkilotchisiga aylandi.
Musobaqada ishtirok etishni xohlovchi N ta klublar mavjud. Klublar prezidentlari juda o'jar va musobaqada jamoaning barcha klub a'zolari ishtirok etishi mumkin bo'lgan taqdirdagina qatnashadilar.
Tanlov ikki turdan iborat: saralash va final. Raqobat qilayotgan barcha jamoalar teng miqdordagi a'zolarga ega bo'lishi va bitta jamoaning barcha a'zolari bir klubga tegishli bo'lishi kerak. Saralash bosqichida har bir klubning istalgan sonidagi jamoalar ishtirok etishi mumkin va har bir klubning eng yaxshi jamoasi final bosqichiga yo‘llanma oladi.
Shohruh biladiki, unga reklama kerak. Shu sababli, u finalda tomoshabinlar soni imkon qadar ko'p bo'lishi uchun final ishtirokchilari sonini ko'paytirishni xohlaydi.
Yodda tuting, har bir ishtirokchi klub finalda bitta jamoa bilan chiqish huquqiga ega. Bundan tashqari, musobaqada kamida ikkita klub ishtirok etishi kerak, aks holda musobaqa homiylarni jalb qilish uchun juda zerikarli bo'ladi.
Finalda ishtirokchilarning maksimal sonini aniqlang, shunda Shohruh jamoa o'lchamini tanlashi shart bo'lmaydi.

3
1 2 4

4

2
1 5

2

5
4 6 3 8 9

9

D. Ifodani maksimallashtirish

Xotira: 1024 MB, Vaqt: 1000 ms

Sizga n ta sondan tashkil topgan massiv beriladi. Siz quyidagi amalni ko'pida bir marotaba bajarishingiz kerak:

•  (i va j) juftlikni tanlang va \(a_i\) ni qiymatini \(a_j\) bilan o'zgartiring. (\(a[i] = a[j]\))

Bu amalni bajarishdan asosiy maqsad esa 1 ta k (1 ≤ k ≤ n) butun sonini tanlash va quyidagi ifoda qiymatini maksimallashtirish:

• (\(a_1\)&\(a_2\)&…&\(a_k\)) + (\(a_{k+1}\)&\(a_{k+2}\)&…&\(a_n\))

Bu yerda & belgisi - bitwise AND operatori

6
6 5 4 3 5 6

10

3
0 7 3

10

9
5 0 4 3 3 0 1 3 3

5

E. Xesh funksiya

Xotira: 512 MB, Vaqt: 3000 ms

Shohruh raqamli qiymatlarni so'zlarga bog'laydigan xesh funksiyasini o'rganmoqda. Funksiya rekursiv ravishda quyidagicha aniqlanadi:
• f( bo'sh so'z ) = 0
• f( so'z + harf ) = ( f( so'z ) * 33 ) XOR ord( harf ) ) % MOD
Funksiya ingliz alifbosining faqat kichik harflaridan iborat so'zlar uchun belgilanadi. 

• XOR bitli XOR operatorini bildiradi (masalan, 0110 XOR 1010 = 1100);
• ord(harf) alifbodagi harfning tartib raqamini bildiradi (ord(a) = 1, ord(z) = 26);
• A % B B raqami bilan butun sonni bo‘lishda A sonining qolgan qismini bildiradi;
• MOD \(2^M\) ko‘rinishdagi butun son bo‘ladi.

M = 10 bo'lganda xesh funktsiyasining ba'zi qiymatlari:

•  f( a ) = 1
• f ( aa ) = 32
• f ( kit ) = 438

Mirko N uzunligidagi nechta so'zning K hash qiymatiga ega ekanligini bilmoqchi. Unga bu sonni hisoblashda yordam beradigan dastur yozing.

1 0 10

0

1 2 10

1

3 16 10

4