A. Sehrgarning Kod Lentalari

Xotira: 256 MB, Vaqt: 1000 ms

Auron ismli sehrgar qadimiy qo‘lyozmalardan topilgan maxfiy kodlarni saqlaydi. Har bir kod qog‘oz lentaga yozilgan bo‘lib, unda kichik ingliz harflari ketma-ket joylashgan.

Sehrgar qo‘lida \(N\) ta kod lentasi bor.

U barcha lentalarni istalgan tartibda birlashtirib, bitta uzun kod hosil qilmoqchi. Har bir lentani ulashdan oldin uni:

• o‘z holicha qoldirish,
• yoki butunlay teskari aylantirish (reverse)

mumkin.

So‘ng hosil bo‘lgan uzun kodning ikki uchi tutashtirilib, yopiq halqa hosil qilinadi.

Halqaning kuchi unda ketma-ket joylashgan bir xil harflarning eng uzun guruhi bilan aniqlanadi. Halqa yopiq bo‘lgani sababli, kodning oxirgi va birinchi harflari ham qo‘shni hisoblanadi.

Sehrgarga halqaning eng katta kuchini topishda yordam bering, ketma-ket keladigan bir xil harflarning maksimal mumkin bo‘lgan sonini aniqlang.

2
ab
cb

2

3
abbc
cbbb
abb

5

4
abbba
aaaa
aaa
aa

11

B. O‘rgimchak to‘ri va pashshalar

Xotira: 256 MB, Vaqt: 2000 ms

O‘rgimchak ulkan to‘rni qurib qo‘ygan. Bu to‘r \(N \times M\) kataklardan iborat maydon shaklida tasvirlanadi. Har bir katak — o‘rgimchak to‘rining tuguni.

To‘r ichida K ta pashsha ilinib qolgan. Har bir pashsha aynan bitta tugunda joylashgan.

O‘rgimchak juda ayyor: u o‘tirgan joyidan turib, bitta tugunni “markaz” sifatida tanlaydi va barcha pashshalarni shu nuqtaga tortib keladi. Pashshani to‘r bo‘ylab faqat gorizontal yoki vertikal harakatlantira oladi.

Har bir pashshaning “qarshiligi” uning bosib o‘tgan yo‘li uzunligiga teng, ya’ni Manhattan masofasi bilan o‘lchanadi.

O‘rgimchak shunday \((x, y)\) tugunni tanlashi kerakki, barcha pashshalarning umumiy qarshiligi minimal bo‘lsin:

\(\sum (|X_i - x| + |Y_i - y|)\)

Vaqt o‘tishi bilan to‘r o‘zgara boshlaydi. Q ta hodisa sodir bo‘ladi.

Har bir hodisada (X, Y) tugun bilan bog‘liq voqea bo‘ladi:

• agar bu tugunda pashsha bo‘lsa — u to‘rdan chiqib ketadi
• agar yo‘q bo‘lsa — yangi pashsha shu tugunga ilinadi
   

Sizdan talab qilinadi, har bir holat uchun:

• o‘rgimchak tanlaydigan optimal tugun \((x, y)\)
• minimal umumiy qarshilik

3 3 3
1 1
2 3
3 1
0

2 1
4

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

2 3
11
4 3
6
4 1
4
4 4
0
2 3
0
3 3
0

C. Buyuk Ipak Yo‘lidagi Karvon

Xotira: 256 MB, Vaqt: 1000 ms

Buyuk Ipak Yoʻli bo‘ylab har yili minglab savdogarlar uzoq safarga otlanishardi. Ular orasida eng mashhuri — dono va tajribali karvonboshi Mirzo edi.

Mirzoning karvonida \(N\) ta arava ketma-ket joylashgan bo‘lib, har bir aravaga \(1\) dan \(N\) gacha bo‘lgan sonlardan bittasi yozilgan. Har bir son aynan bir marta uchraydi. Demak, aravalardagi sonlar \(1\) dan \(N\) gacha bo‘lgan sonlarning permutatsiyasini tashkil qiladi.

