A. Karralilar soni

Xotira: 256 MB, Vaqt: 1000 ms

Dilnoza va Malika matematikada natural sonning karralilari haqida endigina o‘rganishdi. Yangi tushunchani mashq qilish uchun ular quyidagi o‘yinni o‘ynashga qaror qilishdi: har biri bittadan nolga teng bo‘lmagan natural son tanlaydi va berilgan yopiq oraliq uchun (yopiq oraliqlarda chegaralar ham oraliqqa kiradi), tanlangan sonning shu oraliqda nechta karralisi borligini hisoblaydi. Kim tanlagan son berilgan oraliqda ko‘proq karralarga ega bo‘lsa, o‘sha yutadi, yoki karralar soni teng bo‘lsa, durang bo‘ladi.
Sizga ikki qiz tanlagan sonlar hamda berilgan oraliqlarni aniqlovchi sonlar beriladi, sizning vazifangiz o‘yinda kim yutganini va qaysi son yutishga olib kelganini aniqlashdan iborat.

7
9
30
9
60
20

Malika 4

14
140
123456
23
230
153267

Dilnoza 8809

B. Teskari masala

Xotira: 256 MB, Vaqt: 1000 ms

Dasturlashni endi boshlagan o'quvchilar eng birinchi ishlagan masalasi ikki sonning yig'indisini hisoblash bo'lsa kerak. Bu masalada ushbu masalaning teskarisini topish talab qilinadi, ya'ni butun son \(X\) beriladi, shunday \(A\) va \(B\) ni topingki, yig'indisi \(X\) ga teng bo'lsin. Faqat bir shart bor, \(A\) ning ham, \(B\) ning ham absolyut qiymati \([L, R]\) oralig'ida bo'lishi kerak, boshqacha aytganda, \(L \le |A|, |B| \le R\) bo'lsin. 

6
10 2 8
-15 5 10
0 10 20
100 10 20
1 10 20
0 0 10

5 5
-7 -8
15 -15
impossible
11 -10
0 0

C. Gilam

Xotira: 256 MB, Vaqt: 1000 ms

— Buxoroning eng mashhur gilamlari to'rtburchak bo'lib, ularni yoyish ham o'ziga xos san'at.

Ustozning ustaxonasida \( N \times N \) katakdan iborat katta bir gilam yotibdi. Gilamning har bir katakchasiga \( 1 \) dan \( N^2 \) gacha bo'lgan natural sonlar ketma-ket yozilgan: avval qatorlar bo'yicha chapdan o'ngga, yuqoridan pastga tartibda. Ya'ni yuqori chap burchakdagi katak \( 1 \), undan keyingisi \( 2 \), va hokazo.

Masalan, \( N = 4 \) bo'lganda gilam quyidagi ko'rinishda bo'ladi:

\( 1 \quad 2 \quad 3 \quad 4 \)
\( 5 \quad 6 \quad 7 \quad 8 \)
\( 9 \quad 10 \quad 11 \quad 12 \)
\( 13 \quad 14 \quad 15 \quad 16 \)

Usta gilam yoqtirib qolgan bir burchagidan ushlab, uni gorizontal yoki vertikal yo'nalishda tortib olmoqchi. Gilam tortillayotganda tashqi qavat spiralsimon tarzda ichga qarab yig'iladi — xuddi ip g'altagi singari. Natijada barcha katakchalardagi sonlar bitta ketma-ketlik hosil qiladi.

Masalan, \( N = 4 \) bo'lganda:

Yuqori chap burchakdan gorizontal yo'nalishda tortilganda: \( 1 \ 2 \ 3 \ 4 \ 8 \ 12 \ 16 \ 15 \ 14 \ 13 \ 9 \ 5 \ 6 \ 7 \ 11 \ 10 \)

