A. O'zga sayyoraliklar

Xotira: 32 MB, Vaqt: 1000 ms

Yerga Dravex va Zepharion sayyorasidan mehmonlar tashrif buyurishdi. Dravex sayyorasidan kelgan mehmonlarning har birida \(X\) ta, Zepharion sayyorasidan kelgan mehmonlarning esa \(Y\) ta oyog'i bor. Mehmonlarning bo'yi juda ham balandligi sababli biz ularning faqatgina oyoqlarini ko'ra olamiz. Hozirda bizni qiziqtirgan narsa,  oyoqlar sonidan kelib chiqib, eng kamida nechta mehmon tashrif buyurganini va har bir sayyoradan nechtadan mehmon kelganini aniqlash.

10 4 6

1 1

103 9 4

11 1

406459 84 49

-1 -1

B. Dogsledding

Xotira: 32 MB, Vaqt: 1000 ms

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.

5

6

10

36

541344693

927417013

C. Chiroyli subsequence lar

Xotira: 32 MB, Vaqt: 1000 ms

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.

5
1
1
2
4
3

2

3
12
33
7

0

D. Domino Festivali

Xotira: 64 MB, Vaqt: 1000 ms

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!

5 3
2 1 -1
1 3 2
0 2 3
2 1 1
3 3 0

16

E. Chiziqlar jangi

Xotira: 32 MB, Vaqt: 1000 ms

Bir kuni Mirzabek va uning do‘sti Sardorbek zerikib, yangi qiziqarli o‘yin o‘ylab topdilar. O‘yinning boshida ular koordinata tekisligida N ta nuqta belgilab olishdi. O‘yin navbat bilan o‘ynaladi va birinchi bo‘lib Mirzabek boshlaydi. U koordinata o‘qlaridan biriga parallel bo‘lgan va belgilangan N ta nuqtadan kamida bittasi orqali o‘tuvchi to'g'ri chiziq chizadi. Keyingi o‘yinchi o‘z navbatida, avvalgi o‘yinchi chizgan chiziq ustida joylashgan nuqtalardan biri orqali yana koordinata o‘qlaridan biriga parallel bo‘lgan yangi chiziq chizadi. Bir chiziqni qayta chizish mumkin emas. O‘z navbatida hech qanday yangi chiziq chiza olmagan o‘yinchi mag‘lub bo‘ladi.

Sizning vazifangiz – optimal strategiya bilan o‘ynalganda, kim g‘olib bo‘lishini aniqlashdir.

3
1 1
1 2
1 3

Mirzabek

4
1 1
1 2
2 1
2 2

Sardorbek