A. Almashuvchi skaner

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Zilola kartochkalarni tekshiradigan kichik skaner yasadi. Har bir kartochkada belgi faqat bitta tomonda joylashgan: chap tomonda yoki o'ng tomonda.

Skaner boshida chap tomonni tekshiradi. Kartochkalar \(1\)-kartochkadan \(n\)-kartochkagacha tartib bilan skanerga kiritiladi.

Agar joriy kartochkadagi belgi skaner tekshirayotgan tomonda bo'lsa, kartochka qabul qilinadi va skaner darhol boshqa tomonni tekshiradigan holatga o'tadi. Aks holda kartochka o'tkazib yuboriladi va skanerning holati o'zgarmaydi.

Berilgan kartochkalar ketma-ketligidan nechta kartochka qabul qilinishini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(n\) beriladi \((1 \le n \le 2 \cdot 10^5)\).

Ikkinchi qatorda uzunligi \(n\) ga teng \(s\) satri beriladi. Har bir \(s_i\) belgisi `L` yoki `R` bo'ladi. `L` belgi chap tomonda, `R` esa o'ng tomonda ekanini bildiradi.

Chiquvchi ma'lumotlar:

Qabul qilingan kartochkalar sonini chiqaring.

Izoh:

Birinchi namunada har bir kartochkadagi belgi skaner tekshirayotgan tomonga mos keladi. Shuning uchun \(6\) ta kartochkaning hammasi qabul qilinadi.

Ikkinchi namunada dastlabki ikki kartochka o'tkazib yuboriladi. Uchinchi kartochka qabul qilinadi, so'ng skaner o'ng tomonni tekshiradi. To'rtinchi kartochka o'tkazib yuboriladi, beshinchi kartochka qabul qilinadi. Javob \(2\).

Uchinchi namunada \(1\)-, \(3\)-, \(4\)-, \(5\)-, \(7\)- va \(8\)-kartochkalar qabul qilinadi. Jami \(6\) ta kartochka qabul qilingan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 LRLRLR	6
2	5 RRLLR	2
3	8 LLRLRRLR	6

B. Panellar

Xotira: 65 MB, Vaqt: 1000 ms

Masala

Sizga \(n\) ta panel berilgan. Har bir panel to'g'ri to'rtburchak shaklida bo'lib, ularning eni va bo'yi yig'indisi \(B\) ga teng. Panellar chapdan o'ngga ketma-ket joylashtirilgan. Sizga har bir panelning hozirgi balandligi \(a_i\) beriladi. Istalgan panellarni 90 gradus o'ngga aylantirishingiz mumkin. Agar balandligi \(a_i\) bo'lgan panel aylantirilsa, uning yangi balandligi bu uning eni bo'ladi. Ba'zi panellarni aylantirish orqali panellarning balandliklarini chapdan o'ngga kamaymaydigan tartibga keltirish mumkinmi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t\) — testlar soni beriladi. Har bir test uchun birinchi qatorda ikkita butun son \(n\) va \(B\) beriladi. Ikkinchi qatorda \(n\) ta butun son \(a_1,a_2,\ldots,a_n\) beriladi. Cheklovlar:

\[1 \le t \le 1000\] \[1 \le n \le 2 \cdot 10^5\] \[2 \le B \le 10^9\] \[1 \le a_i < B\]

Bitta testcase ichidagi barcha testlar bo'yicha:

\[\sum n \le 2 \cdot 10^5\]

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda `YES`, agar kerakli tartibga erishish mumkin bo'lsa, aks holda `NO` chiqaring. Javobni istalgan registrda chiqarish mumkin.

Izoh:

Birinchi testda panellar balandliklarini \(2,3,4\) qilib tanlash mumkin. Ikkinchi testda hech qanday aylantirishlar orqali balandliklarni kamaymaydigan tartibga keltirib bo'lmaydi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 10 8 3 6 4 10 7 8 6 2 5 12 5 7 6 8 4 1 2 1 4 9 6 5 7 4	YES NO YES YES NO

