Berilgan \(n\) ta elementdan iborat \(a_1, a_2, \dots, a_n\) massivdan shunday \((i, j)\) indekslar juftligini topish kerakki, bunda \(1 \le i < j \le n\) shart bajarilsin va ularning yig'indisi \((a_i + a_j)\) juft son bo'lsin. Jami shunday "Sehrli juftliklar" sonini topish talab etiladi.

Asosiy g'oya (Matematik yondashuv):

Ikkita sonning yig'indisi \((a_i + a_j)\) qachon juft son bo'ladi? Buni bilish uchun ularning juft yoki toqligini tekshirish kifoya:

• Juft + Juft = Juft
• Toq + Toq = Juft
• Juft + Toq = Toq (bu bizga mos kelmaydi)

Demak, yig'indi juft chiqishi uchun tanlab olingan ikkita sonning ikkalasi ham juft bo'lishi yoki ikkalasi ham toq bo'lishi kerak.

Algoritm:

1. Massivdagi barcha sonlarni qarab chiqamiz va ularning nechtasi juft, nechtasi toq ekanini sanab olamiz:

• Juft sonlar sonini saqlash uchun even_count o'zgaruvchisini ochamiz.
• Toq sonlar sonini saqlash uchun odd_count o'zgaruvchisini ochamiz.

2. Juft sonlardan juftlik hosil qilish:
Agar massivda \(E\) ta juft son bo'lsa, ulardan ikkitasini tanlash usullari soni kombinatsealar formulasiga ko'ra \(E \times (E - 1) / 2\) ta bo'ladi.

3. Toq sonlardan juftlik hosil qilish:
Agar massivda \(O\) ta toq son bo'lsa, ulardan ikkitasini tanlash usullari soni \(O \times (O - 1) / 2\) ta bo'ladi.

4. Jami "Sehrli juftliklar" soni shu ikki qiymatning yig'indisiga teng:

\(\frac{E \times (E - 1)}{2} + \frac{O \times (O - 1)}{2}\)

Murakkablik:

Vaqt murakkabligi: \(O(n)\) — massivni bir marta to'liq ko'rib chiqib, juft va toq sonlar sanog'i topiladi. Bu \(n \le 2 \times10^5\) cheklovi uchun juda tez ishlaydi va vaqt chegarasiga bemalol ulguradi.
Xotira murakkabligi: \(O(1)\) yoki \(O(n)\) — massivni xotirada saqlash uchun (agar elementlarni birma-bir o'qib ketilsa, qo'shimcha massiv ham talab etilmaydi).

Bizga \(n\) ta kristallar energiyalari berilgan: \(a_1, a_2, \dots, a_n\), va yana maxfiy son \(k\). Shunday \((i, j)\) indekslar juftligini \((1 \le i < j \le n)\) topishimiz kerakki, ularning yig'indisi \(k\) ga qoldiqsiz bo'linsin, ya'ni \((a_i + a_j) \pmod k == 0\). Jami shunday juftliklar sonini chiqarish talab etiladi.

Asosiy g'oya (Matematik yondashuv / Modular Aritmetika):

Ikkita \(a_i\) va \(a_j\) sonlarining yig'indisi \(k\) ga bo'linishi uchun ularning \(k\) ga bo'lgandagi qoldiqlari yig'indisi \(k\) ga bo'linishi kerak. Boshqacha qilib aytganda:

\((a_i + a_j) \pmod k \equiv 0\) \( \iff\) \((a_i \pmod k + a_j \pmod k)\) \(\pmod k \equiv 0\)

Bu shartdan kelib chiqib ikki xil holatni ko'rishimiz mumkin:

1. Agar \(a_i \pmod k == 0\) bo'lsa, unga mos keluvchi ikkinchi sonning qoldig'i ham \(0\) bo'lishi kerak \((0 + 0 \equiv 0 \pmod k)\).
2. Agar \(a_i \pmod k == r\) bo'lsa \((r > 0)\), unga mos keluvchi ikkinchi sonning qoldig'i \(k - r\) bo'lishi kerak, shunda ularning yig'indisi \(r + (k - r) = k\) bo'lib, \(k\) ga qoldiqsiz bo'linadi.

Algoritm (Chastota massivi yoki Hash Map yordamida):

1. Massivdagi har bir elementni qarab chiqamiz va ularning \(k\) ga bo'lgandagi qoldig'ini topamiz: \(r = a_i \pmod k\).
2. Har bitta qoldiq necha marta uchraganini hisoblab borish uchun chastota massividan (map yoki massiv) foydalanamiz.
3. Hozirgi \(a_i\) elementi uchun, undan oldin kelgan va bizga mos keladigan qoldiqga ega elementlar sonini umumiy javobga qo'shamiz:
   — Agar \(r == 0\) bo'lsa, oldindan uchragan qoldig'i \(0\) bo'lgan elementlar sonini qo'shamiz.
   — Agar \(r > 0\) bo'lsa, oldindan uchragan qoldig'i \(k - r\) bo'lgan elementlar sonini qo'shamiz.
4. Oxirida barcha mos juftliklar yig'indisini chiqaramiz.

Murakkablik:

Vaqt murakkabligi: \(O(n)\) — massivni bir marta to'liq qarab chiqish va qoldiqlarni hisoblash kifoya. \(n \le 2 \cdot 10^5\) cheklovi uchun juda tez ishlaydi.
Xotira murakkabligi: \(O(k)\) yoki \(O(n)\) — qoldiqlar chastotasini saqlash uchun.