Pastki o'ng burchakdan vertikal yo'nalishda tortilganda: \( 16 \ 12 \ 8 \ 4 \ 3 \ 2 \ 1 \ 5 \ 9 \ 13 \ 14 \ 15 \ 11 \ 7 \ 6 \ 10 \)

Berilgan burchak va yo'nalish bo'yicha gilamni tortishdan hosil bo'lgan sonlar ketma-ketligini toping.

4
1 1
G

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

4
4 4
V

16 12 8 4 3 2 1 5 9 13 14 15 11 7 6 10

3
1 3
V

3 6 9 8 7 4 1 2 5

D. Saralash

Xotira: 256 MB, Vaqt: 1000 ms

Sizda \(n\) ta 1 dan \(n\) gacha sonlar yozilgan kartochkalar bor va ular ustma-ust joylashtirilgan. Bir amalda siz:

• Eng yuqoridagi kartochkani navbatning eng oxiriga qo'yishingiz mumkin yoki navbatdan olib saralangan ketma-ketligingizga qo'shishingiz mumkin.

Minimum nechta amalda bacha elementlarni saralangan ketma-ketligingizga qo'ya olasiz ?
 

7 
7 5 6 3 1 2 4

16

5
5 4 1 3 2

11

E. Javoxir va Yetti

Xotira: 256 MB, Vaqt: 1000 ms

Javoxirning juda maxsus soni bor — bu sonni 7 ga bo'lganda qoldiq 0 bo'ladi. Javoxir bu xususiyat haqida o'ylaganida, u doim: "WOW, bu ajoyib son!" deydi.

Hammaga ma'lumki, Javoxir oddiy uy hayvoni emas — u aqlli va qiziquvchan. Shuning uchun u asl sonni quyidagicha o'zgartiradi: Javoxir sonni ikkilik (binary) ko'rinishda yozadi, so'ngra ikkita indeks tanlaydi va o'sha pozitsiyalardagi bitlarni o'zaro almashtiradi. U bir muddat shu kabi bir necha almashtirish amallarini bajaradi.

Javoxir bajargan almashtirish amallarining umumiy sonini eslamaydi, lekin u ikkilik ko'rinishda qaysi pozitsiyalar biror algaqida almashtirilganini eslab qolgan. Bundan tashqari, u eng muhim bit (most significant bit) hech qachon almashtirilmaganini ham eslaydi.

Endi Javoxir asl sonni tiklashni istaydi, ammo u band — shuning uchun sizdan yordam so'raydi. Javoxirga yordam bera olasizmi?

79
5
0 1 2 4 5

91

21
2
0 3

28

1152921504606846975
5
13 39 40 58 59

1152921504606846975

F. Parity of Power Sum

Xotira: 256 MB, Vaqt: 1000 ms

Sizga ikkita massiv beriladi:

• \(A\) — uzunligi \(N\) bo‘lgan nomanfiy butun sonlar massivi
• \(B\) — uzunligi \(N\) bo‘lgan nomanfiy butun sonlar massivi

Sizning vazifangiz:

\(S=\sum_{i=1}^{N} A_i^{B_i}\)

yig‘indining juft (Even) yoki toq (Odd) ekanligini aniqlash.

3
2 3 4
5 2 1

Odd

1
8
2

Even

G. Musiqa bloklari

Xotira: 256 MB, Vaqt: 2000 ms

Musiqa studiyasida pleylistdagi treklar ustida mashq qilinmoqda. Pleylistda jami \(n\) ta trek bor va ularning balandlik qiymatlari \(a_1, a_2, \ldots, a_n\) ko'rinishida berilgan.

Pleylistni bir nechta ketma-ket bloklarga ajratish kerak. Har bir blok aynan \(2\) ta yoki aynan \(3\) ta trekdan iborat bo'lishi shart. Har bir trek faqat bitta blokka kiradi va bloklar asl tartibni saqlaydi.

