1-daraja testi: Bronza

1-darajaBronza — algoritmik fikrlash1–8 darslar

Yigirma savol, 1–8 darslar bo’yicha. Savollar uch turga bo’lingan: murakkablik bahosi, usul tanlash va xato topish — olimpiadada eng ko’p kerak bo’ladigan uch ko’nikma.

Murakkablik bahosi

1Kompyuter bir soniyada taxminan nechta oddiy amal bajaradi? A) 10⁴ B) 10⁶ C) 10⁸ D) 10¹²

Javobni ko'rish

C. 10⁸ — qo’pol, lekin foydali o’lchov. Python’da bu raqamni o’n barobar past olish kerak: taxminan 10⁷. (4-dars)

2Shartda n ≤ 5000. Qaysi yechim sig'adi? A) 2ⁿ B) n³ C) n² D) n!

Javobni ko'rish

C. 5000² = 2,5 · 10⁷ — sig’adi. n³ esa 1,25 · 10¹¹ bo’lib ketadi. (4-dars)

3Shartda n ≤ 20. Bu chegara nimani ishora qiladi? A) Masala juda oson B) Barcha variantni ko'rish kutilmoqda C) Xato bor D) n log n kerak

Javobni ko'rish

B. Shunchalik kichik chegara deyarli har doim 2ⁿ yoki n! yechimga ochiq taklif bo’ladi. (2 va 4-darslar)

4n ikki barobar oshsa, n² yechim necha barobar sekinlashadi? A) 2 B) 3 C) 4 D) O'zgarmaydi

Javobni ko'rish

C. To’rt barobar. Shuning uchun n² yechimlar «birdan» yiqilgandek tuyuladi. (4-dars)

5Million elementli saralangan ro'yxatda ikkilik qidiruv nechta qadam qiladi? A) 10 B) 20 C) 1000 D) 10⁶

Javobni ko'rish

B. log₂(10⁶) ≈ 20. Har qadam qidiruv maydonini ikkiga bo’ladi. (7-dars)

6n = q = 200000 da prefiks yig'indi yechimi nechta amal qiladi? A) n · q B) n + q C) n² D) q log n

Javobni ko'rish

B. Jadval n amalda quriladi, keyin har so’rov bitta ayirish — jami 400 ming atrofida. (5-dars)

7Saralashning o'zi nechta amal oladi? A) n B) n log n C) n² D) log n

Javobni ko'rish

B. n = 200000 da bu 3,5 million atrofida — shuning uchun saralash deyarli har doim «arzon» hisoblanadi. (6-dars)

Usul tanlash

8Ro'yxatga o'zgarish kiritilmaydi, lekin oraliq yig'indisi 200 ming marta so'raladi. Qaysi usul? A) Har so'rovda qayta qo'shish B) Prefiks yig'indi jadvali C) Saralash D) Ikkilik qidiruv

Javobni ko'rish

B. Bir marta tayyorlanib, keyin har so’rovga bitta ayirish bilan javob berish. (5-dars)

9Saralangan ro'yxatda «shu son bormi?» degan so'rov ko'p marta beriladi. Qaysi usul? A) Chiziqli qidiruv B) Ikkilik qidiruv C) Prefiks D) Har juftni ko'rish

Javobni ko'rish

B. Ro’yxat saralangan ekan, har savolda yarmini tashlab yuborish mumkin. (7-dars)

10Bir o'lchamli ko'chada eng yaqin ikki uyni topish kerak, n ≤ 200000. Qaysi usul? A) Har juftni o'lchash B) Saralab, qo'shnilarni ko'rish C) Prefiks yig'indi D) Ochko'zlik

Javobni ko'rish

B. Saralangandan keyin eng yaqin juftlik albatta qo’shni bo’ladi — n² o’rniga n log n. (6-dars)

11Robot buyruqlarni bajaradi va bosib o'tgan har xil kataklar sanaladi. «Bu katakda bo'lganmidim?» savoliga qanday javob berish kerak? A) Ro'yxatda qidirish B) To'plamga saqlash C) Saralash D) Prefiks

Javobni ko'rish

B. To’plamda qidirish deyarli bir amal turadi, ro’yxatda esa ro’yxat uzunligiga bog’liq. (3-dars)