Bizga \(n \times m\) o'lchamli labirint berilgan. Boshlang'ich nuqta \((1, 1)\), oxirgi manzil esa \((n, m)\). Labirintda bo'sh kataklar ('.') va devorlar ('#') mavjud. Biz eng ko'pi bilan \(k\) ta devorni "buzib", oddiy bo'sh katakka aylantirgan holda \((1, 1)\) dan \((n, m)\) ga borish uchun ketadigan eng kam qadamlar sonini topishimiz kerak. Agar ilojsiz bo'lsa, \(-1\) chiqaramiz.

Asosiy g'oya (Shortest Path / BFS):

Bu turdagi eng qisqa yo'lni topish masalalarida BFS (Breadth-First Search - Eniga qidirish) algoritmidan foydalanamiz. Biroq, bu oddiy BFS emas, chunki bizda qo'shimcha resurs (\(k\) ta devor buzish imkoniyati) mavjud.

Holatni (state) quyidagicha belgilaymiz: \((r, c, \text{broken})\), bu yerda:

• \(r\) — hozirgi qator indeksi;
• \(c\) — hozirgi ustun indeksi;
• \(\text{broken}\) — shu paytgacha nechta devor buzib o'tilgani.

Cheklovlar kichik bo'lgani uchun (\(2 \le n, m \le 300\) va \(0 \le k \le \min(n \cdot m, 20)\)), holatlar soni unchalik katta emas.

Algoritm (0-1 BFS yoki Oddiy BFS + Visited massivi):

1. Navbat (Queue): BFS navbatiga boshlang'ich holatni qo'shamiz: \((1, 1, 0)\) — ya'ni \((1, 1)\) katakdamiz va hali \(0\) ta devor buzganmiz, qadamlar soni \(0\) ga teng.

2. Masofalar/Holatlar massivi (\(dist[r][c][broken]\)): Har bir katak uchun shu paytgacha sarflangan eng kam qadamlarni saqlab boramiz. Boshlang'ich qiymatlar cheksizlik (\(\infty\)) bilan to'ldiriladi.

3. Qadam tashlash:

• Hozirgi \((r, c)\) katakdan to'rtta qo'shni tomonga (yuqori, pastki, chap, o'ng) yuramiz.
• Agar qo'shni katak bo'sh ('.') bo'lsa, devor buzish soni o'zgarmaydi (\(\text{broken}\) o'zgarmaydi).
• Agar qo'shni katak devor ('#') bo'lsa, uni buzib o'tishimiz mumkin, bunda \(\text{broken} + 1\) ga teng bo'ladi (agar bu qiymat \(k\) dan oshib ketmasa).

4. Optimallashtirish: Har safar yangi holatga o'tganda qadamlar soni kamroq bo'lsagina uni navbatga qo'shamiz va dist massivini yangilaymiz.

5. \((n, m)\) katakiga yetib kelganimizdagi eng birinchi topilgan qadamlar soni eng qisqa yo'l bo'ladi (chunki BFS qadamma-qadam kengayib boradi). Agar oxirigacha borib bo'lmasa, \(-1\) chiqaramiz.

Murakkablik:

Vaqt murakkabligi: \(O(n \times m \times k)\) — har bir katak va har bir mumkin bo'lgan buzilgan devorlar soni holati uchun navbatdan bir marta o'tiladi. \(300 \times 300 \times 20 \approx 1.8 \times 10^6\) operatsiyani tashkil qiladi va vaqt chegarasiga bemalol ulguradi.
Xotira murakkabligi: \(O(n \times m \times k)\) — dist massivi va navbat uchun sarflanadigan xotira.

Bu masalada berilgan massivni tartibini buzmagan holda \(m\) ta ketma-ket bo'lakka bo'lishimiz va har bir bo'lak yig'indilarining eng kattasini (maksimal qismini) imkon qadar kichik qilishimiz talab etiladi.

Asosiy g'oya (Binary Search on Answer):

Massiv elementlari va o'lchami katta bo'lgani uchun (\(\le 2 \times 10^5\)), to'g'ridan-to'g'ri qidirib chiqish vaqt chegarasiga ulgurmaydi. Shuning uchun javobning o'zini ikkilik qidiruv orqali topamiz.

1. Qidiruv chegaralari (low va high):

• Javob eng kamida massivdagi eng katta elementga teng bo'lishi shart (\(low = max(a)\)), chunki bitta elementning o'zi boshqalardan katta bo'lsa ham guruh yig'indisini o'sha qiymatdan kamaytirib bo'lmaydi.
• Eng ko'pi bilan barcha elementlar yig'indisiga teng bo'lishi mumkin (\(high = sum(a)\)).

2. Ochko'zlik (Greedy) yondashuvi:

Ikkilik qidiruv orqali o'rtadagi qiymatni (\(mid\)) eng katta ruxsat etilgan limit deb olamiz. Keyin massivni chapdan o'ngga qarab yig'ib chiqamiz:

• Agar joriy elementni qo'shganda limitdan oshib ketsa, demak yangi yordamchiga o'tamiz (bo'laklar sonini \(1\) taga oshiramiz).
• Agar oxirida hosil bo'lgan bo'laklar soni \(m\) tadan oshib ketmasa, demak bu limitimiz to'g'ri keladi va javobni kichikroq tomonga qarab qidirib ko'ramiz (\(high = mid - 1\)). Aks holda limitni kattalashtiramiz (\(low = mid + 1\)).

Murakkablik

Ikkilik qidiruv taxminan \(O(\log(\text{sum}(a)))\) marta takrorlanadi.
Har bir tekshirish (greedy o'tish) \(O(n)\) vaqt oladi.
Umumiy murakkablik: \(O(n \times \log(\text{sum}(a)))\).