A. Sehrli Yo‘ldagi Xazina

Xotira: 256 MB, Vaqt: 1000 ms

Qadim zamonlarda bir sarkarda Jasur haqida afsona mavjud. U o‘z bahtini sinab ko‘rmoqchi bo‘lib, sehrli yo‘lga safarga chiqadi.
Bu yo‘l uzunligi \(N\) bo‘lib, uning har bir nuqtasida qadimiy sandiq joylashgan.

Har bir sandiq oltin bilan to'la, bu oltinlar soni quyidagicha:

\(a_1, a_2, \ldots, a_N\)

Sarkarda Jasur yo‘ldan o‘tib ketayotib, ketma-ket joylashgan biron segmentdagi sandiqlarni ochish huquqiga ega.

Lekin, antik qoidaga ko‘ra faqat quyidagi shartlar bajarilgandagina sandiqlarni ochishi mumkin:

• Tanlangan segmentdagi oltinlarning jami \(K\) dan oshmasligi kerak;
• Tanlangan segmentda eng ko‘p oltin va eng oz oltin bor sandiqlar orasidagi farq \(D\) dan katta bo‘lmasligi kerak.

Jasur, barcha shartlarga mos eng uzun ketma-ket segment uzunligini aniqlashni istaydi.

Unga bu masalada yordam bera olasizmi?

7 15 3
2 4 5 3 10 6 7

4

B. Qadimiy Ketma-ketlikning Sirli Og‘irligi

Xotira: 256 MB, Vaqt: 1000 ms

Bir kun kelib, siz qadimiy yodgorliklar daftarchasini topasiz va ichida quyidagi qiziqarli ketma-ketlik haqida ma'lumot o‘qiysiz:

Sizda ajoyib musbat butun sonlar ketma-ketligi bor:

\(a_1, a_2, \ldots, a_n\)

Har bir \((l, r)\) oralig‘i uchun \(1 \leq l \leq r \leq n\) uning sirli og‘irligi quyidagicha hisoblanadi:

\(W(l, r) = \gcd(a_l, a_{l+1}, \ldots, a_r) \times (r-l+1)\)

Bu yerda:

• \(\gcd\) — berilgan oraliqdagi sonlarning eng katta umumiy bo‘luvchisi,
• \((r-l+1)\) — oraliq uzunligi (nechta son tanlangan).

Sizga vazifa: barcha bo‘sh bo‘lmagan oraliqlar (kesmalar) ichidan eng katta sirli og‘irlikni toping.

Ya'ni, quyidagini aniqlang:

\(\max_{1 \leq l \leq r \leq n} \left( \gcd(a_l, a_{l+1}, \ldots, a_r) \times (r - l + 1) \right)\)

Qiziqartiruvchi savol: qadimiy ketma-ketlikda eng katta sirli og‘irlik qaysi oraliqqa to‘g‘ri keladi?

5
6 9 3 12 15

15

C. Davlat Boshqaruvi

Xotira: 256 MB, Vaqt: 2000 ms

Siz yangi barpo etilgan davlatning bosh me'morisiz. Davlatda \(N\) ta shahar bor va ular \(N - 1\) ta ikki tomonlama yo'l bilan bog'langan. Shaharlar tizimi daraxt strukturasini hosil qiladi (ya'ni, ixtiyoriy ikki shahar orasida yagona yo'l mavjud).

Qirol davlatni boshqarish uchun har bir shaharga bir nafardan amaldor tayinlashni buyurdi. Amaldorlarning darajalari ingliz alifbosining bosh harflari bilan belgilanadi: 'A', 'B', ..., 'Z'. Bu yerda 'A' eng yuqori daraja, 'B' esa undan keyingi o'rinda turadi va hokazo.

Qirolning talabi quyidagicha:

Agar ikki xil \(u\) va \(v\) shaharlariga bir xil darajali amaldorlar tayinlangan bo'lsa, u holda \(u\) va \(v\) shaharlarini bog'lovchi yagona oddiy yo'lda kamida bitta yuqoriroq darajali amaldor o'tirgan shahar bo'lishi shart.

Eslatma: Masalan, ikki shaharda ham 'C' darajali amaldor bo'lsa, ular orasidagi yo'lda kamida bitta 'A' yoki 'B' darajali amaldor bo'lishi kerak.

Sizning vazifangiz — Qirolning talabini qondiradigan tarzda amaldorlarni shaharlarga taqsimlash.

D. Suv omborlari

Xotira: 256 MB, Vaqt: 1000 ms

"Xirtam"deb nomlanuvchi bir o'lkada N ta suv omborlari bor. Sirli sabablarga ko'ra M ta bir tomonli ariqlar bor. Sizda ushubu ariqlarni ko'rsatuvchi xarita bor, unda siz M ta u, v, w ko'rinishidagi qiymatlar berilgan, bunda 1 kunda u suv omboridan undagi w% hajmiga teng suv ariq orqali v suv omboriga oqib o'tadi.

Sizga a massiv berilgan bo'lib, 1<=i<=N uchun a[i] i-suv omboradiga suv hajmini anglatadi.

Ushbu o'lka xalqi sizdan K kundan so'ng har bir suv omborida qancha hajmdagi suv qolishini so'rashdi

 

K juda katta son bo'lgani tufayli w% = w/100 ni w * inv(100) mod 998244353 qilib ishlang

bunda a mod b a ni b ga bo'lgandagi qoldiqni anglatadi

inv(a) mod b = aᵇ⁻² mod b qachonki b tub son bo'lsa

5 4 2
0 100 100 100 100
2 1 50
3 1 60
4 1 70
5 1 80

346 25 16 9 4