Bir blokning noqulayligi shu blok ichidagi eng katta va eng kichik balandliklar ayirmasiga teng, ya'ni agar blokdagi qiymatlar \(b_1, b_2, \ldots, b_k\) bo'lsa, uning noqulayligi

\[\max(b_1, b_2, \ldots, b_k) - \min(b_1, b_2, \ldots, b_k)\]

bo'ladi.

Sizdan barcha bloklar orasidagi eng katta noqulaylikni imkon qadar kichik qilish so'raladi.

Pleylistni talab qilingan tarzda ajratganda olinishi mumkin bo'lgan eng kichik maksimal noqulaylikni toping.

5
8 4 6 10 9

4

6
5 5 5 5 5 5

0

8
3 5 4 9 8 7 1 2

2

H. Qadimiy Bitiklar

Xotira: 256 MB, Vaqt: 1000 ms

Arxeologlar noma'lum qadimiy sivilizatsiyaning yozuv tizimini kashf etishdi. Ko'p yillik tadqiqotlar natijasida ular hayratlanarli xususiyatni aniqladilar: bu tilda so'zning ma'nosi faqat undagi harflar tarkibiga — qaysi harfdan nechtasi borligiga bog'liq, ularning **tartibi esa ahamiyatsiz**. Masalan, `tosh` va `shot` bu tilda aynan bir xil ma'noni anglatadi, chunki ikkalasida ham `t`, `o`, `s`, `h` harflari bittadan ishtirok etadi.

Tadqiqot guruhi yillar davomida \(n\) ta so'zdan iborat lug'at tuzgan. Yaqinda yangi qazilma joydan \(q\) ta noma'lum bitik topildi. Har bir bitik uchun aniqlang: u lug'atdagi biror so'z bilan bir xil ma'noga egami?

3 4
apt
cat
hello
pat
tap
dog
act

Yes
Yes
No
Yes

2 3
abc
xyz
bca
zzz
yxz

Yes
No
Yes

I. Yangi Shahar

Xotira: 256 MB, Vaqt: 1000 ms

Cho'l o'rtasida yangi shahar qurilmoqda. Reja bo'yicha \(n\) ta inshoot qurilishi kerak. Ba'zi inshootlar boshqalariga bog'liq — masalan, suv tarmog'i qurilmagunicha, fontanni o'rnatib bo'lmaydi.

Jami \(m\) ta bog'liqlik berilgan. Har bir bog'liqlik "\(a\) inshoot \(b\) inshoatdan oldin qurilishi shart" degan ma'noni bildiradi. Bog'liqliklar sikl hosil qilmasligi kafolatlangan — ya'ni barcha inshootlarni qurish doimo mumkin.

Bir vaqtda faqat bitta inshoot quriladi. Agar bir nechta inshootning barcha bog'liqliklari bajarilgan bo'lsa, raqami eng kichik bo'lgani birinchi quriladi.

Barcha \(n\) ta inshootni to'g'ri tartibda qurish rejasini tuzing.

4 3
4 1
4 2
4 3

4 1 2 3

5 4
3 1
3 2
5 4
2 4

3 1 2 5 4

J. Kompaniya siri

Xotira: 256 MB, Vaqt: 1000 ms

