A. Unli harflar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Ingliz alifbosi 26 ta harfdan iborat. Ulardan beshtasi (a, e, i, o va u) unli harflar hisoblanadi, qolgan 21 tasi esa undosh harflardir. Deyarli har bir inglizcha so'zda hech bo'lmaganda bitta unli harf bo'ladi (masalan, "rhythm" so'zi kamdan-kam istisnolardan biridir).

Ushbu masalada sizga ingliz matnidan bir bo‘lak beriladi. Sizning vazifangiz ushbu matnda uchragan har bir unli harfning chastotasini (qanchalik ko‘p uchraganligini) aniqlash va natijalarni chastotaga ko‘ra kamayish tartibida chiqarishdir. Agar ikkita unli harf bir xil miqdorda uchrasa, ular alifbo tartibida chiqariladi.

Quyidagi misollardan ko‘rinib turibdiki, katta va kichik harflar bir xil harf hisoblanadi. Chiqishda faqat kichik harflardan foydalaning. Ikkinchi misoldan ko‘rinib turganidek, chastotasi nolga teng bo‘lgan unli harflar ham chiqarilishi kerak.

Kiruvchi ma'lumotlar:

Yagona qatorda shartda aytilgan satr kiritiladi. Satr uzunligi 500 dan oshmaydi. Kiritilgan balcha belgilar ASCII belgilaridan tashkil topgan.

Chiquvchi ma'lumotlar:

Chiqishda har bir unli harf kichik harf bilan yoziladi, so‘ngra ikki nuqta (:) va keyin o‘sha harf chastotasi yoziladi. Har bir unli harf va uning chastotasi orasida bitta bo‘sh joy bo‘lishi kerak.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	Salom, dunyo!	o:2 a:1 u:1 e:0 i:0
2	C++ – C tiliga asoslangan dasturlash tili boʻlib, C ham oʻz navbatida B va BCPL tillaridan kelib chiqqan. BCPL 1967-yilda Martin Richards tomonidan tuzilgan va operatsion sistemalarni yozish uchun moʻljallangan edi.	a:26 i:20 o:9 e:4 u:4

#

INPUT.TXT

OUTPUT.TXT

1

Salom, dunyo!

o:2 a:1 u:1 e:0 i:0

2

C++ – C tiliga asoslangan dasturlash tili boʻlib, C ham oʻz navbatida B va BCPL tillaridan kelib chiqqan. BCPL 1967-yilda Martin Richards tomonidan tuzilgan va operatsion sistemalarni yozish uchun moʻljallangan edi.

a:26 i:20 o:9 e:4 u:4

B. Shohruh matematika darsida

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Shohruh endigina 3-sinfga o‘tdi. Hozirda u nafaqat qo‘shish va ko‘paytirish, balki ayirish hamda bo‘lish amallarini ham o‘rganmoqda. Matematika o‘qituvchisi O‘g‘iloy opa Shohruhga uyga topshiriq berdi. Vazifa shundan iboratki: u bitta son \(X\) ni 1 dan 100 gacha oraliqdan tanlaydi va shu son ustida ketma-ket amallarni bajaradi.

Ammo Shohruh manfiy sonlar va kasrlar bilan ishlay olmaydi. Shuning uchun:

Agar biron-bir amal natijasida hosil bo‘lgan qiymat manfiy son bo‘lsa, yoki
bo‘lish natijasi butun son bo‘lmasa — Shohruh bu \(X\) soni ustida amallarni bajarishni davom ettirmaydi.

Sizdan talab etiladi: 1 dan 100 gacha bo‘lgan qaysi sonlarni tanlasa, Shohruh barcha amallarni muvaffaqiyatli bajara oladi? Ularning umumiy sonini aniqlang.

Kiruvchi ma'lumotlar:

Dastlabki qatorda bitta butun son \(N \ (1 \le N \le 10)\) - amallar soni kiritiladi.

Keyingi \(N\) ta qatorda amal turi hamda uning qiymati beriladi, kiritilgan sonlar natural va qiymati 5 dan oshmaydi.

