A. A+B

Xotira: 32 MB, Vaqt: 1000 ms

Qorbobo ko'plab boshqa sport dasturlash musobaqalarida bo'lgani kabi bu musobaqani ham "A+B" masalasi bilan boshlamoqchi bo'ldi. U bu juda oson masala bo'lganligi uchun masalaga test generatori tuzishni "Dasturlash musobaqalari" bo'limiga endigina ishga joylashgan "Junior" darajadagi elf dasturchilarga berdi. Qorbobo ularga bu uchun C++ dasturlash tilidan foydalanishlari kerakligini aytdi. Lekin ular Qorboboning aytganini qilmasdan generator uchun Javascript dasturlash tilidan foydalanishdi va xatolikga yo'l qo'yishdi. Ya'ni generatorda qo'shiluvchi o'zgaruvchilardan biri string turida qolib ketgan edi, natijada generator ikki sonning yig'indisini emas ularni ketma-ket yozishdan hosil bo'ladigan sonni javob sifatida chiqaradigan bo'lib qoldi. Junior elflar esa bu xatolikni topa olmasdan, Qorboboga bildirmasdan masalaning shartini shu xatolikga moslab o'zgartirib qo'yishdi. Siz esa endi shu masalani yechishingiz kerak 😄😄.
Qissadan-hissa shuki, kattalarning gapiga kirish kerak 😁☝️.

1 1

11

1 2

12

B. Kuchli jamoa kerak

Xotira: 32 MB, Vaqt: 1000 ms

Hammaga ma'lumki Qorbobo shimoliy qutbda yashaydi, shimolliklarning azaliy raqiblari esa albatta janubiy qutbda yashovchilar. Qorbobo ular bilan bo'ladigan har qanday bellashuvlarga jiddiy tayyorgarlik ko'radi. Kelayotgan 2024-yil esa qutbliklar o'rtasidagi yanvar oyida o'tkaziladigan jamoaviy musobaqa bilan boshlanyapti. Musobaqa qoidalariga ko'ra jamoa 2 kishidan iborat bo'ladi, jamoalar o'zaro matematika va algoritmlashga oid masalalarni ishlagan holda bellashishadi. Ikkala qutb ham final bosqichiga o'zlarining eng kuchli 1 ta jamoasini chiqaradi.

Qorbobo yaxshi biladiki bu musobaqada yaxshi ishtirok etish uchun jamoada bitta matematik va bitta dasturchi bo'lishi kerak. Qorboboda bu borada juda kuchli bo'lgan N ta elf bor. U ushbu N ta elf orasidan 2 kishilik jamoa yig'ishga qiynalyapti, sababi barcha N ta elflar bir-biridan qolishmaydigan kuchli. Qorbobo bu elflarni 1 dan N gacha raqamlab chiqgan va qarasa toq o'rindagi elflar kuchli matematik, juft o'rindagilar esa kuchli dasturchi bo'lib saralanib qolibdi. Shunda Qorboboda 1 ta dasturchi va 1 ta matematik elfdan iborat jamoa tuzishning nechta usuli mavjud?

2

1

C. G'irromchi elflar

Xotira: 128 MB, Vaqt: 1000 ms

Qorbobo “A+B” masalasiga test tuzgan “Junior” elf dasturchilarning qilgan ishidan xabar topib qoldi va buning uchun ularni jazolashga qaror qildi. Jazo sifatida ularga bitta masala berdi, agar bu masalani ishlay olishmasa “Shimoliy qutb” kompaniyasining “Dasturlash musobaqalari” bo'limidan haydalishini aytdi. Masala sharti quyidagicha edi:

• Sizga N ta natural son berilgan. Ular orasida \(2^x*3^y\) ko'rinishida yozish mumkin bo'lganlarini tartibini o'zgartirmagan holda chiqaring.

Elflar bu masala uchun hamma holatlarni ko'rib chiqadigan “Brute force” yechim yoza olishdi xolos, yozgan dasturlari kutilgan natijani chiqarishi uchun soatlab vaqt sarflar edi. Lekin ular yana g'irromlik qilish yo'lini topishdi, ular Qorbobo o'tkazayotgan sport dasturlash musobaqasiga bu masalani ham qo'shib yuborishdi. Albatta masala testlarini “Brute force” yechim bilan deyarli kun bo'yi generatsiya qilishdi 😁. Musobaqa yakunida esa ishtirokchilar tomonidan jo'natilgan eng yaxshi yechimlarni olib Qorboboga o'zlarining yechimi sifatida ko'rsatishmoqchi. Endi bu masalani yechib g'irromchi elflarga yordam berishga majbursiz 🙃.

4
2 10 42 144

2 144

D. Junior elfning masalasi

Xotira: 64 MB, Vaqt: 1000 ms

