A. Yoshga bog'liq kasalliklar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Shifokor olimlar yoshga bog'liq kasalliklar ustida ilmiy tadqiqotlar olib borishdi, hamda bu tadqiqotlar natijasida yoshga bog'liq kasalliklar quyidagi 4 guruhga bo'linishini aniqlashdi:

0-18 yosh oralig'idagi kasalliklar

19-35 yosh oralig'idagi kasalliklar

36-60 yosh oralig'idagi kasalliklar

61 va undan yuqori yoshdagi kasalliklar

Yoshga bog'liq kasalliklarni davolaydigan shifoxonada N ta be'mor bor, ularning har birini yoshi sizga beriladi. Sizning vazifangiz har bir guruhga tegishli be'morlar sonini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida bitta butun son, $N(1 \le N \le 100)$ - be'morlar soni kiritiladi.

Keyingi satrda $N$ ta $[0, 130]$ oralig'idagi butun son, be'morlarning yoshlari bo'sh joy bilan ajratilgan holda kiritiladi.

Chiquvchi ma'lumotlar:

Yagona satrda 4 ta butun son, har bir guruhga tegishli bo'lgan be'morlar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 0 5 10 15 20 25 30 50 70 90	4 3 1 2

B. Tanaffus

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Maktab hovlisida tanaffus paytida bolalar o'yin o'ynamoqda. O'yin quyidagicha tashkil etilgan:

O'yin cheksiz koordinatalar sistemasida bo'ladi.
Har bir bola o'ziga xos koordinatada joylashgan.
Bayroqlar ham koordinatalarda joylashgan bo'lib, har bir bayroqda raqam yozilgan (1 dan N gacha).
O'qituvchi "start" deganida, har bir bola o'ziga eng yaqin bayroq tomon yuguradi.
Agar bir nechta bayroq masofa jihatdan eng yaqin bo‘lsa, bola raqami kichik bo‘lgan bayroqni tanlaydi.
Masofa Manhattan masofasi bo‘yicha aniqlanadi:
$\text{dist} = |x_i - X_j| + |y_i - Y_j|$

Har bir bolaning qaysi bayroq tomon yugurishini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda $M$ (bolalar soni) va $N$ (bayroqlar soni) kiritiladi.
Keyingi $M$ qator — har bir bolaning koordinatasi: $X_j$ va $Y_j$ beriladi.

Keyingi $N$ qator — har bir bayroqning koordinatasi: $x_i$ va $y_i$ beriladi.

$1 \le N, M \le 100$

$|x|, |y|, |X|, |Y| \le 10^8$

Chiquvchi ma'lumotlar:

Har bir bola uchun alohida qatorda — u tanlagan bayroqning raqamini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4 10 10 -10 -10 3 3 1 2 2 3 3 5 3 4	3 1 2
2	2 2 2 0 0 0 -1 0 1 0	2 1

C. G'alati musobaqa

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Robolandiya Sport Dasturlash federatsiyasi yangi turdagi musobaqa tashkil etmoqda. Musobaqaning hayratlanarli tarafi masalalar o'quvchilarning bilimidan kelib chiqib tuzilgan, aniqroq aytganda har bir ishtirokchi aynan $a_i$ masalani ishlay oladi va boshqa hech qaysi ishtirokchi u ishlay oladigan masalani ishlay olmaydi. Ushbu musobaqa 2 ta ishtirokchidan iborat guruhlar orasida bo'lib o'tadi. Quvonarlisi, hozirda ro'yxatdan o'tgan ishtirokchilar soni juft, ya'ni istalgan ishtirokchi musobaqada qatnasha oladi. Musobaqa jarayonida juda past natija ko'rsatgan jamoalar federatsiya obro'siga zarar yetkazishi mumkin. Shu sababdan federatsiya ishtirokchilarni o'zlari guruhlab chiqishga qaror qildi. Shunda har bir jamoa eng kamida $X$ ta masala ishlaydi. Siz shu $X$ ning eng katta qiymatini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun juft son $N \ (2 \le N \le 10^6)$ - ishtirokchilar soni kiritiladi.

