A. Boshliqlik sindromi

Xotira: 32 MB, Vaqt: 1000 ms

Robolandiyada bir tashkilot bor. U tashkilotning ofislari n × m o‘lchamli jadval shaklida joylashgan bo'lib, har bir ofisning ichki devori quyidagi ranglardan biri bilan bo‘yalgan:

• A → Amethyst (binafsha)
• B → Beige (Sarg'ish)
• C → Coral (Marjonrang)
• D → Denim (jeans ko‘ki)

Ofislarning har biri to‘rt tomondan qo‘shnilari bilan eshik orqali tutashgan (chap, o‘ng, yuqori, past).

Yaqinda bu tashkilotga yangi rahbar tayinlandi. Unda “boshliqlik sindromi” bor:

• U qaysi ofisga kirsa ham, albatta kamchilik topadi va devorlarni boshqa rangga bo‘yashni buyuradi. Ya’ni, har bir ofisning rangi o‘zgarishi kerak va yangi rang eski rangdan farq qilishi shart.
• Bundan tashqari, rahbarning yana bir qat’iy talabi bor: qo‘shni ikki ofisning rangi bir xil bo‘lishi mumkin emas.

Sizning vazifangiz

Ofislarning ranglarini qayta tanlang:

• Qayta tanlangan rang A, B, C yoki D bo'lishi kerak.
• Har bir ofisning yangi rangi eski rangidan farq qilishi kerak.
• Yonma-yon (qo'shni) ofislarning ranglari bir xil bo‘lmasligi kerak.

4 4
ADAD
DDDD
DDBC
AACD

CBDC
ACBA
BACD
DBAC

B. Passportlar

Xotira: 128 MB, Vaqt: 2000 ms

Robolandiya mamlakatida \(N\) ta shahar mavjud. Shaharlar orasida \(N-1\) ta ikki yo‘nalishli yo‘l qurilgan. Bu yo‘llar shunday ulangan-ki, har qanday shahardan boshqasiga bevosita yoki bir nechta shaharlar orqali borish mumkin (ya’ni, graf daraxt shaklida).

Har bir yo‘l ikki shaharning orasini bog‘laydi va uning ustida \(W_{i}\) soni yozilgan. Qo‘shni shaharlar deb, orasida bevosita yo‘l mavjud bo‘lgan shaharlar juftligiga aytamiz. Agar kimdir bir shahardan uning qo‘shnisiga o‘tmoqchi bo‘lsa, uning pasport kuchi kamida shu yo‘l qiymatiga (\(W_{i}\)) teng bo‘lishi kerak. Kuch qiymati \(w\) bo‘lgan pasport aynan \(w\) tangaga tushadi.

Shunday qilib, ikki shahar \(a\) va \(b\) orasida sayohat qilish uchun pasport kuchi marshrutdagi eng katta \(W_{i}\) qiymatiga teng bo‘lishi kifoya. Ya’ni, siz tanlagan yo‘ldagi yo‘llar orasidagi maksimal qiymatni qoplash zarur.

Sizning vazifangiz: barcha juftliklar uchun \((1 \le i < j \le N)\) sayohat qilish uchun zarur bo‘lgan minimal pasport narxini hisoblang va ularning yig‘indisini toping.

4
1 2 5
2 3 1
2 4 2

20

C. Renessansdagi birinchi kun

Xotira: 32 MB, Vaqt: 1000 ms

Renessans oromgohiga kelgandan keyin Nurbaxsh va Husanboy do'konga chiqib ichimlik olib kelishga qaror qilishdi.

Ular borgan do'konda \(n\) xil gazli va \(m\) xil gazsiz ichimlik bor ekan. Nurbaxsh va Husanboy bittadan ichimlik olishmoqchi. Ularni qiziqtirgan savol: Ular necha xil usulda do'kondan har biri bittadan (jami bo'lib 2 ta) ichimlik  olishlari mumkin?

Ularga bu savolga javob topishga yordam bering.

1 1

4

D. AYOQSH

Xotira: 32 MB, Vaqt: 1000 ms

Ikrom uzunligi \(10^9\) km dan iborat bo'lgan yo'lning \(D\) - kmligida yashaydi. Bu yo'lning har \(A\) km ligida (ya'ni, 0, A, 2A, 3A, ...) Ibr ga tegishli AYOQSH mavjud, har \(B\) km ligida Carvon ga tegishli AYOQSH mavjud, hamda har \(C\) km ligida DipOil ga tegishli AYOQSH mavjud.

Eslatma: Bir nuqtada bir nechta turdagi AYOQSH lar bo'lishi mumkin, masalan 0-kmlikda barcha turdagi, ya'ni Ibr, Carvon va DipOil ga tegishli AYOQSH lar bor.

Ikrom o'zining avtomobiliga yoqilg'i quyish uchun uyidan chiqdi, hamda uyiga eng yaqin masofada joylashgan AYOQSH ga borishga qaror qildi. Agar eng yaqin joylashgan AYOQSH lar soni 1 tadan ko'p bo'lsa Ikrom qaysi AYOQSH ga borishni tanlashda qiynalib qoladi. 

Ikromga eng yaqinda joylashgan AYOQSH gacha bo'lgan masofani topishda yordam bering. Agar eng yaqin joylashgan AYOQSH lar soni bittadan ko'p bo'lsa Ikromga "Istaganingizni tanlashingiz mumkin!" degan xabarni yetkazing.

2
5 14 11 29
23 10 21 35

1 Istaganingizni tanlashingiz mumkin!
5

E. Nurlar soni

Xotira: 64 MB, Vaqt: 2000 ms

Nyuboy matematikani o'rganishni boshladi, u koordinatalar sistemasiga juda qiziqadi. U koordinatalar sistemasida nuqtalardan foydalanib kvadrat yasashni yoqtiradi. Nyuboy o'lchami  \(N \times N\) bo'lgan kvadrat yasamoqchi bo'lsa, \(0\le x \le N\) va \(0\le y \le N\)shartni qanoatlantiradigan barcha butun koordinatalarga nuqta qo'yib chiqadi. 

Nyuboy bugun matematika darsida “Nur” bilan tanishdi. 

Nur - bir tomoni chegaralangan va ikkinchi tomoni cheksiz ketuvchi geometrik shakl. 

Nyuboy boshlanish nuqtasi  \((0,0)\) da joylashgan hamda yo'nalishi o'zi yasagan \(N \times N\) o'lchamli kvadratning \((0,0)\) nuqtasidan tashqari har bir nuqtasiga qaratilgan Nurlar chiza boshladi, bunda u bir Nur ni takroran chizmaydi. 

Nyuboy barcha Nurlarni chizib bo'lgach, u yerda jami nechta Nur chizilganligiga qiziqib qoldi. \(N\) ning kichik qiymatlari uchun buni aniqlash Nyuboyga qiyinchilik tug'dirmaydi, ammo \(N\) ning katta qiymatlarida natijani aniqlash uchun Nyuboydan juda ko'p vaqt talab qilinadi. Shu sababli Nyuboy siz dasturchilardan yordam so'ramoqchi. U sizga o'zi yasagan kvadratning tomon uzunligi \(N\) ni aytadi, siz esa unga nechta Nur o'tkazish mumkinligini aytishingiz kerak. 

4

13

1

3

F. Raqamli pechenyelar

Xotira: 32 MB, Vaqt: 1000 ms

Azizbek sehrli raqam-pechenyelarni bir-biriga ulab, ulardan bir katta butun son yasadi. Endi u ushbu son ustida quyidagicha o‘yin o‘ynaydi:

• Har qadamda aniq bitta raqamni (istalgan joydan) o‘chirib tashlaydi.
• O‘chirilgan raqamdan so‘ng qolgan raqamlar bir-biriga yopishib, tartibi saqlanadi.
• Agar raqamlarning boshida nol(lar) paydo bo‘lsa, ularni birdan olib tashlaydi (ya’ni, oldinda nol raqami qolmaydi).
• Har safar yangi hosil bo‘lgan son tub son bo‘lsa, o‘yin davom etadi. Agar tub bo‘lmasa, o‘yin shu zahoti to‘xtaydi.

Boshlang‘ich son ham hisobga olinadi: agar tub bo‘lsa, o‘zi ham birinchi holat sifatida qabul qilinadi.

Shunday tartibda raqamlarni o‘chirish ketma-ketligini eng zo‘r tanlab, Azizbek eng ko‘p necha marta tub son bilan uchrashishi mumkinligini (boshlang‘ich holat ham qo‘shiladi) aniqlang.

Sizning vazifangiz: Berilgan son \(N\) uchun yuqoridagi o‘yinda raqamlarni qanday ketma-ketlikda o‘chirish mumkinligi ichida, ketma-ket tub sonlar maksimal sonini chiqaring.

11

1

2

1

773

3

300007

2

15

0

G. Sheldonning sevimli o‘yini

Xotira: 32 MB, Vaqt: 1000 ms

Eslatma: O'yinning asl nomi “Rock, Paper, Scissors, Lizard, Spock”, bu o'yin The Big Bang Theory ko'rsatuvi yordamida Sheldon tomonidan ommalashtirilgan bo'lganligi sababli uni Sheldon's game deb atashadi.

Husanboy va Nurbaxsh "Umumiy o'rta ta'lim tashkilotlarida faoliyat ko'rsatayotgan informatika va axborot texnologiyalari fani o'qituvchilari o'rtasida Respublika olimpiadasi"ning final bosqichiga hakamlik qilish uchun lagerga kelishdi.

Musobaqaning 1-kuni ishtirokchilar uchun juda qiziqarli bo'ldi, chunki ular bir-biridan qiziqarli bo'lgan masalalar ishlashdi. Husanboy va Nurbaxsh musobaqada ishtirok etmagan bo'lsada musobaqaning birinchi kuni ular uchun ham qiziqarli bo'ldi. Bunga sabab Husanboy va Nurbaxsh vaqtlarini qiziqarli o‘tkazish uchun “Rock, Paper, Scissors, Lizard, Spock” o‘yinini o‘ynashga qaror qilishdi.

O‘yin quyidagi qoidalarga ega:

• Scissors kesadi Paperni
• Paper qoplaydi Rockni
• Rock ezadi Lizardni
• Lizard zaharlaydi Spockni
• Spock sindiradi Scissorsni
• Scissors chopib tashlaydi Lizardni
• Lizard yeydi Paperni
• Paper rad etadi Spockni
• Spock bug‘laydi Rockni
• Rock sindiradi Scissorsni

Har bir raundda Husanboy va Nurbaxsh bittadan belgi tanlaydi. Agar Husanboyning belgisi Nurbaxshniki ustidan g‘alaba qozonsa, bu raundni Husanboy yutadi. Agar Nurbaxshning belgisi Husanboyniki ustidan g‘alaba qozonsa, bu raundni Nurbaxsh yutadi. Agar ikkovi bir xil belgi tanlasa, bu raund natijasi durang bo‘ladi.

Sizga Husanboy va Nurbaxsh jami necha marotaba o'yin o'ynaganligi soni \(N\) va har bir raunddagi ikkala o‘yinchining tanlovi beriladi.

Sizning vazifangiz quyidagilarni aniqlash:

• Husanboy nechta g‘alaba qozondi?
• Nurbaxsh nechta g‘alaba qozondi?
• O'yin natijasi necha marotaba durang bo‘ldi?

5
R S
L K
K R
P P
L S

3 1 1

H. Jozibali subsequence

Xotira: 128 MB, Vaqt: 1000 ms

Sizga uzunligi \(N\) ga teng bo'lgan, butun sonlardan iborat \(A\) massiv berilgan. Sizning vazifangiz massivdagi jozibali subsequencelar sonini sanashdan iborat.

Subsequence - massivdan 0 yoki bir nechta elementni o'chirishdan hosib bo'ladigan ketma-ketlik. 

Masalan [2,1,3] ketma-ketlikda 8 ta har xil subsequence bor, bular: [], [2], [1], [3], [2,1], [2,3], [1,3], [2,1,3]. 

Massivning turli o'rinlaridagi elementlarni o'chirishdan hosil bo'ladigan subsequence lar turlicha subsequence hisoblanadi. Masalan [2,2,3] ketma ketlikda ham 8 ta har xil subsequence bor, bular: [], [2] (2-element), [2] (3-element), [3], [2,2], [2,3](1 va 3 - element), [2,3] (2 va 3-element) , [2,2,3]

 

Jozibali subsequence - quyidagi shartlarning barchasini qanoatlantiradigan subsequence ga aytiladi:

• Elementlar soni kamida 2 ta bo'lgan subsequence;
• Elementlari qiymati bo'yicha aynan o'sish tartibida joylashgan subsequence;
• Ketma-ket kelgan ixtiyoriy 2 elementi orasidagi farq juft son bo'lgan subsequence.

10
20 6 18 10 4 20 10 18 4 2

17

10
4 3 7 5 2 4 5 7 2 1

9

I. Mukofotlar

Xotira: 32 MB, Vaqt: 1000 ms

Fan olimpiadalari markazi (FOM) nihoyat "O'qituvchilar Olimpiadasi"ni o'tkazdi! Ustozlarimiz bilimda kuch sinashib, butun Respublika bo'ylab eng zo'r o'qituvchi nomiga loyiq bo'lishdi. Hamma ishtirokchilar natijalarini intiqlik bilan kutmoqda, sababi FOM barcha qatnashchilarga alohida pul mukofoti tayyorladi! Lekin, albatta, buni ham ajoyib va adolatli tarzda amalga oshirish rejalangan:

• FOM dagi pul kupyuralari faqat \(K^0, K^1, K^2, ..., K^{\infty}\) ko'rinishida (ya'ni, K ning nomanfiy butun darajalari).
• Ustozlar bir xil qiymatdagi kupyuradan ko'pi bilan bittadan olishi mumkin va har bir ustoz hech bo'lmaganda bitta kupyura bilan taqdirlanadi.
• Eng oxirgi oʻrindagi ustoz, yaʼni \(N\)-oʻrin egalari, yuqoridagi cheklovlar asosida to'lash mumkin bo'lgan eng kichik miqdordagi mukofotni oladi. \((N-1)\)-o'rin sohibi esa undan keyingi eng kichik mukofotni, va hokazo. \(i\)-o‘rindagi ustoz \(N-i+1\)-eng kichik mukofotga ega bo‘ladi, boshqacha so'zlar bilan aytganda, eng kichik mukofot — oxirgi o‘ringa, eng katta mukofot esa 1-o‘ringa beriladi..

Misol uchun, agar \(N = 5, K = 3\) bo‘lsa:

Eng kichik hosil qilib bo‘ladigan mukofotlar: \([1, 3, 4, 9, 10]\). Demak, 1-o‘rin uchun 10 so‘m, 2-o‘rin uchun 9 so‘m, va hokazo!

Endi har bir ustoz o'z o'rnini biladi va mukofot miqdorini ham bilishni xohlaydi. Ularning hayajonini kutarib, siz tashkilotchi sifatida qo'lga kiritgan mukofotlarni aniqlab, ularga xursandchilik ulashing!

5 3 4
1
2
3
5

10
9
4
1

10 4 5
4 
7
1
10
3

21
16
68
1
64

J. Dekart o'yini

Xotira: 32 MB, Vaqt: 1000 ms

Husanboy bilan Shohruh aqliy raqobat qiladigan standart o'yinlarning barchasini birgalikda juda ko'plab marotaba o'ynashgan. Shu sababli ular standart o'yinlardan zerikib qolishdi va o'zlarining aqliy raqobat qiladigan dekart o'yini nomli o'yinlarini o'ylab topishdi. 

O'yin quyidagicha izohlanadi: 

• O'yin ikki o'yinchi orasida o'ynaladi;
• O'yinda amal bajarishni birinchi o'yinchi (\(A\)) boshlab beradi, ikkinchi o'yinchi (\(B\)) davom ettiradi, va shu tariqa o'yinda amal bajarish navbati almashib kelaveradi. Ya'ni \(A \rightarrow B \rightarrow A \rightarrow B \rightarrow A \rightarrow ...\) ketma-ketligida;
• O'yin davomida o'yinchilarda dekart koordinatalar sistemasida joylashgan bitta o'yin toshi mavjud bo'lib bu o'yin toshining dastlabki joylashuv koordinatasi  \((x_0,y_0)\) ekanligi ma'lum. Bu yerda \(x_0\) va \(y_0\) natural sonlar;
• Har bir o'yinchi o'zining amal bajarish navbati kelganida o'yin toshini ayni vaqtdagi koordinatasi \((x, y)\) dan olib, boshqa bir koordinata\((x', y')\)ga joylashtirishi kerak, bunda quyidagi shartlar bajarilishi zarur:
  • \(0 \le x' \le x\)
  • \(0 \le y' \le y\)
  • \(x'\) va \(y'\) butun son
  • \(0 < |x-x'|+|y-y'| \le k\)
• O'z navbati kelganida o'yin toshini \((0,0)\) koordinataga olib kelgan o'yinchi o'yin g'olibi hisoblanadi.

Agarda ushbu o'yinni Husanboy va Shohruh birgalikda o'ynashsa, o'yinda amal bajarishni Husanboy boshlab bersa hamda har ikkala o'yinchi optimal o'ynasa o'yinda kim g'olib bo'lishini aniqlang.

1 1
2

Husanboy

1 1
1

Shohruh

1000 1000
1000

Husanboy