“Dasturlash musobaqalari” bo'limidagi bir “Junior” elf dasturchining hayoliga musobaqaga qo'yish uchun ajoyib masala kelib qoldi va bu haqida Qorboboga aytdi. Lekin masalaga yechim yoza olmagani sababli bu masalani musobaqaga qo'shmadi. Lekin Qorbobo allaqachon bu masalaning testlarini tayyor qilib bo'lgan edi, chunki masala Qorboboga ham juda yoqqan edi 😃🥳. Masala sharti:

Bir nechta natural sonlar to'plamining ko'paytmasi P ga teng. To'plamdagi sonlarning yig'indisi eng kamida necha bo'lishini toping.

1

1

8

6

E. Sovg'a konveyeri

Xotira: 128 MB, Vaqt: 1000 ms

Shimoliy qutbda yaqinda katta tadbir bo'lib o'tadi. Sababi esa yangi sovg'a qadoqlash zavodining ochilish marosimidir. Zavod qadoqlanmagan sovg'alarni 3 ta nuqtadan qabul qiladi va ularni qadoqlash uchun bitta konveyerga birlashtiradi. Qadoqlanib chiqayotgan sovg'a o'z egasiga to'g'ri yetib borishi uchun sovg'alarning konveyerdan chiqish tartibi juda muxim. Qorbobo shuni hisobga olgan holda bugungi musobaqaga ham zavoddagi konveyerning ishlashini simulyatsiya qiluvchi masala qo'yishni xohladi. Chunki siz musobaqadan yaxshi o'tib, “Shimoliy qutb” kompaniyasiga ishga joylashganingizdan so'ng birinchi navbatta qiladigan proektingiz shu ish bo'ladi. 

Konveyer quyidagicha tartibda ishlashi kerak:

• 1-nuqtadan kiruvchi sovg'alar konveyerdagi navbatning boshiga qo'shiladi;
• 2-nuqtadan kiruvchi sovg'alar navbatning o'rtasiga qo'shiladi. Ya'ni navbatda N ta sovg'a bo'lsa \({\lfloor \frac{N}{2} \rfloor}\)- sovg'adan keyin qo'shiladi;
• 3-nuqtadan kiruvchi sovg'alar esa navbatning oxiriga qo'shiladi.

Sizdan konveyerning ishlash jarayoni haqida ma'lumotlar berilganda konveyerdan chiqayotgan sovg'alar tartibi so'raladi.

6
1 1
2 3
3 4
4
1 6
4

3 6

F. To'ra

Xotira: 64 MB, Vaqt: 1000 ms

Bu interaktiv masala.

8*8 o'lchamli shaxmat doskasining \(X_0Y_0\) katagida to'ra joylashgan. Sizdan to'ra joylashgan katak manzili \(X_0Y_0\) ni topish so'raladi. Buning uchun siz \(? \space X \space Y\) ko'rinishida so'rov jo'natishingiz mumkin, hakamlar hay'ati dasturi sizga javob sifatida \(|X_0-X|+|Y_0-Y|\) qiymatini qaytaradi. To'ra joylashgan manzilni \(! \space X \space Y\) ko'rinishida chiqarasiz va dastur yakuniga yetadi.
Siz ko'pi bilan 8 ta \(? \space X \space Y\) ko'rinishidagi so'rovni jo'natishingiz mumkin. To'ra joylashgan manzilni noto'g'ri chop etsangiz, so'rovlar soni oshib ketsa yoki noto'g'ri so'rov jo'natsangiz \(\textcolor{red}{Wrong \space answer}\) natijasini olasiz.

 

Namunaviy test:

stdin	stdout
8   6   0	? 1 1   ? 8 8   ? 5 5   ! 5 5

G. Eski fotoapparat

Xotira: 256 MB, Vaqt: 1000 ms

“Dasturlash musobaqalari” bo'limi uchun yaqinda yangi ofis qurildi. Shu sababli bu yerdagi barcha dasturchi elflar yangi ofisga ko'chish uchun eski ofisdagi hamma narsani yig'ishtirishdi. Narsalarni yig'ishtirish davomida “Junior” dasturchi elflar juda eski fotoapparat topib olishdi. Ular bir amallab fotoapparatdan chiqayotgan tasvirlarni raqamli ko'rinishga o'tkazishni uddalashdi, ammo fotoapparat eskiligi uchun chiqayotgan tasvirlarda ko'plab dog'lar bor. Ular tasvirdan dog'larni tozalaydigan dastur qilmoqchi bo'lishdi, ammo uddalay olishmadi. Siz ularga yordam bering.

Dastur quyidagicha ishlashi kerak:

Sizga binar tasvir (faqat oq va qora rangdan iborat tasvir) beriladi. Siz tasvirdan diametri K dan kichik yoki teng bo'lgan qora dog'larni o'chirib tashlashingiz kerak bo'ladi. Dog'ning diametri undagi istalgan ikkita piksel orasidagi maksimal masofa hisoblanadi. Bitta pikselga uning tepa, past, chap va o'ng taraflarida joylashgan piksellar qo'shni hisoblanadi.

4 4
1000
0110
0100
0010
2

0000
0000
0000
0000

H. Connecting game

Xotira: 64 MB, Vaqt: 1000 ms

Pokemon o'yinlari orasida "Connect animals" nomli ajoyib o'yin mavjud. O'yin shartiga ko'ra sizga hayvonlar rasmlari tushirilgan kartalar to'g'ri to'rtburchak ko'rinishida taxlangan holatda beriladi. Siz 2 ta bir xil rasmli kartalarni birlashtirish orqali o'yindan chiqarib yuborishingiz mumkin, hamma kartalarni chiqarib yuborganingizdan keyin o'yin yakuniga yetadi. 2 ta bir xil rasmli kartani birlashtirish uchun kartalar orasidagi yo'lda ko'pi bilan 2 ta burilish bo'lishi mumkin. 2 tadan ko'p bo'lgan holatda yoki kartalar orasida yo'l bo'lmagan holatda kartalarni o'yindan chiqara olmaysiz. Kartalar orasidagi yo'l boshqa karta ustidan o'tishi yoki diagonal bo'yicha o'tishi mumkin emas. O'yinni o'ynab ko'rish uchun link.
 

Sizga NxM o'lchamdagi o'yin maydoni beriladi. O'yin maydonidagi har bir katak ingliz alifbosining kichik harflari yoki . (nuqta) belgisidan iborat bo'lishi mumkin. Bunda harflar hayvonlarni, . belgisi esa bo'sh katakni ifodalaydi. Bir xil harflar bir xil hayvonlarni ifodalaydi. Shu berilgan o'yin holatida nechta birlashtirish imkoniyati borligini aniqlang.

3 3
...
a.a
...

1

3 3
a.a
a.a
a.a

15

1 3
aaa

3

I. Hech kim yecholmagan masala

Xotira: 256 MB, Vaqt: 1000 ms

Qorbobo yaqinda "Dasturlash musobaqalari" bo'limi uchun sport dasturlash bo'yicha musobaqa o'tkazdi. Unda bitta masalani hech qaysi elf yecha olmadi, hatto eng kuchlilari ham. Boshqa hamma masala tuzuvchilarga o'xshab Qorbobo ham bu masalani keyingi musobaqaga olib qo'ydi 😁, ya'ni ushbu musobaqaga. Masala sharti esa quyidagicha edi:
Natural bo'luvchilari soni N ta bo'lgan eng kichik natural sonni chiqaring.
Bu shart unchalik qiyin bo'lmasligi mumkin deb o'ylab, Qorbobo masalani so'rovli qilgan edi. Sizga Q ta so'rov va har bir so'rovda N soni beriladi. Siz har bir so'rov uchun N ta natural bo'luvchiga ega eng kichik natural sonni topishingiz kerak.

3
1
2
3

1
2
4

J. Maxsus sovg'a

Xotira: 256 MB, Vaqt: 2000 ms

Qorbobo sizga juda injiq bola uchun sovg'a tayyorlashni buyurdi. Bola sovg'a sifatida ko'pi bilan \(N\) ta shar olishni xohlaydi, lekin u injiqligi tufayli hamma sharlari och rangli bo'lib qolishini xohlamaydi, xuddi shunday to'q rangli bo'lib qolishini ham xohlamaydi. Sizga Qorbobo \(K\) xil rangdagi sharlarning har biridan cheksiz miqdorda ishlatishga ruxsat berdi. Siz sovg'a bolaga yoqishi uchun quyidagicha usulda sovg'ani tayyorlashingiz kerak:

• \(K\) xil shardan 1 tadan \(N\) tagacha qilib yasash mumkin bo'lgan barcha turli sharlar to'plamini yasab chiqasiz va ularni och ranglardan to'qga qarab saralaysiz. (Leksikografik saralashga o'xshash, aniqroq tushunish uchun namunaviy test va uning izohini tekshiring)
• Tasavvur qiling sizda \(S\) ta sovg'a (sharlar to'plami) hosil bo'ldi. Siz bolaga sovg'a sifatida \(\frac{S}{2}\) - sovg'ani berasiz, chunki bu sovg'a ranglar jihatidan muvozanatlangan bo'ladi.

Bolaga berilgan sovg'adagi sharlar ranglarini chiqaring.

E'tibor bering: To'plamda bir nechta bir xil rangdagi sharlar bo'lishi mumkin.

2 2

1 2

2 3

2 1