Keyingi qatorda $N$ ta butun son $a_i \ (1 \le a_i \le 10^9)$ - har bir ishtirokchi ishlay oladigan masalalar soni beriladi.

Chiquvchi ma'lumotlar:

Har bir jamoa ishlagan masalalar soni kamida $X$ bo'lishi mumkin bo'lgan maksimal qiymatni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 1 2 3 5	5
2	2 18 16	34

D. Chiroyli subsequence lar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Shohruh quyidagi massivni chiroyli deb ataydi:

massivning uzunligi kamida 2 ga teng;
massiv quyidagi ikki holatning biriga mos tushadi:
- massivdagi har bir element (birinchi elementdan tashqari) o'zidan oldingi elementdan katta emas; (non-increasing)
- massivdagi har bir element (birinchi elementdan tashqari) o'zidan oldingi elementdan kichik emas; (non-decreasing)

$N$ uzunlikdagi butun sonlardan tashkil topgan $A$ massivi berilgan. Shohruh ushbu massivni bir nechta subsequence* larga ajratishi kerak:

Har bir subsequnce chiroyli bo'lishi kerak;
$A$ ning har bir elementi aynan 1 ta subsequence ichida bo'lishi kerak;

Shohruh eng kamida nechta subsequence yaratishi kerakligini aniqlang.

Subsequence — bu massivdan ba’zi elementlarni (ehtimol 0 ta) olib tashlab, qolganlarini tartibini o‘zgartirmasdan tuzilgan yangi massivdir.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son $N \ (1 \le N \le 25)$ - massiv uzunligi kiritiladi.

Keyingi $N$ ta qatorda $A_i \ (1 \le A_i \le 100)$ - massiv elementlari beriladi.

Chiquvchi ma'lumotlar:

Barcha shartlarga javob berish uchun yaratilishi kerak bo'lgan minimal subsequence lar sonini chop eting. Agar shartni bajarish imkonsiz bo'lsa 0 ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 1 2 4 3	2
2	3 12 33 7	0

E. Geometrik san'at

Xotira: 32 MB, Vaqt: 1000 ms

Masala

San'atkor Komil geometrik san'at ko‘rgazmasiga tayyorgarlik ko‘ryapti. U tekislikda N ta chiziq chizdi, har bir chiziq $A_ix +B_iy+C_i=0$ ko‘rinishida ifodalangan. Komil ko‘rgazmasida faqat uchburchak shakllarni namoyish qilishni rejalashtirgan. Uning chizgan barcha uchburchaklari aynan mana shu N ta chiziq orqali hosil qilinishi kerak.

Sizning vazifangiz – Komil chizgan chiziqlar orasidan uchta chiziqni tanlab uchburchak hosil qilish mumkin bo'lgan usullar sonini aniqlashdan iborat. Natija juda katta bo‘lishi mumkinligi sababli, javobni $10^9+7$ ga bo‘lgandagi qoldiq ko‘rinishida chiqaring.

Muhim eslatma: Uch yoki undan ortiq chiziq bitta nuqtada kesishmasligi kafolatlanadi!.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son $N (1\le N\le 3 * 10^5)$ – chiziqlar soni beriladi. Keyingi N ta qatordan har birida $A_i$ , $B_i$ va $C_i$ butun sonlari beriladi (har bir sonning mutlaq qiymati $10^9$ dan kichik bo‘ladi).

Chiquvchi ma'lumotlar:

Yagona qatorda talab qilingan uchburchaklar sonini $10^9+7$ ga bo‘lingandagi qoldiq ko‘rinishida chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 0 1 0 -5 3 0 -5 -2 25 0 1 -3 0 1 -2 -4 -5 29	10
2	5 -5 3 0 -5 -3 -30 0 1 0 3 7 35 1 -2 -1	10