C. Mukofot

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Botir aka zavodni muvaffaqiyatli boshqarib, oy oxirida \(n\) ta xodimiga mukofot bermoqchi.

Xodimlar bir qatorda turishadi va chap tarafdan \(1\) dan \(n\) gacha raqamlangan. Har bir xodimning ish samaradorligi \(p_i\) butun son bilan ifodalangan.

Xodimlar bir-birini yaxshi taniydi. Har bir xodim o'zining chap va/yoki o'ng qo'shnilari orasida o'zidan samaradorligi qat'iy yuqori bo'lganlarning sonini biladi. Bu sonni xodimning bosimi deb ataymiz.

Botir aka quyidagi qoidaga amal qilmoqchi: agar ikkita qo'shni xodimdan birining bosimi ikkinchisidan qat'iy katta bo'lsa, u qat'iy ko'proq mukofot olishi shart. Bosimlar teng bo'lsa — hech qanday cheklov yo'q.

Barcha mukofotlar musbat butun son bo'lishi kerak (kamida \(1\) so'm).

Botir aka xarajatni imkon qadar kamaytirmoqchi. Minimal umumiy mukofot summasini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son \(t\) — test-caselar soni.

Har bir test-case uchun:

Birinchi qatorda butun son \(n\) — xodimlar soni.

Ikkinchi qatorda \(n\) ta butun son \(p_1, p_2, \ldots, p_n\) — xodimlarning ish samaradorliklari.

\(1 \le t \le 10^4\)

\(1 \le n \le 2 \times 10^5\)

\(1 \le p_i \le 10^9\)

Barcha \(n\) larning yig'indisi \(2 \times 10^5\) dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir test-case uchun bitta butun son — minimal umumiy mukofot summasini chop eting.

Izoh:

1-test: \(p = [3, 1, 4, 1, 5]\)

Bosimlarni hisoblaymiz: \(i=1\) uchun o'ng qo'shni \(1 < 3\), shuning uchun bosim \(= 0\); \(i=2\) uchun chap \(3 > 1\) va o'ng \(4 > 1\), bosim \(= 2\); \(i=3\) uchun chap \(1 < 4\) va o'ng \(1 < 4\), bosim \(= 0\); \(i=4\) uchun chap \(4 > 1\) va o'ng \(5 > 1\), bosim \(= 2\); \(i=5\) uchun chap \(1 < 5\), bosim \(= 0\).

Bosimlar: \([0, 2, 0, 2, 0]\). Qo'shni juftliklar uchun majburiyatlarni hisobga olsak, minimal to'g'ri topshiriq \([1, 2, 1, 2, 1]\) bo'lib, jami \(= 7\).

2-test: Barcha samaradorliklar teng, shuning uchun barcha bosimlar \(0\). Hech qanday cheklov yo'q — hammaga \(1\) beriladi, jami \(= 4\).

3-test: \(p = [1, 2, 3, 4, 5]\) — o'suvchi ketma-ketlik. Bosimlar: \([1, 1, 1, 1, 0]\). Faqat oxirgi juftda bosim farqi bor (\(1\) vs \(0\)), shuning uchun minimal topshiriq \([1, 1, 1, 2, 1]\), jami \(= 6\).

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 1 4 1 5	7
2	4 2 2 2 2	4
3	5 1 2 3 4 5	6

D. Unutilgan indekslar

Xotira: 65 MB, Vaqt: 1000 ms

Masala

Sizga uzunligi \(n\) bo'lgan massiv berilgan:

\[ a_1,a_2,\ldots,a_n \]

Har bir indeks \(i\) uchun \(c_i\) narx ham beriladi. Siz massivdagi istalgan indekslarni unutib yuborishingiz mumkin. Agar \(i\)-indeks unutilsa, buning uchun \(c_i\) narx to'lanadi. Unutilmagan indekslar chapdan o'ngga qaralganda quyidagi shart bajarilishi kerak:

\[ a_j-a_i\ge d \]

