Minorada joylashgan qadimiy soat mexanizmi bor. Unga bitta son \(n\) kiritilsa, mexanizm uni \(m\) marta ketma-ket "aylantiradi".
Har bir aylanishda quyidagi ikki amal bajariladi:
Ushbu jarayon aynan \(m\) marta takrorlanadi. Sizning vazifangiz — barcha aylanishlardan so'ng hosil bo'ladigan yakuniy sonni topishdan iborat.
Yagona qatorda ikkita butun son \(n\) va \(m\) beriladi (\(1 \le n \le 10^{18}\); \(1 \le m \le 10^{18}\)) — boshlang'ich son va aylanishlar soni.
Barcha \(m\) marta aylanishdan so'ng hosil bo'lgan yakuniy sonni chop eting.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
7 3 |
7 |
Sizning platformangiz foydalanuvchilaridan biri xavfsizlik tizimi uchun maxsus raqamli shifrlash usulini o'ylab topdi. Berilgan \(N\) ta butun sondan iborat \(A\) massivdagi har bir son ustida ma'lum bir matematik amal bajarilib, yakuniy qiymat hisoblanishi kerak.
Har bir \(A_i\) son uchun quyidagi shartlar asosida qiymat topiladi:
Sizning vazifangiz — massivdagi barcha o'zgarishlar bajarilgandan keyingi hosil bo'lgan yangi elementlarning arifmetik o'rtacha qiymatini topish.
Birinchi qatorda bitta butun son — \(N\) (\(1 \le N \le 10^3\)) massiv elementlarining soni kiritiladi.
Ikkinchi qatorda \(N\) ta butun sondan iborat \(A\) massiv elementlari \(A_1, A_2, \dots, A_N\) probel bilan ajratilgan holda kiritiladi (\(-10^4 \le A_i \le 10^4\)).
Masalaning natijasi sifatida bitta haqiqiy son — o'zgarishdan keyingi massiv elementlarining arifmetik o'rtachasini \(10^{-2}\) xona aniqlikda chiqaring.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
4 4 3 -2 0 |
2.00 |
| 2 |
3 9 16 5 |
36.00 |
Raqamlar Akademiyasining sirli xazinalar omborida \(n\) ta turli qiymatli afsungar sonlardan iborat \(a_1, a_2, \dots, a_n\) qatoriy massivi saqlanadi.
Akademiya ustozlari shunday qoida o'rnatishganki, massiv ichidan ikkita turli o'rindagi \(i\) va \(j\) (\(1 \le i < j \le n\)) elementlarini tanlaganda, ularning yig'indisi (\(a_i + a_j\)) juft son bo'lsa, bunday juftlik mukofotga loyiq "Sehrli juftlik" deb e'tirof etiladi
Sizning vazifangiz — ombordagi barcha mumkin bo'lgan elementlar orasidan jami nechta shunday "Sehrli juftlik" hosil qilish mumkinligini topishdan iborat.
Birinchi qatorda yagona butun son \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — massivdagi elementlar soni kiritiladi.
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) — massiv elementlari beriladi.
Yagona qatorda — Akademiya talablariga mos keluvchi barcha "Sehrli juftliklar" sonini chop eting.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
5 2 4 6 3 5 |
4 |
| 2 |
4 1 2 3 4 |
2 |
Qadimiy minorada \(n\) ta sehrli kristall topilgan, ularning har birida \(a_i\) miqdorda energiya bor. Afsonaga ko'ra, agar ikkita kristallni birlashtirilsa va ularning energiyalari yig'indisi maxfiy son \(k\) ga qoldiqsiz bo'linsa, o'sha juftlik yashirin portalni ochadi.
Sehrgar sizdan yordam so'rayapti: minoradagi barcha kristall juftliklari orasida nechtasi portal ochish qobiliyatiga ega ekanini aniqlab bering — chunki minora qulab tushishidan oldin faqat bitta imkoniyat qoladi, va sehrgar qaysi juftlikni tanlashni oldindan bilmoqchi.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi (\(1 \le n \le 2 \times 10^5\); \(1 \le k \le 10^9\)) — kristallar soni va portal sirli soni.
Ikkinchi qatorda \(n\) ta butun son \(a_1, \dots, a_n\) beriladi (\(0 \le a_i \le 10^9\)) — har bir kristallning energiyasi.
Portal ochishga qodir bo'lgan \((i, j)\) juftliklar sonini chop eting, bunda \(1 \le i < j \le n\) va \((a_i + a_j) \pmod k = 0\).
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
4 3 3 1 5 2 |
2 |
| 2 |
5 5 5 10 15 20 25 |
10 |
| 3 |
6 4 1 3 2 2 5 7 |
5 |
1-Test: \(n=4\), \(k=3\), kristallar: \(3, 1, 5, 2\)
Barcha juftliklarni tekshiramiz:
Jami \(2\) ta juftlik portal ochadi: \((1, 5)\) va \((1, 2)\).
2-Test: \(n=5\), \(k=5\), kristallar: \(5, 10, 15, 20, 25\).
Har bir son \(5\) ga qoldiqsiz bo'linadi (qoldig'i \(0\)), shuning uchun istalgan ikkita kristall birlashsa ham yig'indi \(5\) ga bo'linadi. Jami juftliklar soni \(\binom{5}{2} = \frac{5 \times 4}{2} = 10\).
3-Test: \(n=6\), \(k=4\), kristallar: \(1, 3, 2, 2, 5, 7\).
Har bir kristallni \(4\) ga bo'lgandagi qoldig'iga qarab guruhlaymiz:
Qoldig'i \(2\) bo'lgan guruh o'zi ichida (\(2 + 2 = 4\), \(4 \pmod 4 = 0\)) — \(1\) ta juftlik: \((2, 2)\). Qoldiq \(1\) va qoldiq \(3\) guruhlari o'zaro birlashadi (yig'indi \(4\) karrali bo'ladi): \(1 + 3 = 4\), \(1 + 7 = 8\), \(5 + 3 = 8\), \(5 + 7 = 12\) — \(4\) ta juftlik.
Jami: \(1 + 4 = 5\) ta juftlik portal ochadi.
Sizga o'lchami \(n \times m\) bo'lgan to'g'ri burchakli labirint berilgan. Labirint \(n\) ta qatordan iborat bo'lib, har bir qator \(m\) ta belgidan tashkil topgan. Har bir katak ikkita holatdan biriga ega:
Qatorlar \(1\) dan \(n\) gacha (yuqoridan pastga), ustunlar esa \(1\) dan \(m\) gacha (chapdan o'ngga) raqamlangan. \((r, c)\) katak \(r-\)qator va \(c-\)ustunda joylashgan katakni bildiradi.
Siz \((1, 1)\) katakdan sayohatni boshlaysiz va \((n, m)\) katakka yetib borishingiz kerak. Bir qadamda joriy katakdan unga chegaradosh (yuqori, quyi, chap yoki o'ng) katakka o'tishingiz mumkin.
Sizda maxsus kuch bor: sayohat davomida jami ko'pi bilan \(k\) ta devor katagini "buzib", oddiy bo'sh katakka aylantirib, undan o'tishingiz mumkin. Devorni buzib o'tish ham bitta oddiy qadam kabi hisoblanadi (ya'ni devor bo'lgan katakka o'tish ham 1 ta qadam sifatida hisoblanadi, lekin bunday o'tishlar soni \(k\) tadan oshmasligi kerak).
\((1, 1)\) va \((n, m)\) katakchalari har doim bo'sh \(\text{«.»}\) bo'lishi kafolatlanadi.
\((1, 1)\) dan \((n, m)\) gacha yetib borish uchun kerak bo'ladigan eng kam qadamlar sonini toping. Agar hech qanday holatda (ko'pi bilan \(k\) ta devor buzib ham) yetib bo'lmasa, \(-1\) chiqaring.
Birinchi qatorda uchta butun son \(n\), \(m\) va \(k\) (\(2 \le n, m \le 300\); \(0 \le k \le \min(n \cdot m,\ 20)\)) — labirintning o'lchamlari va buzish mumkin bo'lgan devorlar sonining chegarasi berilgan.
Keyingi \(n\) ta qatorning har birida \(m\) ta belgidan iborat qator berilgan — labirintning tasviri (\(\text{«.»}\) yoki \(\text{«#»}\)).
Yagona butun sonni — \((1,1)\) dan \((n,m)\) gacha yetib borish uchun kerak bo'ladigan eng kam qadamlar sonini (yoki bu imkonsiz bo'lsa \(-1\)) chiqaring.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
3 5 1 ..... ##### ..... |
6 |
| 2 |
5 5 0 ..... ..... ..... ....# ...#. |
-1 |
| 3 |
5 5 1 ..... ..... ..... ....# ...#. |
8 |
1-Test: O'rtadagi qator to'liq devordan iborat, shuning uchun kamida bitta devorni buzish kerak. Masalan, \((1,1) \to (2,1)\) (devor buzib) \(\to (3,1) \to (3,2)\) \(\to (3,3) \to (3,4) \to (3,5)\) — jami \(6\) ta qadam.
2-Test: \(k=0\) bo'lgani uchun devor buzish mumkin emas, \((5,5)\) katakning ikkala qo'shnisi ham devor bo'lgani sabab uni umuman bosib bo'lmaydi.
3-Test: Endi bitta devor buzish mumkin. \((5,5)\) katakka \((4,3)\) yoki \((3,5)\) orqali kirib, faqat bitta devorni buzish kifoya qiladi — javob Manhetten masofasiga (\(4+4=8\)) teng bo'lib qoladi.
Minora qulashidan oldin, alkimyogar qatorda tizilgan \(n\) ta kristallni (\(a_1, a_2, \dots, a_n\) tartibida, energiyalari mos ravishda) \(m\) ta yordamchisiga taqsimlab berishi kerak. Har bir yordamchi kristallarning ketma-ket (tartibni buzmasdan) bo'lagini oladi — ya'ni massiv aynan \(m\) ta bo'sh bo'lmagan qismga bo'linadi.
Alkimyogar adolatli bo'lishni xohlaydi: eng ko'p energiya olgan yordamchining yukini iloji boricha kamroq qilishni istaydi. Eng kichik mumkin bo'lgan maksimal yukni toping.
Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi (\(1 \le m \le n \le 2 \times 10^5\)).
Ikkinchi qatorda \(n\) ta butun son \(a_1, \dots, a_n\) beriladi (\(1 \le a_i \le 10^9\)) — kristallarning energiyalari.
Eng kichik mumkin bo'lgan maksimal yukni chop eting.
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
5 2 7 2 5 10 8 |
18 |
| 2 |
5 3 7 2 5 10 8 |
14 |
| 3 |
7 4 4 8 9 2 3 6 5 |
12 |
1-Test: \(n=5\), \(m=2\), kristallar: \(7, 2, 5, 10, 8\)
Massivni \(2\) ta ketma-ket bo'lakka bo'lamiz: \([7, 2, 5]\) (yig'indi = \(14\)) va \([10, 8]\) (yig'indi = \(18\)). Ikki bo'lakning maksatli maximumi = \(18\). Boshqa har qanday bo'linish bundan kattaroq yuk beradi, shuning uchun eng kichik maksimal yuk = \(18\).
2-Test: \(n=5\), \(m=3\), xuddi shu kristallar
Endi \(3\) ta bo'lakka bo'lamiz: \([7, 2, 5]\) (\(14\)), \([10]\) (\(10\)), \([8]\) (\(8\)). Maksimal yuk = \(14\). Bo'laklar soni oshgani sari yukni tekislash osonlashadi, shuning uchun javob kamaydi (\(18 \rightarrow 14\)).
3-Test: \(n=7\), \(m=4\), kristallar: \(4, 8, 9, 2, 3, 6, 5\)
Optimal bo'linish maksimal yukni \(12\) ga tushiradi. Undan kichik limit bilan bo'lib bo'lmaydi, chunki \(9\) o'zi katta element bo'lib, kamida bitta guruh yukini \(12\) ga yetkazadi.