A. Dominolar
Xotira: 32 MB, Vaqt: 1000 msKomiljon va Adhambek uy ishilarini qilib bo‘lgach, zerikib qolishdi. Endi ular domino donachalaridan binocha qurishmoqchi. Adhambekka bino balandligi muhim emas, lekin Komiljon bino balandligi kamida 28 ta dominodan qurilishi kerak deb hisoblaydi.
Sizga nechta domino donasi borligi aytiladi, agar dominolar soni bino qurish uchun yetarli bo‘lsa "Enough" deb chiqaring, aks holda yana nechta domino donasi kerak ekanligini chiqaring.
Yagona qatorda bitta butun son - \(n(0 \leq n \leq 45)\) mavjud domino donalari kiritiladi.
Domino donalari bino qurish uchun yetsa “Enough” deb chiqaring, aks holda yana nechta domino donasi kerak ekanligini chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
25 |
3 |
| 2 |
29 |
Enough |
B. Satrlarni tenglash
Xotira: 32 MB, Vaqt: 1000 msIngliz tili alifbosining kichik harflaridan iborat, uzunligi bir xil bo‘lgan 2 ta, \(A\) va \(B\) satrlar bor. Sizning vazifangiz \(A\) satrni \(B\) satr bilan bir xil qilishdir. Buning uchun \(A\) satrdagi ixtiyoriy belgini o‘zgartirish mumkin. Unli belgini unli belgiga hamda undosh belgini undosh belgiga o‘tkazish tekin, ammo unlidan undoshga va aksincha o‘tkazish uchun 1 so‘m to‘lash lozim. \(A\) satrni \(B\) satrga tenglashtirish uchun to‘lash kerak bo‘ladigan minimal narxni toping. Faqatgina {‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘y’} belgilari ingliz alifbosining unli belgilari hisoblanadi.
Kirish oqimining birinchi qatorida \(A\) satr kiritiladi.
Kirish oqimining ikkinchi qatorida \(B\) satr kiritiladi.
\(A\) va \(B\) satrlarning uzunligi bir xil ekanligi va ularning uzunligi 200 dan oshmasligi kafolatlanadi.
\(A\) satrni \(B\) satrga tenglashtirish uchun to‘lash kerak bo‘ladigan minimal summani chiqaring.
1-testda: “cat” satrini “rat” satriga o‘zgartirish uchun ‘c’ belgisini ‘r’ belgisiga o‘zgartirish yetarli. Undosh belgini undosh bepul, shuning uchun jami 0 so‘m to‘lash yetarli.
2-testda: \(A\) satridagi 3-9-harflarni o‘zgartirish uchun pul to‘lash lozim. Demak 7 so‘m to‘lash yetarli.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
cat rat |
0 |
| 2 |
abracadabra abacabadaba |
7 |
C. Introvert Komiljon
Xotira: 32 MB, Vaqt: 1000 msKomiljon bugungi informatika darsiga kechikib keldi. Vaholanki ba’zi bir kompyuterlar band edi. Informatika xonasidagi stolda jami \(N\) ta kompyuter bor, stol esa aylana shaklida. Ya’ni har bir \(i\) uchun \(i\)- va \(i+1\)-kompyuterlar hamda 1- va \(N\)-kompyuterlar qo‘shni hisoblanadi.
Komiljon introvert bola, shuning uchun u o‘ziga shunday joy tanlamoqchiki, u boshqa o‘quvchilar o‘tirgan joydan iloji boricha uzoqda joylashgan bo‘lsin. Boshqacha qilib aytgancha Komiljon tanlagan joyda uning chap qo‘shnisi undan \(x\) uzoqlikda, o‘ng qo‘shnisi \(y\) uzoqlikda (stol aylanaligi hisobidan ikkisi ham bir odam bo‘lishi mumkin) bo‘lsa, u \(min(x, y)\) qiymatni maksimallashtiruvchi o‘rindiqni tanlamoqchi. Sizning vazifangiz Komiljon uchun u istagan joyni tanlab berishdan iborat.
Kirish oqimining birinchi qatorida bitta butun son - \(N(2 \leq N \leq 2000)\) informatika xonasida joylashgan aylana stolidagi kompyuterlar soni.
Kirish oqimining ikkinchi qatorida uzunligi \(N\) bo‘lgan \(S\) satri kiritiladi.
\(S_i\) = ‘.’ bo‘lsa, \(i\)-kompyuter bo‘sh ekanligini, \(S_i\) = ‘#’ bo‘lsa, \(i\)-kompyuterni boshqa o‘quvchi band qilganligini anglatadi. Hech bo‘lmasa bitta kompyuter band ekanligi hamda hech bo‘lmasa bitta bo‘sh joy bor ekanligi kafolatlanadi.
Komiljonga unga mos keluvchi joyni tanlab bering. To‘g‘ri javob bir nechta bo‘lsa, istalganini chiqaring!
1-testda: Komiljon 3-kompyuter oldida o‘tirsa uning eng yaqin qo‘shnisi undan 2 masofada bo‘ladi. Ushbu holat uchun bu yagona optimal joy hisoblanadi.
2-testda: Komiljon 4-kompyuterdan tashqari, 5-, 10-, 11- kompyuterlarni tanlashi ham mumkin edi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 #...# |
3 |
| 2 |
12 ##....##.... |
4 |
D. Masalalar tuzuvchi kengash
Xotira: 256 MB, Vaqt: 1000 msInformatika fanidan olimpiadalarga masala tuzuvchi kengashda jami \(N\) nafar a’zo bor. Yaqinda bo‘lib o‘tadigan musobaqa uchun kengashning \(i\)-a’zosi \(a_i\) ta masala taklif qildi. Boshqa nufuzli kengashdagi kabi bu kengashning ham o‘z boshlig‘i bor. Kengashning boshlig‘i taklif qilingan masalalarni rad etish huquqiga ega. Komitet boshlig‘ining fikricha musobaqa yaxshi o‘tishi uchun musobaqada hech kim undan ko‘proq masala tuzmasligi lozim. Ya’ni kengashning \(j\)-a’zosi boshliq bo‘lsa, barcha \(i(1 \leq i \leq N)\) uchun \(a_i \leq a_j\) sharti qanoatlantirilishi lozim.
Sizning vazifangiz har bir \(i(1 \leq i \leq N)\) uchun kengashning \(i\)-a’zosi boshliq bo‘ladigan bo‘lsa, musobaqa yaxshi o‘tishi uchun rad etilishi kerak bo‘lgan minimal masalalar sonini chiqaring. E’tibor bering, musobaqa uchun masalalar qolmasligi ham mumkin.
Birinchi qatorda bitta butun son - \(N (1 \leq N \leq 2*10^5)\) kiritiladi.
Ikkinchi qatorda probel bilan ajratilgan \(N\) ta son - \(a_i(1 \leq a_i \leq 10^9)\) qiymatlari kiritiladi.
\(N\) ta butun son ekranga chiqaring. \(i\)-son \(i\)-kengash a’zosi boshliq bo‘lsa, musobaqa yaxshi o‘tishi uchun rad etish kerak bo‘lgan minimal masalalar sonini chiqaring.
1-testda:
1-a’zo kengash boshlig‘i bo‘lsa u faqatgina 2-a’zo taklif qilgan 1 ta masalani rad etsa maqsadga erishadi. Bunda taklif qilingan masalalar \([2, 2, 1]\) bo‘ladi.
2-a’zo kengash boshlig‘i bo‘lsa, hech qaysi masalalar rad etilmasa ham musobaqa yaxshi o‘tadi. Bunda taklif qilingan masalalar \([2, 3, 1]\) bo‘ladi.
3-a’zo kengash boshlig‘i bo‘lsa, 3 ta masala rad etilishi kerak bo‘ladi. Bunda taklif qilingan masalalar \([1, 1, 1]\) ko‘rinishida bo‘lishi kerak.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 2 3 1 |
1 0 3 |
| 2 |
6 1 1 0 7 9 12 |
25 25 30 7 3 0 |
E. K-th subarray sum
Xotira: 256 MB, Vaqt: 1000 msUzunligi \(N\) bo‘lgan musbat sonlardan iborat \(A\) massiv mavjud. Komiljon oldin bu massivning har bir qism massivi uchun uning elementlarini yig‘indisini yozib chiqdi. So‘ng yozilgan barcha sonlarni kamaymaslik tartibida saraladi va bu sonlar orasida qiymati \(K\)-bo‘lganini tanlab oldi. Oradan biroz vaqt o‘tib Komiljon ushbu sonni unitib qo‘ydi. Endi u sizdan bu sonni topib berishni so‘radi. Unga yordam bering.
Birinchi qatorda ikkita butun son - \(N\) va \(K\). \((1 \le N \le 2 \cdot 10^5); (1 \le K \le \frac{N(N+1)}{2})\)
Ikkinchi qatorda probel bilan ajratilgan \(N\)ta son - \(A\) massiv elementlari kiritiladi. \((0 \le A_i \le 10^9)\)
Ekranga yagona son, barcha qism massiv yig‘indilari orasida \(K\)-kichigini chiqaring.
1-testda \([1, 2]\) massivning 3 ta qism massivi mavjud, bular: \([1]\); \([2]\); \([1, 2]\). Ularning yig‘indisi 1, 2, 3ga teng. \(K=1\) holatda javob 1.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 1 1 2 |
1 |
| 2 |
6 7 4 12 5 0 3 9 |
8 |