Bu yerda \(i\) va \(j\) — ikkita ketma-ket unutilmagan indeks va \(i \lt j\). Boshqacha aytganda, qolgan elementlar indeks tartibini saqlagan holda har safar kamida \(d\) ga oshib borishi kerak. Sizning vazifangiz — massivni shartga mos holatga keltirish uchun to'lanadigan eng kichik umumiy narxni topish. Kamida bitta indeks unutilmay qolishi kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(t\) — testlar soni beriladi. Har bir test uchun birinchi qatorda ikkita butun son \(n\) va \(d\) beriladi. Ikkinchi qatorda \(n\) ta butun son beriladi:

\[ a_1,a_2,\ldots,a_n \]

Uchinchi qatorda \(n\) ta butun son beriladi:

\[ c_1,c_2,\ldots,c_n \]

Bu yerda \(c_i\) — \(i\)-indeksni unutish narxi. Cheklovlar:

\[ \begin{aligned} 1&\le t\le 1000,\\ 1&\le n\le 2\cdot 10^5,\\ 1&\le \sum n\le 2\cdot 10^5,\\ 0&\le d\le 10^9,\\ 1&\le a_i,c_i\le 10^9. \end{aligned} \]

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda bitta butun son chiqaring — shart bajarilishi uchun to'lanadigan minimal narx.

Izoh:

Birinchi testda \(2\)- va \(4\)-indekslarni unutish mumkin. Qolgan elementlar:

\[ 4,7,10 \]

Ular orasidagi farqlar:

\[ 7-4=3,\qquad 10-7=3 \]

Demak, shart bajariladi. To'langan narx:

\[ c_2+c_4=5+4=9 \]

Ikkinchi testda massiv kamayib boradi:

\[ 5,4,3,2 \]

\(d=2\) bo'lgani uchun bir nechta elementni indeks tartibida qoldirish foyda bermaydi. Faqat \(4\)-indeksni qoldirib, qolganlarini unutish optimal. Narx:

\[ c_1+c_2+c_3=10+20+30=60 \]

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 5 3 4 1 7 5 10 8 5 6 4 7 4 2 5 4 3 2 10 20 30 40	9 60

E. 3D Panjara va Lampalar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

- Siz \( N \times M \times P \) o'lchamli uch o'lchamli panjaraga egasiz. Har bir katak \( (x, y, z) \) da bitta lampochka bor. Dastlab barcha lampochkalar o'chiq holatda.

Sizga \( K \) ta qadam beriladi. Har bir qadamda:

Panjaradan tasodifiy ravishda \( A \) katagi tanlanadi.
Panjaradan tasodifiy ravishda \( B \) katagi tanlanadi.
\( A = (x_1, y_1, z_1) \) va \( B = (x_2, y_2, z_2) \) bo'lsa, quyidagi shartni qanoatlantiruvchi barcha \( (x, y, z) \) kataklardagi lampochkalar holati almashtiriladi (yoniq bo'lsa o'chiriladi, o'chiq bo'lsa yoqiladi):

\( \min(x_1, x_2) \le x \le \max(x_1, x_2) \)
\( \min(y_1, y_2) \le y \le \max(y_1, y_2) \)
\( \min(z_1, z_2) \le z \le \max(z_1, z_2) \)

\( K \) qadam o'tgandan so'ng yoniq lampochkalarning kutilgan sonini toping.

Eslatma: \( A \) va \( B \) bir xil katak bo'lishi mumkin.

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son \( T \) — test holatlar soni kiritiladi.

Keyingi \( T \) ta qatorda to'rtta butun son \( N \), \( M \), \( P \) va \( K \) — panjaraning o'lchamlari va qadam soni beriladi.

\( 1 \le T \le 100 \)
\( 1 \le N, M, P \le 100\)
\( 0 \le K \le 10^4 \)

Chiquvchi ma'lumotlar:

Har bir test holat uchun bitta qatorda yoniq lampochkalarning kutilgan sonini chop eting. Javob \( 10^{-6} \) xatolikkacha qabul qilinadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 2 3 4 1 5 3 4 2	6.375000 17.419805

