A. Yangi yil musobaqasi

Xotira: 16 MB, Vaqt: 500 ms

Har yili Qorbobo Yangi yil bayramini yaxshi o‘tkazib, barcha bolalarga o‘z sovg‘alarini yetkazib bo‘lgach elflar orasida turli sport musobaqalarini o‘tkazib keladi. Qorbobo elflari turli guruhlarga bo‘lingan va har bir guruh uchun turlicha sport turlari tanlanadi. Dasturchi elflar guruhi uchun esa odatda shaxmat sport turi tanlanadi. Chunki Qorbobo dasturchilarni juda ham aqlli bo‘lishi kerak deb hisoblaydi va bunda shaxmatning yordami kattaligini yaxshi biladi.

Xullas bu yil ham dasturchi elflar orasida shaxmat musobaqasi o‘tkazildi va qoidalar quyidagicha belgilandi:

• Har bir dasturchi elfning o‘yindagi darajasi turlicha va ular oldindan ma’lum.
• Har bir bosqichda ro‘yxat boshidagi 2 ta o‘yinchi o‘zaro o‘ynaydi va mag‘lub bo‘lgan o‘yinchi ro‘yxat oxiriga o‘tkaziladi.
• Dastlabki k ta g‘alabaga erishgan o‘yinchi g‘olib hisoblanadi.

Sizning vazifangiz esa g‘olib elfning darajasini topish.

2 2
1 2

2

B. Shoshilish kerak!

Xotira: 16 MB, Vaqt: 500 ms

Maqsud ukasi Suhrob bilan Yangi yil kechasida aylanish uchun Samarqand shahridagi eng katta archaga chiqib ketdi. Ular aylanib yurib vaqt o‘tganini sezmay qolishdi. Bir vaqt soatlariga qarashsa Yangi yil kirishiga juda oz fursat qolibdi. Shundagina uyga ketishga shoshilib qolishdi.

Yangi yil archasi \(X_1, Y_1\) koordinatada, ularning uylari esa \(X_2, Y_2\) koordinatada joylashgan. Ular bir qadamda 8 ta qo‘shni koordinataning biriga o‘tishi mumkin va buning uchun 0.5 soniya vaqt sarflashadi. Ular uylariga yetib borguncha minimal qancha vaqt o‘tishini toping.

4 4 8 8

2

C. Uchish yo'lakchasi 1

Xotira: 32 MB, Vaqt: 1000 ms

Quruvchi elflar guruhi bu yili Qorbobo chanasi uchun yangi uchish-qo‘nish yo‘lakchasi qurishdi. Ular hamma ishni deyarli bitirishdi, ammo bitta kamchilik qoldi, ya’ni yo‘lakchadagi maxsus relslar orasiga kafel yotqizish kerak edi. Elflar rels orasiga to‘liq mos tushuvchi \(N\) ta kafel topib kelishdi. Endigi vazifa esa bu kafellar yordamida \(L\) uzunlikdagi yo‘lakchani to‘liq qoplab bo‘lish yoki bo‘lmasligini aniqlash.

5 11
3 6 2 8 4

yes

3 13
5 7 2

no

D. Uchish yo'lakchasi 2

Xotira: 32 MB, Vaqt: 1000 ms

Quruvchi elflar guruhi bu yili Qorbobo chanasi uchun yangi uchish-qo‘nish yo‘lakchasi qurishdi. Ular hamma ishni deyarli bitirishdi, ammo bitta kamchilik qoldi, ya’ni yo‘lakchadagi maxsus relslar orasiga kafel yotqizish kerak edi. Elflar rels orasiga to‘liq mos tushuvchi \(N\) ta kafel topib kelishdi. Endigi vazifa esa bu kafellar yordamida \(L\) uzunlikdagi yo‘lakchani to‘liq qoplab bo‘lish yoki bo‘lmasligini aniqlash. Agar qoplashning iloji bo‘lsa ishlatilgan kafellar haqida Qorboboga hisobot yozilishi kerak.

5 11
3 6 2 8 4

0 1 2

E. Archa

Xotira: 128 MB, Vaqt: 1000 ms

Qorboboning dasturchi elflar guruhi Yangi yilga o‘zlari uchun Archa nomli ma’lumotlar tuzilmasi yaratishdi va u uchun dokumentatsiya ham yozishdi. Siz esa “Tester” sifatida berilgan ma’lumotlar Archa tuzilmasiga mos kelishi yoki yo‘qligini tekshirishingiz kerak. Siz tekshirishni quyidagi dokumentatsiyaning bir qismi orqali amalga oshirishingiz kerak:

1. Archaning faqatgina bitta uchi (root) bo‘ladi va u –1 bilan belgilanadi.
2. Archada istalgan bitta tugundan ikkinchisiga borish mumkin.
3. Archaning har bir qavatidagi (level) tugunlar soni o‘zidan oldingisidan ko‘pi bilan K ta ko‘p bo‘lishi kerak.

Elflar berilgan tuzilma Archaligini tekshirish uchun shu ma’lumotlar yetarli deb hisoblashadi.

6 2
-1 1 1 2 2 3

yes

5 1
-1 1 1 2 2

no

F. Archa 2

Xotira: 64 MB, Vaqt: 1000 ms

Dasturchi elflar o‘z Archalarini muvaffaqiyatli yaratishgach uni bezatishni o‘ylab qolishdi. Buning uchun ular Archaning har bir tuguniga rangli o‘yinchoqlar ilib chiqishdi va Archaning chiroyini baholamoqchi bo‘lishdi. Agar Archada ikkita qo‘shni o‘yinchoq bir xil rangda bo‘lsa Archa chiroyli chiqmagan hisoblanadi, aks holda u chiroyli. Berilgan ma’lumotlar asosida Archani baholang.

O‘yinchoqga uning chap, o‘ng tomonlaridagi va o‘zaro bog‘langan tugunlarda joylashgan o‘yinchoqlar qo‘shni hisoblanadi.

 

6
-1 1 1 2 2 3
1 2 3 1 3 4

good

6
-1 1 1 2 2 3
1 2 3 1 3 3

bad