Karvonning boshida, o‘rtasida va oxirida harakatlanishning mashaqqatlari turlicha bo‘lgani sababli, Mirzo vaqti-vaqti bilan karvonning ma’lum bir qismini qayta tartiblab turardi, ya'ni u karvonning ma’lum bir qismini tanlab, o‘sha qism ichidagi aravalarni aylantirib turardi: 

• ba’zan qism boshidagi aravalarni uning oxiriga,
• ba’zan esa qism oxiridagi aravalarni uning boshiga o‘tkazardi.

Mirzo bajargan buyruqlari ketma-ketligini sizga taqdim etadi, siz uning savollariga javob bering.

Sizga \(Q\) ta buyruq beriladi. Har bir buyruq quyidagi uch turdan biri bo‘ladi:

• \(L \ a \ b \ k\) -  \(a\)- tartibli aravadan \(b\)- tartibli aravagacha bo‘lgan qismni chapga \(k\) marta aylantirish, ya'ni \(k\) marta qism boshidagi element qism oxiriga ko‘chiriladi.
• \(R \ a \ b \ k\) -  \(a\)- tartibli aravadan \(b\)- tartibli aravagacha bo‘lgan qismni o'ngga \(k\) marta aylantirish, ya'ni \(k\) marta qism oxiridagi element qism boshiga ko‘chiriladi.
• \(P \ x\) - Hozirgi holatda \(x\)-tartibli aravada qaysi son yozilganini aniqlang.

Bu yerda: 

• \(1 \le a < b \le N\)
• \(1 \le k \le b-a+1\)
• \(1 \le x \le N\)

7 5
7 5 3 1 4 2 6
L 1 3 2
R 2 4 1
P 1
P 4
P 7

3
5
6

5 5
3 5 4 2 1
R 3 5 1
R 1 4 1
P 1
R 1 5 4
P 1

4
3

D. Mining Serverlari

Xotira: 256 MB, Vaqt: 1000 ms

Katta mining fermada n ta server mavjud. Har bir serverning boshlang‘ich yuklamasi 0 ga teng.

Har bir serverning ishlashida muhim texnik xususiyat bor, ya'ni server H dan katta yuklamani saqlab tura olmaydi. Agar yuklama H dan oshsa, u avtomatik ravishda yuklamani H ga teng qilib, ortiqcha yuklamani tashlab yuboradi.

Ferma boshqaruvchilari serverlarni umumiy bitta tizimga bo'ysundirgan holda ishlashadi, va tizim orqali serverlarga ketma-ket jami M ta operatsiyani amalga oshirishadi. Har bir operatsiya quyidagilardan ixtiyoriy biri bo'lishi mumkin:
 

1.  N X
   Tizim barcha serverlarga bir xil yuklama qo‘shadi:
   - har bir serverning yuklamasi X ga oshadi
   - agar natija H dan oshsa → u avtomatik ravishda H ga teng bo‘lib qoladi
2. L X
   Chap tomondan birinchi X ta server qayta ishga tushiriladi (reset) natijada ularning yuklamasi 0 ga tushadi.
3. D X
   O‘ng tomondan birinchi X ta server qayta ishga tushiriladi (reset) natijada ularning yuklamasi 0 ga tushadi.
4. S X
   Server xonasidagi shovqinni vaqtinchalik kamaytirish maqsadida yuklamasi X dan katta bo'lgan serverlarning X dan ortiqcha qismi olib tashlanadi, ya'ni:
   - agar server yuklamasi X dan katta bo‘lsa → u X darajasiga tushiriladi
   - aks holda o‘zgarmaydi
5. Z
   Monitoring so‘rovi. Ya'ni barcha serverlar yuklamalarining yig‘indisini chiqaring.

10 1000 5
Z
N 10
Z
L 3
Z

0
100
70

10 1000 10
N 10
L 5
Z
N 10
L 3
Z
D 2
Z
S 1
Z

50
120
80
5

7 10 10
N 9
Z
N 9
Z
N 5
Z
S 1
Z
N 10
Z

63
70
70
7
70