F. Kontest Zanjiri

Xotira: 256 MB, Vaqt: 1000 ms

Masala

KhIMIO 2026 musobaqa komiteti yangi kontest tayyorlamoqda. Ular \( N \) ta masala tuzishdi. Tajribalariga asoslanib, ba'zi masalalar boshqalaridan qiyinroq ekanligi ma'lum — bu munosabatlar yo'naltirilgan graf shaklida berilgan: \( u \) dan \( v \) ga yo'nalgan qirra mavjud bo'lsa, \( u \)-masala \( v \)-masaladan qat'iy osonroq degan ma'noni anglatadi.

Har bir masalaning \( q_i \) qiziqarlilik balli bor. Bu ball manfiy ham bo'lishi mumkin — zerikarli yoki takroriy mavzu kontestning umumiy sifatini pasaytiradi.

Komitet kontestni aynan \( K \) ta masaladan tuzmoqchi, va bu masalalar qiyinlik darajasi bo'yicha o'sish tartibida joylashtirilishi kerak. Barcha bunday yo'llar ichidan ular umumiy qiziqarlilik bali eng katta bo'lganini tanlashni xohlaydi.

Aynan \( K \) ta masaladan iborat to'g'ri kontestning maksimal umumiy qiziqarlilik balini toping. Agar bunday kontest tuzish mumkin bo'lmasa, IMPOSSIBLE deb chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda uchta butun son \( N \), \( M \), \( K \) — masala-nomzodlar soni, "qiyinroq" munosabatlar soni va kontest uzunligi.

Ikkinchi qatorda \( N \) ta butun son \( q_1, q_2, \ldots, q_N \) — har bir masalaning qiziqarlilik bali.

Keyingi \( M \) qatorda ikkitadan butun son \( u \) va \( v \) — \( u \)-masala \( v \)-masaladan qat'iy osonroq ekanligi.

\( 1 \le N \le 1000 \)
\( 0 \le M \le 5000 \)
\( 1 \le K \le N \)
\( -10^9 \le q_i \le 10^9 \)
Grafda sikl mavjud emasligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Uzunligi aynan \( K \) bo'lgan yo'lning maksimal umumiy qiziqarlilik balini chop eting.

Agar bunday yo'l mavjud bo'lmasa, IMPOSSIBLE deb chiqaring.

Izoh:

1-test: \( N = 5 \) ta masala, \( q = [8, 3, 5, 7, -2] \), \( K = 3 \). Graf quyidagicha:

1(8)
/ \
2(3) 3(5)
\ / \
4(7) 5(-2)

Uzunligi 3 bo'lgan barcha yo'llar:
- \( 1 \to 2 \to 4 \): ball \( 8 + 3 + 7 = 18 \)
- \( 1 \to 3 \to 4 \): ball \( 8 + 5 + 7 = 20 \) (maksimal)
- \( 1 \to 3 \to 5 \): ball \( 8 + 5 + (-2) = 11 \)

Javob: 20.

2-test: 4 ta masala zanjir bo'lib ulangan: \( 1 \to 2 \to 3 \to 4 \). Eng uzun yo'l uzunligi 4, lekin \( K = 5 \) kerak. To'g'ri kontest tuzib bo'lmaydi, javob: IMPOSSIBLE.

3-test: \( N = 6 \), \( q = [0, 100, 1, 2, 3, -50] \), \( K = 3 \). Graf:

1(0) -> 2(100) [o'tuvchi qirra yo'q]
1(0) -> 3(1) -> 4(2) -> 5(3)
-> 6(-50)

2-masala jozibali ko'rinadi (\( q_2 = 100 \)), lekin \( 1 \to 2 \) yo'li uzunligi 2 va 2-masaladan chiquvchi qirra yo'q — uni \( K = 3 \) ga yetkazib bo'lmaydi.

