A. Black Blast!

Xotira: 256 MB, Vaqt: 2000 ms

Talabalar uzoqdagi universitetga borish uchun har kuni metroda uzoq vaqt o'tkazadilar. Metroda internet tortmayotgani sababli ular zerikishdan qutulish uchun yangi o'yin - Black Blast! ni o'ynashga ahd qilishdi.

O'yin qoidalari quyidagicha:

• O'yin maydoni to'rtburchak (N x M) va unga 1x1 o'lchamli "toshchalar" joylashtiriladi.
• Agar maydonning biror vodiy yoki ustuni to'liq toshlar bilan to'lgan bo'lsa, u qatordagi barcha toshlar birdaniga yo'qolib ketadi.

Talabalar quyidagi savolga qiziqib qolishdi: Maydonga maksimal ravishda nechta tosh joylashtirish mumkin, shunda hech qaysi qatorda ham, ustunda ham barcha kataklar band bo'lmaydi va biror tosh yo'qolib ketmaydi? 

Bitta testda, birinchi qatorida testlar soni \(T\) beriladi. Keyingi \(T\) ta qatorda har birida \(N, M\) - maydon o'lchamlari beriladi. Har bir test uchun maksimal nechta tosh joylash mumkinligini aniqlang.

3
15 3
20 20
14 16

30
380
208

B. Eldorning skaneri

Xotira: 256 MB, Vaqt: 1000 ms

Eldor laboratoriyada bir qator bo‘ylab joylashgan 1 dan N gacha raqamlangan kataklar ustida ishlaydigan skaner yasadi.

- Eldor skanerni 1-katak ustiga qo‘yadi.
- Har bir yonishda u 1 ta katak oldinga (yoki orqaga) siljiydi.
- Agar skaner chetga yetib qolsa (ya’ni \(1\) yoki \(N\)), u darhol teskari tomonga qaytib davom etadi(sakraydi).

Shuning uchun yongan kataklar ketma-ketligi quyidagicha bo‘ladi:

- N = 5 bo‘lsa: 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, ...
- N = 3 bo‘lsa: 1, 2, 3, 2, 1, 2, 3, ...

Eldor har safar skaner qaysi katak ustida yonayotgan bo‘lsa, shuncha ball oladi (katak raqamiga teng).

Sizning vazifangiz: Eldor birinchi K ta yonishdan keyin necha ball yig‘ishini hisoblash. 

4
5 8
4 9
1 7
3 10

24
21
7
19

C. Eng yaqin daraja son

Xotira: 256 MB, Vaqt: 1000 ms

Natural son \(n\) daraja son deyiladi, agar shunday natural sonlar \(a\) va \(b\) mavjud bo‘lsa:

• \(a\ge 1\)
• \(b \ge 2\)
• \(n = a^b\)

Masalan:

• \(32 = 2^5\), \(169 = 13^2\), \(1 = 1^2\) — daraja sonlar.
• \(72\), \(2000\), \(31\) — daraja sonlar emas.

Sizga \(N\) va \(M\)  hamda \(N\) ta \(x_1, x_2, ..., x_N\) sonlar beriladi. Har bir \(x_i\)\([1, M]\) oralig‘ida.

Har bir \(x_i\) uchun \([1,M]\) oralig‘idan shunday \(r_i\) sonini topingki:

• \(r_i\) daraja son bo‘lsin;
• \([1,M]\) oralig‘idagi istalgan boshqa daraja son \(p\) uchun quyidagi shart bajarilsin:

\(|x_i - r_i| \le |x_i - p|\)

Ya’ni \(r_i\) — \(x_i\) ga eng yaqin daraja son bo‘lishi kerak.

6 1000
345
99
999
500
26
124

343
100
1000
512
25
125

D. Robot-kuryer

Xotira: 256 MB, Vaqt: 1000 ms

Husanboy “Algoritm Express” kompaniyasida kichik robot-kuryer Robo-1 ni sinovdan o‘tkazyapti. Robo-1 har daqiqada batareya holatini yozib boradi (to‘liq sikl n daqiqadan iborat):

• 'S' — robot quyosh panelidan quvvat oldi (batareya \(+1\)).
• 'M' — robot harakat qildi (batareya \(-1\)).

Sinov oxirida robot butun marshrutni aylana bo‘ylab aylanib chiqadi va yana boshlang‘ich joyiga qaytadi. Afsuski, jurnal saqlanayotgan paytda tizim buzilib, yozuvlar aylanma ko‘rinishda saqlanib qolgan: ya’ni sizda faqat \(n\) ta belgi bor, lekin qaysi daqiqadan boshlanganini bilmaymiz.

Siz istalgan k (1 ≤ k ≤ n) boshlanish daqiqasini tanlab, jurnalni quyidagicha o‘qiysiz:

\(S[k], S[k+1], ..., S[n], S[1], ..., S[k-1]\)

Husanboy robot haqiqiy startda batareyasi \(0\) bo‘lgan deb hisoblaydi. Tanlangan \(k\) to‘g‘ri start bo‘lishi uchun(ikkala shart ham bajarilishi majburiy):

1. O‘qish davomida batareya hech qachon manfiy bo‘lib ketmasin.
2. \(n\) daqiqadan so‘ng batareya yana \(0\) ga qaytsa.

Sizning vazifangiz: nechta \(k\) boshlanish daqiqasi to‘g‘ri ekanini toping.
 

3
4
SMSM
6
MMSSSM
5
SSSMM

2
1
0

E. Arxiv segmentlari 2

Xotira: 256 MB, Vaqt: 1000 ms

Yer orbitasidagi Arxiv-Lentada ketma-ket joylashgan \(N\) ta yozuv bor. Har bir yozuv uchun \(a[i]\) qiymat berilgan (\(1..M\) oralig‘ida) — bu yozuvning maxfiylik darajasi.

Siz lentani ketma-ket bo‘laklarga ajratib, imkon qadar ko‘p mustaqil segment hosil qilmoqchisiz.

Mustaqil segment 

\([s,d]\) oralig‘idagi ketma-ket yozuvlar \(a[s], a[s+1], ..., a[d]\) mustaqil segment deyiladi, agar segmentdan tashqarida turgan har bir yozuv segment ichidagi yozuvlar bilan “aralashib” keta olmasa.

Aniqroq qilib aytganda, agar \(i\notin [s, d]\) bo‘lsa, unda quyidagi shartlardan aynan bittasi bajarilishi shart.

1. \(a[i]\) segment ichidagi barcha qiymatlardan kichik:
   \(a[i] < a[j]\) barcha \(s \le j \le d\) uchun;
2. \(a[i]\) segment ichidagi barcha qiymatlardan katta:
   \(a[i] > a[j]\) barcha \(s \le j \le d\) uchun;

Berilgan \(N, M\) va \(a\) ketma-ketligi uchun lentani ketma-ket segmentlarga ajrating:

• har bir indeks aynan bitta segmentga tegishli bo‘lsin;
• segmentlar soni maksimal bo‘lsin.

Natija sifatida:

1. maksimal segmentlar soni \(G\) ni chiqaring;
2. har bir segmentning oxirgi indeksi (\(d\) lar) ni o‘sish tartibida chiqaring.

Eslatma: oxirgi segmentning oxirgi indeksi doim \(N\) bo‘ladi.

6 5
1 4 2 3 5 5

5
1 2 3 4 6

4 3
3 1 2 1

2
1 4

7 5
1 3 2 1 5 2 4

1
7

14 10
5 8 6 7 5 2 1 2 3 3 4 10 9 10

5
5 8 10 11 14