Amallar: ADD (qo'shish), SUBTRACT (ayirish), MULTIPLY (ko'paytirish) va DIVIDE (bo'lish).

Chiquvchi ma'lumotlar:

Bitta qatorda 1 dan 100 gacha bo'lgan nechta sonni tanlash mumkinligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 ADD 1 SUBTRACT 10	92
2	2 MULTIPLY 2 SUBTRACT 2	100

C. Dogsledding

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Ushbu rasmdagi sport dogsledding deb ataladi va u Kanadada juda keng tarqalgan. Bu sport turida chanaga bir nechta itlar bog'lanadi va birinchi bo'lib marraga yetib kelgan ishtirokchi g'olib hisoblanadi. Rasmda ko'rinib turganidek, itlar bir nechta qator bo'lib joylashtirilgan hamda har bir qatorda bir nechtadan itlar bor. Bunda itlarning umumiy kuchi qatorlardagi itlar sonining ko'paytmasiga teng: misol uchun 10 ta it bor va ular 4 - 2 - 3 - 1 ko'rinishida joylashtirilgan bo'lsa, ularning umumiy kuchi \(4 \times 2 \times 3 \times 1 = 24\) ga teng. Shunisi aniqki, eng katta kuchga ega ishtirokchi g'alaba qozonish ehtimoli juda ham yuqori. Siz ham bu musobaqada ishtirok etyapsiz, sizda \(N\) ta it bor va musobaqada g'olib bo'lmoqchisiz. Itlarni bir nechta qatorga bo‘lish orqali maksimal umumiy kuchni toping.

Kiruvchi ma'lumotlar:

Yagona qatorda bitta butun son \(N \ (1 < N \le 10^9)\) - qo'l ostingizdagi itlar soni kiritiladi.

Chiquvchi ma'lumotlar:

Maksimal umumiy kuchni chop eting. Javob juda ham katta bo'lib ketishi mumkin, shuning uchun javobni \(10^9+7\) ga bo'lgandagi qoldig'ini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5	6
2	10	36
3	541344693	927417013

D. Domino Festivali

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Davron shahrida har yilgi Domino festivali bo‘lib o‘tmoqda. Festivalda shahar markazida joylashgan maxsus domino maydoni mavjud. Bu maydon N qator va aynan 3 ustundan iborat. Har bir katakda festival tashkilotchilari tomonidan turli xil qiymatli ballar yozilgan.

Mirjalol ushbu festivalda ishtirok etmoqda va uning ixtiyorida aynan K dona domino mavjud. Har bir domino o‘lchami 2x1 bo‘lib, Mirjalol ularni xohlagancha burib yoki aylantirib joylashtirishi mumkin. Uning maqsadi, domino kataklari bilan qoplagan maydonidagi sonlar yig‘indisini imkon qadar maksimal qilishdir.

Mirjalolga aynan K ta dominodan foydalanib, hech qanday bir-birini ustiga chiqmagan holda, maksimal ballarni yig‘ishga yordam bering!

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(N(1\le N\le 10^3)\) – maydonning qatorlari soni va \(K(1\le K\le 10^3)\) – domino toshlari soni beriladi. Keyingi N ta qatorda uchtadan butun son yozilgan bo‘ladi. Bu sonlar maydonning tegishli kataklaridagi ballarni ifodalaydi. Har bir sonning absolyut qiymati \(10^6\) dan kichik bo‘ladi.

Chiquvchi ma'lumotlar:

Bitta son chiqariladi – aynan \(K\) ta dominodan foydalanib olinishi mumkin bo‘lgan maksimal ballar yig‘indisi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 2 1 -1 1 3 2 0 2 3 2 1 1 3 3 0	16

E. Tovuqlar fermasi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Fermada \(N\) ta tovuq mavjud va ular bir chiziqdagi kataklarga joylashtirilgan, bunda \(i-\) tovuq \(i-\) katakda yashaydi. Tovuqlar noyob va ular vaqti-vaqti bilan noyob "oltin tuxum" qo'yadi. Tovuqxona egasi hech qaysi tuxumga ziyon yetishini xohlamaydi, shuning uchun u mini-robotlar sotib olishga qaror qildi. Robot tovuq tuxum qo'ygan zahoti uni ehtiyotkorlik bilan tutib oladi hamda avaylab savatga joylashtiradi. Mini-robot har sekundda ko'pi bilan 1 katak yura oladi. Robot narxi juda qimmat, shuning uchun fermer imkon qadar kamroq robot yordamida barcha tuxumlarni yig‘ib olishni xohlaydi.

Biz har bir tovuq qachon tuxum qo'yishini bilamiz: \(s_i-\)katakdagi tovuq, \(t_i-\)sekundda oltin tuxum qo'yadi. Robotlarning dastlabki joylashuvini erkin belgilagan holda, barcha tuxumlarni tutib olish uchun kamida nechta robot kerak bo‘lishini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N \ (1 \le N \le 200 \ 000)\) — tuxumlar soni kiritiladi.

Keyingi \(N\) qatorda har bir tuxum uchun ikkita son: \(s_i\) va \(t_i\) \( (1 \le s_i, t_i \le 10^9)\).

Har bir tovuq bir vaqtda ko'pi bilan bitta tuxum qo'ya oladi, aniqroq aytganda barcha \(i \neq j\) uchun \(s_i \neq s_j\) yoki \(t_i \neq t_j\) ekanligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Yagona qatorda — kerakli minimal robotlar soni \(w\) ni chop eting.

Misollar:

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