Uzunligi 3 bo'lgan barcha to'g'ri yo'llar:
- \( 1 \to 3 \to 4 \): ball \( 0 + 1 + 2 = 3 \)
- \( 1 \to 3 \to 6 \): ball \( 0 + 1 + (-50) = -49 \)
- \( 3 \to 4 \to 5 \): ball \( 1 + 2 + 3 = 6 \) (maksimal)

Yo'l manba (kirish darajasi 0 bo'lgan) tugundan boshlanishi shart emas — istalgan joydan boshlanishi mumkin.

Javob: 6.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 5 3 8 3 5 7 -2 1 2 1 3 2 4 3 4 3 5	20
2	4 3 5 1 2 3 4 1 2 2 3 3 4	IMPOSSIBLE
3	6 5 3 0 100 1 2 3 -50 1 2 1 3 3 4 4 5 3 6	6

G. Qulfli segmentlar

Xotira: 65 MB, Vaqt: 1000 ms

Masala

Sizga uzunligi \(n\) bo'lgan massiv berilgan:

\[ a_1,a_2,\ldots,a_n \]

Massivni bir yoki bir nechta bo'sh bo'lmagan ketma-ket segmentlarga bo'lish kerak. Segmentlar massivning barcha elementlarini chapdan o'ngga qamrab oladi, har bir element aynan bitta segmentga kiradi. Segment \([l,r]\) ning kaliti \(K(l,r)\) quyidagicha aniqlanadi:

\[ K(l,r)=\min(a_l,a_{l+1},\ldots,a_r)+\max(a_l,a_{l+1},\ldots,a_r) \]

Bo'linish yaxshi deyiladi, agar hosil bo'lgan segmentlar chapdan o'ngga qaralganda ularning kalitlari kamaymaydigan tartibda bo'lsa. Agar bo'linishda \(m\) ta segment bo'lsa va ularning kalitlari \(k_1,k_2,\ldots,k_m\) bo'lsa, quyidagi shart bajarilishi kerak:

\[ k_1\le k_2\le \cdots \le k_m \]

Sizning vazifangiz massivni yaxshi bo'linishlar sonini topishdir. Javob juda katta bo'lishi mumkin, shuning uchun uni \(998244353\) ga bo'lgandagi qoldiq sifatida chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(t\) — testlar soni beriladi. Har bir test uchun birinchi qatorda bitta butun son \(n\) beriladi. Ikkinchi qatorda \(n\) ta butun son beriladi:

\[ a_1,a_2,\ldots,a_n \]

Cheklovlar:

\[ \begin{aligned} 1&\le t\le 1000,\\ 1&\le n\le 2000,\\ 1&\le \sum n\le 2000,\\ 1&\le a_i\le 10^9. \end{aligned} \]

Bu yerda \(\sum n\) barcha testlar bo'yicha \(n\) qiymatlari yig'indisini bildiradi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda bitta butun son chiqaring — yaxshi bo'linishlar sonining \(998244353\) ga bo'lgandagi qoldig'i.

Izoh:

Birinchi testda massiv \(1,2,3\) ko'rinishida berilgan. Uning barcha mumkin bo'lgan bo'linishlari yaxshi:

\[ [1][2][3],\quad [1][2,3],\quad [1,2][3],\quad [1,2,3] \]

Bu bo'linishlarning kalitlari mos ravishda:

\[ 2,4,6;\qquad 2,5;\qquad 3,6;\qquad 4 \]

Shuning uchun javob \(4\). Ikkinchi testda massiv \(3,1,2\) ko'rinishida berilgan. Yaxshi bo'linishlar faqat ikkitadir:

\[ [3,1][2],\quad [3,1,2] \]

Uchinchi testda barcha elementlar teng. Har bir segmentning kaliti \(10\) ga teng bo'ladi, shuning uchun har qanday bo'linish yaxshi. Uzunligi \(4\) bo'lgan massiv uchun bo'linishlar soni \(2^3=8\).

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 3 1 2 3 3 3 1 2 4 5 5 5 5	4 2 8