A. Tug'ilgan kun

Xotira: 256 MB, Vaqt: 1000 ms

Yerdagi shavqatsizliklarga chiday olmagan Azizbek "Xalvarion" sayyorasiga ko'chib o'tdi. Bilamiz yerda bir yil 365 kunga teng bo'lsa  Xalvarion sayyorasida 364 kunga teng (qulaylik uchun kabisa yillari yo'q deb hisoblaymiz). Har yil \(364\) kundan iborat, kunlar \(1\) dan \(364\) gacha raqamlanadi. Xalvarion va Yer sayyorasi bir vaqtda paydo bo'lgan, shuning hisobidan 1-yilning 1-kuni ikkala sayyorada ham bir kunga to'g'ri keladi. Azizbek ham aynan shu kuni tug'ilgan. Azizbekga oila a'zolari tug'ilgan kunni nishonlashni har yili bir xil sanada deb emas, har 365 kunda keladi deb o'rgatishgan. Azizbek Xalvarion sayyorasida uning \(x-\) tug'ilgan kuni qaysi sanada bo'lishiga qiziqmoqda.

5

5 5

400

401 36

B. Signal Zanjiri

Xotira: 256 MB, Vaqt: 1000 ms

Robototexnika laboratorida ketma-ket ulangan \(N\) ta signal modul mavjud. Har bir modulda ikkita port qiymati yozilgan:

- chap port: \(s\)

- o‘ng port: \(d\)

Modullar aynan berilgan tartibda joylashgan. Ikki qo‘shni modul mos (compatible) deyiladi, agar birinchisining o‘ng porti ikkinchisining chap portiga teng bo‘lsa:  \(d[i] = s[i+1]\)

Biror \([l..r]\) ketma-ket modul bo‘lagi to‘liq mos deyiladi, agar ushbu bo‘lak ichidagi har bir qo‘shni juftlik mos bo‘lsa:  \(d[l]=s[l+1], d[l+1]=s[l+2], ..., d[r-1]=s[r]\)

Berilgan modullar ketma-ketligida to‘liq mos bo‘lgan eng uzun bo‘lak (subarray) uzunligini toping.

Subtasklar

- Subtask 1 (7 ball): barcha juftliklar mos keladi yoki birorta juftlik mos kelmaydi.

- Subtask 2 (10 ball): \(N \le 200\)

- Subtask 3 (30 ball): \(N \le 5000\)

- Subtask 4 (53 ball): Qo'shimcha cheklovlarsiz.

5
2 10
10 5
5 2
2 10
37 5

4

1
5 7

1

C. Sug‘orish kanali

Xotira: 1024 MB, Vaqt: 1000 ms

Sizning bog‘ingiz bo‘ylab chapdan o‘ngga qarab ketadigan uzunligi N bo‘lgan sug‘orish kanali bor. Kanal \(N\) ta ketma-ket bo‘limdan iborat (har biri 1 metr). Har bir bo‘limning hozirgi balandligi \(h[1], h[2], ..., h[N]\) metr.

Siz kanalni bir xil balandlikda qilishni xohlaysiz, ya’ni hamma bo‘limlar balandligini aynan \(H\) ga keltirmoqchisiz.

Buning uchun sizda “shlyuz”li texnika bor: u chapdan o‘ngga yuradi va ortiqcha tuproqni o‘zi bilan olib ketishi mumkin.

• Siz oldindan bitta natural son \(H\) ni tanlaysiz.
• Dastlab texnikada olib yurilayotgan tuproq miqdori \(C = 0\).
• Texnika i-bo‘limga kelganda:

1. Agar \(h[i] \ge H\) bo‘lsa, ortiqcha tuproq \(h[i] - H\) kesib olinadi va zaxiraga qo‘shiladi:
   \(C += h[i] - H\). Bo‘lim balandligi \(H\) bo‘lib qoladi.
2. Agar \(h[i] < H\) bo‘lsa, bo‘limni \(H\) ga ko‘tarish uchun zaxiradan \(H - h[i]\) tuproq to‘kiladi.
   Bu faqat \(C \ge H - h[i]\) bo‘lsa mumkin. So‘ng \(C -= H - h[i]\) va bo‘lim balandligi \(H\) bo‘ladi.

Oxirida zaxirada qolgan tuproq sizni qiziqtirmaydi — u kanal oxiridagi daryoga to‘kilib ketadi.

Vazifa: shunday eng katta \(H\) ni topingki, texnika chapdan o‘ngga yurib, hech qachon zaxirasi yetmay qolmasdan, barcha bo‘limlarni aynan H balandlikka keltira olsin.

Subtasklar

- Subtask 1 (7 ball): \(h\) massiv o'suvchi. 

- Subtask 2 (38 ball): \(N \le 200\)

- Subtask 3 (55 ball): Qo'shimcha cheklovlarsiz.

4
5 2 1 6

2

D. Arxiv segmentlari

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 shart bajarilishi shart.

1. \(a[i]\) segment ichidagi barcha qiymatlardan farqli:
   \(a[i] \ne 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.

 

Subtasklar

- Subtask 1 (6 ball): \(M = 1\)

- Subtask 2 (7 ball): \(M = N\)

- Subtask 3 (19 ball): \(N \le 100\)

- Subtask 3 (22 ball): \(N \le 3000\)

- Subtask 4 (46 ball): Qo'shimcha cheklovlarsiz.

6 5
1 4 2 3 5 5

5
1 2 3 4 6

7 5
1 3 2 1 5 2 4

2
6 7

E. Weak Point

Xotira: 128 MB, Vaqt: 500 ms

Siz armiyaning qo‘mondonisiz. Armiyada \(n\) ta askar bor, ular 1 dan n gacha raqamlangan.
Har bir askarning o‘z kuchi mavjud — massiv \(a[1..n]\).

Biror \([l, r]\) oraliqdagi askarlardan guruh tashkil qilinsa, bu guruhning weak point (zaif nuqtasi) quyidagicha aniqlanadi:

• Weak point - ushbu oraliqda uchramaydigan eng kichik nomanfiy butun son, ya’ni \(MEX(l, r)\).

Guruhning umumiy kuchi esa quyidagicha hisoblanadi: 

\[Power(l, r) = MEX(l, r) \times \sum_{i=l}^{r} a[i]\]

 

Sizga \(q\) guruh beriladi. Har bir guruh \([l_i, r_i]\) oraliq bilan berilgan.
Sizning vazifangiz — berilgan barcha guruhlar orasida eng kuchli guruhning kuchini aniqlash.

Subtasklar

- Subtask 1 (9 ball): \(n \le 100\) \(q \le 100\)

- Subtask 2 (13 ball): \(n * q \le 10^6\)

- Subtask 3 (15 ball): \(n \le 5000\)

- Subtask 4 (25 ball): \(n \le 10^4\) \(q \le 10^5\)

- Subtask 5 (38 ball): Qo'shimcha cheklovlarsiz.

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

9