12Shartda n ≤ 3000 va har juftlikni ko'rish kerak. Nima qilasiz? A) Tezroq yechim izlayman B) To'liq izlash yozaman C) Masalani tashlab ketaman D) Chegarani e'tiborsiz qoldiraman

Javobni ko'rish

B. 3000²/2 = 4,5 million — sig’adi. Sig’adigan sodda yechim sig’maydigan chiroyli yechimdan afzal. (2 va 4-darslar)

13Ochko'z yechim yozdingiz va uch testda to'g'ri javob berdi. Keyingi qadam? A) Topshiraman B) Nega to'g'ri ishlashini asoslashga urinaman C) Yana test qo'shaman D) Tezlashtiraman

Javobni ko'rish

B. Testlar xatoning borligini ko’rsatadi, yo’qligini emas. Ochko’zlikda xato aynan asoslanmagan joyda bo’ladi. (8-dars)

14Nima uchun to'liq izlash yechimi tez yechim yozilgandan keyin ham saqlanadi? A) Kod chiroyli ko'rinishi uchun B) Etalon sifatida — javoblarni solishtirish uchun C) Zaxira sifatida D) Saqlanmaydi

Javobni ko'rish

B. Ikki yechimni bir kirishda yurgizib javoblarni solishtirish — xato topishning eng ishonchli usuli. (2-dars, keyin 15-dars)

Xato topish

15eng = 0 deb boshlab ro'yxatdagi eng katta sonni qidiryapmiz. Qachon xato chiqadi? A) Ro'yxat bo'sh bo'lsa B) Barcha sonlar manfiy bo'lsa C) Sonlar bir xil bo'lsa D) Ro'yxat uzun bo'lsa

Javobni ko'rish

B. Javob 0 bo’lib qaytadi — ro’yxatda umuman yo’q son. Boshlang’ich qiymat ro’yxatning o’zidan olinishi kerak. (1-dars)

16Juftliklarni sanashda ichki sikl range(i + 1, n) o'rniga range(n) yozildi. Natija? A) Xato xabari B) Javob ikki barobar katta va o'zi bilan juftlik ham sanaladi C) Cheksiz sikl D) Javob o'zgarmaydi

Javobni ko'rish

B. Kod yiqilmaydi, shunchaki noto’g’ri javob beradi — eng yomon turdagi xato. (2-dars)

17uylar = uylar.sort() yozildi. Nima bo'ladi? A) Ro'yxat saralanadi B) Yangi saralangan ro'yxat qaytadi C) uylar None bo'lib qoladi D) Xato xabari darhol chiqadi

Javobni ko'rish

C. sort() joyida saralaydi va None qaytaradi. Saralangan nusxa kerak bo’lsa — sorted(). (6-dars)

18Prefiks jadvalida p[r] - p[l] yozildi. Javob qanday buziladi? A) Ikki barobar katta B) Oxirgi element miqdoricha kam C) Manfiy D) O'zgarmaydi

Javobni ko'rish

B. p[k] birinchi k ta elementni beradi, ya’ni r-elementni ham qo’shish uchun p[r+1] kerak. Bir elementli oraliqda javob nolga aylanadi. (5-dars)

19Ikkilik qidiruvda chap = orta yozildi. Natija? A) Noto'g'ri javob B) Cheksiz sikl C) Sekin ishlaydi D) Bir elementda xato

Javobni ko'rish

B. Ikki element qolganda orta har safar chap ga teng chiqadi va oraliq kichraymaydi. To’g’risi: chap = orta + 1. (7-dars)

20Robot masalasida korilgan bo'sh to'plam bilan boshlandi. Xato qanday ko'rinadi? A) Javob bittaga kam B) Javob bittaga ko'p C) Xato xabari D) Cheksiz sikl

Javobni ko'rish

A. Boshlang’ich katak hech qachon qo’shilmaydi. Robot umuman qimirlamasa javob 0 bo’ladi. (3-dars)

Keyingi qadam

To’rttadan ko’p xato qilgan bo’lsangiz, mos darslarni qayta oching: 1-dars · 2-dars · 3-dars · 4-dars · 5-dars · 6-dars · 7-dars · 8-dars.

Eng ko’p xato 4-dars (murakkablik) va 7-dars (ikkilik qidiruv) savollarida bo’lsa, ikkinchi darajaga o’tishdan oldin ularni albatta qaytaring: keyingi sakkiz dars shu ikkisiga suyanadi.