Sardor katta bir kompaniyaning rahbari bo'lib, u sohadagi yetakchi kompaniya hisoblanadi. Kompaniyaning muvaffaqiyat siri — ichki boshqaruv tizimida. Kompaniyadagi har bir xodimga \(1\) dan \(N\) gacha bo'lgan alohida raqam berilgan bo'lib, har bir xodimning bevosita bo'limi boshlig'i ma'lum (1-raqamli xodim — bu Sardorning o'zi va uning hech qanday boshlig'i yo'q). Xodimlar o'rtasidagi munosabatlar ildizi 1-tugundan boshlanadigan daraxt tuzilmasini hosil qiladi.

Kompaniya xalqaro ko'rgazmaga taklif qilindi. Ko'rgazmada kompaniya ma'lum miqdordagi jamoalar (Sardor tomonidan belgilanadi) bilan qatnashadi, har bir jamoada ikkita xodim bo'ladi. Sardorga jamoalarning soni emas, ularning qiymati muhim. Shu sababli u quyidagi qoidani belgiladi: \(x\) va \(y\) xodimlar jamoani tashkil eta oladi, agar \(x\) — \(y\) ning bevosita rahbari bo'lsa, yoki ikkalasi ham bir xil rahbarga ega bo'lsa. Bunday jamoaning qiymati \(|x - y|\) ga teng. Shuningdek, Sardor (1-raqamli xodim) hech qanday jamoaga kirmaydi — u kompaniya menedjeri sifatida alohida turadi. Jamoalarning umumiy qiymati barcha jamoalar qiymatlarining yig'indisiga teng.

Har bir xodim faqat bitta jamoaga kirishi mumkin.

Shunday jamoalar tarkibini toping-ki, jamoalarning umumiy qiymati maksimal bo'lsin.

5
1
4
2
4

4

K. O'rtacha baho

Xotira: 256 MB, Vaqt: 1000 ms

Asilbek juda mashhur bola, lekin afsuski uning o'qishdagi baholari do'stlari soniga mutanosib emas. Uning do'sti Elbek Asilbekka yordam berishga qaror qildi va sizni dastur yozishga chaqirdi.

Hozirda Asilbekning umumiy o'rtacha bahosi \(N\) ga teng, va u allaqachon \(A\) ta fanga qatnashgan. Asilbek \(B\) ta qo'shimcha fanga qatnashib bo'lgach, umumiy o'rtacha bahosini \(M\) ga yetkazmoqchi. Elbek Asilbekka maqsadga erishish uchun keyingi \(B\) ta fanda qanday o'rtacha baho olishi kerakligini hisoblab berishda yordam bering. Baholash tizimida \(0\) dan past yoki \(10\) dan yuqori baho olish mumkin emas.

3
7 8 1 1
7 9 5 2 
9.05 9.20 28 20

9.00
Impossible
9.41

L. Kichiklar soni

Xotira: 256 MB, Vaqt: 1000 ms

Sizga \(n\) ta butun sondan iborat \(a_1, a_2, \ldots, a_n\) massiv berilgan.

\(i\) indeks "baxtli" deyiladi, agar \(a_i\) massivdagi \(a_i\) dan qat'iy kichik bo'lgan elementlar soniga teng bo'lsa.

Baxtli indekslar sonini toping.

4
0 1 2 3

4

4
1 2 2 3

1

4
3 3 3 3

0

M. Buyruq Zanjiri

Xotira: 256 MB, Vaqt: 1000 ms

Tog' cho'qqisidagi bosh shtabdan tog' etagidagi front chizig'igacha aloqa postlari tarmog'i o'rnatilgan. Postlar tog' yonbag'rida uchburchak shaklidagi ierarxik tuzilmada joylashgan: 

- cho'qqida yagona bosh shtab turadi (\(1\)-post);

- har bir keyingi bosqich (qator) oldingisidan bitta ko'proq postga ega;

- postlar yuqoridan pastga, har bir bosqichda chapdan o'ngga ketma-ket natural sonlar bilan raqamlangan.

Quyida \(5\) bosqichli tarmog' sxemasi keltirilgan:

 Harbiy buyruqlar bosh shtabdan quyidagi tartibda uzatiladi:
- buyruq har doim \(1\)-postdan (bosh shtab) boshlanadi;

- har bir postdan signal faqat keyingi bosqichdagi ikkita qo'shni postdan biriga — chap pastga yoki o'ng pastga — yo'naltiriladi;

- har bir post signalni kuchaytirib uzatadi, kuchaytirish darajasi shu post raqamiga teng. 

Jangning hal qiluvchi lahzasida \(K\)-postga favqulodda buyruq yetkazish lozim. Marshrutni shunday tanlash kerakki, buyruq o'tgan barcha postlar raqamlari yig'indisi eng katta bo'lsin.

Masalan, \(9\)-postga buyruq yetkazishning bir necha yo'li mavjud:

| Marshrut | Yig'indi |

| \(1 \to 3 \to 6 \to 9 | \textbf{19}\) |

| \(1 \to 2 \to 5 \to 9 | 17\) |

| \(1 \to 3 \to 5 \to 9 | 18\) |

Ko'rinib turibdiki, \(1 \to 3 \to 6 \to 9\) marshruti eng katta yig'indini beradi.

9

19

N. Tank va ta’minot ombori

Xotira: 256 MB, Vaqt: 1000 ms

Harbiy bazada jangovar tanklar uchun ehtiyot qismlar saqlanadigan uzun ombor bor. Har bir ehtiyot qismning o'z xizmat muddati bor: u qancha katta bo'lsa, shuncha ko'p yurishga yaroqli hisoblanadi.

Tanklar uzoq masofalarga chiqishdan oldin texnik xizmat ko'rish punktiga kiradi. Bu yerda mexanik askar tank uchun kerakli ehtiyot qismlarni ombordan olib keladi. Ayrim ehtiyot qismlar ishlatilgan bo'lsa, ularning xizmat muddati kamayadi. Shu sababli tank uchun mos bo'lgan qismlarni to'g'ri tanlash juda muhim.

Ombordagi ehtiyot qismlar bitta qatorda joylashgan: 1-qism 1-pozitsiyada, 2-qism 2-pozitsiyada va hokazo.

Mexanik:

• bir vaqtning o'zida faqat 1 ta ehtiyot qismni ko'tara oladi;
• bir sekundda 1 pozitsiya yuradi;
• barcha ishlar omborning 0-pozitsiyasida boshlanadi va tugaydi.

2 ta qismni olib kelish uchun ketadigan vaqt:

                     \(𝑡𝑖𝑚𝑒=2×(𝑝1+𝑝2)\)

bu yerda \(p_1\)​ va \(p_2\)​ — tanlangan qismlarning pozitsiyalari.

Bazadagi ta'minot bo'limi boshlig'i mexanikdan ikki xil topshiriq bo'yicha javob so'raydi:

• Savol topshirig'i (t=0): berilgan l qiymat uchun xizmat muddati kamida l bo'lgan 2 ta ehtiyot qismni ombordan olib kelish uchun eng kam necha soniya kerakligini aniqlash. Eng kam vaqt uchun xizmat muddati yetarli bo'lgan eng chapdagi 2 ta qism tanlanadi.
• Buyruq topshirig'i (t=1): xizmat muddati kamida 𝑙 bo'lgan eng chapdagi 2 ta ehtiyot qismni olib kelish, ularning asl xizmat muddatlarini chiqarish, so'ng har birining xizmat muddatini l ga kamaytirish.

Savol topshirig'ida qismlar o'zgarmaydi. Buyruq topshirig'ida esa tanlangan qismlarning xizmat muddati l ga kamayadi va ular keyingi topshiriqlar uchun yangilangan holda qaytariladi.

6 4
15 30 10 25 5 20
0 20
1 10
1 15
0 15

12
6 15 30
12 20 25
-1

O. Muntazam uchburchak

Xotira: 256 MB, Vaqt: 1000 ms

Muntazam uchuburchak bu - hamma tomonlari va burchaklari bir xil bo'lgan uchburchakdir.
Sizga uzunligi 1 ga teng bo'lgan \(n\) ta muntazam uchburchak berilgan. 
Siz berilgan uchburchaklarni birlashtirish orqali nechta turli xil qavariq ko'pburchak yasash mumkinligini topishingiz kerak ? 
Shakllar aylantirilsa yoki akslantirilsa ham bir xil hisoblanadi.

16

5