A. Akronim
Xotira: 64 MB, Vaqt: 1000 msSizga ingliz alifbosining kichik harflaridan tashkil topgan \(N\) ta so'z beriladi. Ularning akronimi toping.
Akronim - bir nechta so'zlarning birinchi harflarini birlashtirish va ularni katta harfga aylantirish orqali olinadigan so'z.
Birinchi qatorda butun son \(N \ (3 \le N \le 10)\) - so'zlarning umumiy miqdori kiritiladi.
Keyingi \(N\) ta qatorning har birida bittadan so'z kiritiladi. Har bir so'z faqatgina ingliz alifbosining kichik harflaridan tashkil topgan va uzunligi 20 dan oshmaydi.
Berilgan so'zlarning akronimini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 hyper text markup language |
HTML |
| 2 |
3 short message service |
SMS |
| 3 |
3 virtual private network |
VPN |
B. Sevimli satr
Xotira: 32 MB, Vaqt: 1000 msSatrning murakkabligi deb uning ichidagi turli harflar soni tushuniladi.
Masalan, “salom” so‘zi murakkabligi 5 ga, “banan” so‘zi esa murakkabligi 3 ga teng.
Siz murakkabligi 1 yoki 2 bo‘lgan satrlarni yoqtirasiz. Do‘stingiz sizga bir satr berdi va uni siz yoqtiradigan (ya’ni murakkabligi ≤2 bo‘lgan) satrga aylantirmoqchisiz. Buning uchun sizda sehrli o‘chirgich bor: u har safar satrdan bitta harfni o‘chirib tashlay oladi.
Berilgan satrni murakkabligi 2 dan oshmaydigan satrga aylantirish uchun minimal necha marta o‘chirgichdan foydalanishingiz kerak?
Bitta qatorda uzunligi 100 dan oshmaydigan kichik lotin harfidan (‘a’–‘z’) oshmagan satr berilgan.
Bitta qatorda o‘chirgichdan minimal necha marta foydalanish kerakligini chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
salom |
3 |
| 2 |
banan |
1 |
C. Minimalist
Xotira: 32 MB, Vaqt: 1000 msSiz mashhur minimalist haykaltarosh D’ning san’at ko‘rgazmasi uchun mas’ul etib tayinlandingiz (uning ismi ham minimal!). D’ning asarlari vertikal tarzda joylashtirilgan to‘g‘ri to‘rtburchak qutilarni ustma-ust joylashtirib, kichrayib borish tarzida tuzishdan iborat — ya’ni u katta qutilarni pastga, kichiklarini esa yuqoriga qo‘yadi.
Uning so‘nggi asari “2 ga 3 kamayuvchi” deb nomlangan bo‘lib, unda har birida 3 tadan quti bo‘lgan ikki ustun ko‘rinishidagi olti qutidan tashkil topgan to‘plamlar mavjud. Shunday to‘plamlardan biri quyida ko‘rsatilgan.
D sizga bu san’at asarini yubordi va siz muzeyga ushbu olti qutidan iborat to‘plamlarni to‘g‘ri tartibda joylashtirishingiz kerak. Biroq, bu asarlar muzeyga yetib kelganda, madaniyatsiz tashuvchilar (ya’ni, yetkazib beruvchilar) ularni polga tartibsiz tashlab ketishgan. Ular bu qutilarning asl tartibini bilmagan.
Endi siz bu ikki ustunni qayta tiklashingiz kerak, lekin qaysi quti ustida, qaysi biri ostida turganini bilmaysiz! Sizga faqat quyidagilar ma’lum:
- Sizda 6 ta qutining balandligi berilgan.
- Shuningdek, sizga ikki ustunning umumiy balandligi ham berilgan.
- Qutilar faqat va faqat yoki eng pastda, yoki o'zidan katta bo'lgan qutining ustida tura oladi.
Shu ma’lumotlar bilan ertangi ochilish marosimigacha bu qutilarni to‘g‘ri tartibda joylashtira olishga umid qilasiz.
Bitta qatorda 8 ta musbat butun son beriladi. Dastlabki 6 tasi — qutilarning balandliklari (tartibsiz holatda). So‘nggi 2 ta son — ustunlarning balandligi.
Qutilarning balandligi 100 dan oshmaydi. Qutilarning umumiy balandligi ustunlarning umumiy balandligiga teng.
Dastlab birinchi ustun balandligiga mos keladigan 3 ta qutining balandligini (kamayish tartibida: eng kattasi birinchi) chiqaring. So‘ngra ikkinchi ustun uchun qolgan 3 ta qutining balandligini ham kamayish tartibida chiqaring.
Agar bir nechta yechim mavjud bo'lsa istalganini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
16 8 30 24 34 17 41 88 |
17 16 8 34 30 24 |
| 2 |
7 6 22 8 20 25 67 21 |
25 22 20 8 7 6 |
D. O'quv markaz binosi
Xotira: 128 MB, Vaqt: 1000 msRobolandiya shahri xaritasi \(N×M\) o‘lchamdagi ikki o‘lchamli ko‘rinishda tasvirlangan. Bu shaharda dasturlashga qiziqqan bolalar soni juda ko‘p bo‘lib, ularning barchasi Robotics Lab o‘quv markaziga qatnamoqda. Ayni paytda o‘quvchilar soni shu qadar ortib ketdiki, mavjud binoda ularni joylashtirishning iloji qolmadi. Shu sababli, o‘quv markazi rahbari Zarif aka yangi bino qurishga qaror qildi.
Biroq, shaharning barcha joylariga bino qurish mumkin emas. Xaritada bino qurish mumkin bo‘lgan joylar # belgisi bilan, mumkin bo‘lmagan joylar esa . belgisi bilan belgilangan. Zarif aka allaqachon \(R×C\) o‘lchamdagi yangi bino loyihasini chizib chiqdi. Ushbu loyiha ham # va . belgilaridan iborat bo‘lib, # binoning qurilishi zarur bo‘lgan qismlarini, . esa bo‘sh joylarni anglatadi.
Muhim eslatma: Loyiha chizmasidagi har bir # belgisi shaharning aynan # belgisiga to‘g‘ri kelishi majburiydir. Loyiha chizmasidagi . belgilar esa shaharning istalgan nuqtasiga (# yoki ., hatto shahar tashqarisi ham) to‘g‘ri kelsa bo‘ladi. Boshqacha aytganda, faqat # larni moslashtirish zarur, . lar esa cheklovlarga ega emas. Loyihani aylantirish (rotatsiya) yoki ko‘zgudek akslantirish (mirror qilish) qat’iyan taqiqlanadi. Loyiha qanday ko‘rinishda berilgan bo‘lsa, aynan o‘sha holatda mos tushishi kerak.
Endi sizning vazifangiz — berilgan ikki chizmaga qarab, shaharning nechta turli nuqtasida ushbu loyihani to‘liq mos tarzda joylashtirish mumkinligini aniqlash.
Birinchi qatorda ikki butun son — \(R\) va \(C \ (1≤R,C≤16)\) beriladi. Ular loyiha chizmasining qatorlar va ustunlar sonini bildiradi.
Keyingi \(R\) ta qatorda har birining uzunligi \(C\) bo‘lgan loyiha chizmasi tasvirlanadi. Har bir belgining qiymati # yoki . bo‘ladi.
So‘ngra yana ikki butun son — \(N\) va \(M \ (1≤N, M≤64)\) kiritiladi. Ular shahar xaritasining qatorlar va ustunlar sonini bildiradi.
Keyingi \(N\) ta qatorda har birining uzunligi \(M\) bo‘lgan shahar xaritasi beriladi. Har bir belgining qiymati # yoki . bo‘ladi.
Loyiha bo'yicha eng kamida bitta bino qurilishi kafolatlanadi.
Yagona butun son — shahar xaritasining nechta turli joyiga loyiha chizmasini qo‘yish mumkinligini chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 3 #.. #.# #.. 5 36 #......#........................#... #.#....#.#...#.........#............ #......#.#...##....#...##......###.. .......#.....#...#.#...##........#.# ...................#.....#.......#.. |
4 |
| 2 |
2 2 #. ## 3 5 #.#.# ##### .###. |
4 |
E. Olma terish
Xotira: 256 MB, Vaqt: 1000 msBog‘da \(N\) ta olma daraxti bo‘lib, ular \(1\) dan \(N\) gachа raqamlangan. Daraxtlar halqa ko‘rinishida joylashgan: ya’ni \(i-\) daraxt \(i+1-\)daraxt bilan \((1 ≤ i ≤ n − 1)\) qo'shni, shuningdek \(N-\) va \(1-\) daraxt ham qo'shnilar hisoblanadi. \(i-\) daraxtdagi mevalar soni \(a_i\) ga teng.
Bog' egasi Shohruh va Azizbekka mevalarni terish vazifasi topshirildi. Shohruh ham Azizbek ham qaysidir daraxtdan mevalarni terishni boshlaydi. Shohruh o'zi tanlagan daraxtdagi mevalarni terib bo'lgach, oldin o'zi mevasini tergan daraxtlariga qo'shni bo'lgan istalgan daraxtni tanlaydi va ularni ham teradi. Istalgan daraxtdagi mevani terish 1 soat vaqt oladi. Xuddi shu qoidalar Azizbek uchun ham amal qiladi. Agar oxirida bitta daraxt qolsa, uni Shohruh teradi. Qaysi daraxtdagi mevani terishni birinchi bo'lib Shohruh tanlasa hamda Shohruh ham, Azizbek ham optimal o'ynasa Shohruh ko'pi bilan qancha olma terishi mumkinligi aniqlang.
Birinchi qatorda musbat butun son \(N \ (2 \le N \le 5000)\) — olma daraxtlari soni beriladi.
Ikkinchi qatorda \(N\) ta butun son \(a_1, a_2, ..., a_n \ (1 \le a_i \le 2000)\) — har bir daraxtdagi mevalar soni kiritiladi.
Yagona satrda Shohruh terishi mumkin bo‘lgan maksimal olmalar sonini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 7 6 8 4 |
13 |
| 2 |
5 1 1 1 1 1 |
3 |